Struktur Data Daftar Terkait ing Jawa

Struktur data sing beda digawe kanggo tujuan sing beda. Sampeyan bisa uga ngerti babagan ArrayList (yen isih durung, disaranake sampeyan maca babagan iki dhisik). Ing artikel iki, kita bakal sinau babagan LinkedList lan ngerti apa koleksi iki apik. Yen sampeyan ndeleng sumber kode kelas LinkedList Java 8 (utawa versi basa sing luwih anyar) (ing situs web Oracle utawa ing IDE sampeyan, yen IDEA: crtl + B ing jeneng kelas) sampeyan bakal weruh deklarasi sabanjure:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Saiki, informasi paling penting saka kode kasebut yaiku nyatane LinkedList ngetrapake antarmuka List lan Deque . Antarmuka List njaga urutan nambah item lan ngidini akses menyang item kanthi indeks. Antrian "biasa" ndhukung nambah unsur ing pungkasan lan ngekstrak saka wiwitan. Deque minangka antrian loro-lorone, lan ndhukung nambah lan mbusak unsur saka loro-lorone. Sampeyan bisa uga mikir minangka kombinasi tumpukan lan antrian. Dadi, LinkedList minangka implementasine saka loro kasebut, lan ngidini kita nggawe antrian bidirectional sing kalebu obyek apa wae kalebu null. LinkedListyaiku kumpulan unsur. Kita bisa ndeleng ing sumber kode kelas, wektu iki menehi perhatian menyang lapangan:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Saben unsur, biasane diarani Node , ngemot obyek lan referensi kanggo rong obyek tetanggan - sadurunge lan sabanjure. Mula, ora efektif banget babagan nggunakake memori. Amarga LinkedList sejatine minangka struktur bidirectional, kita bisa kanthi gampang nambah utawa mbusak unsur saka loro-lorone.

LinkedList Konstruktor

Bali menyang sumber kode, kita bisa ngerteni manawa LinkedList duwe loro konstruktor

• LinkedList () tanpa paramèter digunakake kanggo mbangun dhaftar kosong.
• >LinkedList(Koleksi<? ngluwihi E> c) kanggo nggawe dhaptar sing ngemot unsur-unsur koleksi sing ditemtokake, supaya bisa dibalekake dening iterator koleksi.

Pranyatan LinkedList

Nyatane, dhaptar sing disambung (Jawa utawa ing basa liya) kalebu urutan simpul. Saben simpul dirancang kanggo nyimpen obyek saka jinis sing ditetepake nalika nggawe. Dadi kanggo nggawe LinkedList , kode Java yaiku:

LinkedList<Integer> myList = new LinkedList<>();

Kita duwe obyek kanggo njaga urutan wilangan bulat lan pranala menyang tetanggan. Nanging, saiki kosong.

Operasi Utama LinkedList

Minangka biasanipun, ing cilik saka Koleksi sampeyan bisa sijine unsur menyang LinkedList (ing pungkasan utawa ing tengah), mbusak saka ing kono, lan njaluk unsur dening indeks. Dadi ing ngisor iki:

• nambah (E unsur) Appends unsur kasebut kanggo mburi dhaftar iki;
• add (int index, E unsur) Nglebokake unsur ing indeks posisi sing ditemtokake ;
• njaluk (int indeks) Ngasilake unsur ing posisi kasebut ing dhaftar iki;
• mbusak (indeks int) Mbusak unsur sing ana ing indeks posisi;
• mbusak (Obyek o) Mbusak kedadeyan pisanan saka? o unsur saka dhaftar iki yen ana.
• mbusak () Nompo lan mbusak unsur pisanan dhaftar.

Implementasi dhaptar link ing Jawa, nambah lan mbusak unsur. Tuladha

Ayo nyoba operasi iki ing latihan. Pisanan, implementasine Java LinkedList: nggawe LinkedList of Strings, nambah ana 3 unsur. Banjur copot siji, banjur tambahake siji ing tengah.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Asil saka mbukak program iki:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList minangka bagean saka kerangka Koleksi , sampeyan bisa nggunakake Iterator kanggo mbusak unsur, uga iterator khusus kanggo dhaptar - ListIterator . Malah liyane, operasi karo iterator menehi keuntungan utama kelas LinkedList : kinerja apik saka operasi insert / mbusak. Nggunakake Iterator sampeyan bisa entuk wektu sing tetep. Mengko ing artikel iki, kita bakal nulis conto kode kanggo mbandhingake ArrayList lan LinkedList+Iterator

• Iterator.remove () mbusak unsur pungkasan bali dening iterator iki.
• ListIterator.add (E unsur) nglebokake unsur menyang dhaftar

Tuladha Java LinkedList: cara kerja Iterator

Ing kene kita duwe kode Conto Java LinkedList cilik , ing ngendi kita nyoba nambah lan mbusak liwat Iterator.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

Asil saka mbukak program iki:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Operasi Java LinkedList liyane :

• addFirst () , addLast () nambah unsur ing wiwitan / pungkasan dhaptar
• cetha () mbusak kabeh unsur saka dhaftar
• ngandhut (Obyek o) ngasilake bener yen dhaptar ngemot unsur o.
• indexOf (Obyek o) ngasilake indeks kedadeyan pisanan saka unsur o, utawa -1 yen ora ana ing dhaptar.
• set (int index, E unsur) ngganti unsur ing posisi indeks karo unsur
• size () Ngasilake jumlah unsur ing dhaftar.
• toArray () ngasilake array sing ngemot kabeh unsur dhaptar saka pisanan nganti unsur pungkasan.

BTW minangka antrian ukuran loro, LinkedList ing Jawa nduweni operasi khusus tumpukan:

• pop () sing njedhul unsur saka tumpukan (diwakili dening dhaptar)
• push (E e) sing nyurung unsur menyang tumpukan (diwakili dening dhaptar iki)

Carane mbalikke LinkedList: contone

Iki minangka conto cilik, sing populer, nanging tugas sing gampang kanggo pamula. Kita duwe LinkedList lan kudu mbalikke. Algoritma sing paling gampang yaiku ngliwati LinkedList kanthi urutan mbalikke lan sijine saben unsur menyang sing anyar. Nanging, mungkin sampeyan bakal nemokake cara sing luwih apik? Punika kode program java reverse linked list:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Hasile:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: nalika nggunakake sing pisanan

LinkedList lan ArrayList minangka implementasi antarmuka List . LinkedList ngleksanakake karo dhaptar dobel-linked. ArrayList ngleksanakake nggunakake array ngowahi ukuran kanthi dinamis. Kaya sing wis dingerteni, saben simpul LinkedList ngemot Obyek lan rong referensi kanggo tetanggan. Tegese biaya memori tambahan kanggo nyimpen referensi antarane unsur ing kasus Java LinkedList . ArrayList ngleksanakake karo array ngowahi ukuran kanthi dinamis. Sawetara operasi LinkedList lan ArrayList katon padha, nanging bisa digunakake kanthi cara sing beda. Ing ArrayListcilik, sampeyan ngapusi karo array internal, ing LinkedList - karo referensi. ArrayList minangka implementasi List sing paling populer . Sampeyan mesthi kudu nggunakake ArrayList nalika akses indeks minangka prioritas amarga operasi kasebut ditindakake ing wektu sing tetep. Nambah ing pungkasan dhaftar ing rata-rata uga rampung ing wektu pancet. Malah luwih, ArrayList ora duwe biaya tambahan kanggo nyimpen akeh unsur. Sampeyan bisa uga count minangka Cons kacepetan selipan lan njabut operasi nalika rampung ora ing mburi dhaftar. LinkedListluwih migunani ing kasus insert lan mbusak kinerja operasi ing sawetara cara: yen sampeyan nggunakake iterator iku dumadi ing wektu pancet. Operasi akses miturut indeks ditindakake kanthi nggoleki saka wiwitan pungkasan (sing luwih cedhak) menyang unsur sing dikarepake. Nanging, aja lali babagan biaya tambahan kanggo nyimpen referensi ing antarane unsur. Dadi ing kene standar LinkedList lan ArrayList operasi kanthi runtime algoritma. N nuduhake jumlah item sing wis ana ing dhaptar. O (N) tegese ing kasus paling awon kita kudu "mlaku" liwat kabeh dhaftar nganti posisi needed ketemu, Contone, kanggo selipan saka unsur anyar menyang dhaftar. O(1)tegese operasi mengkono ing wektu pancet, independen ing nomer item.

Kompleksitas Wektu LinkedList

Kompleksitas Wektu ArrayList

Nalika nggunakake LinkedList: Conto

Mesthine, ArrayList minangka implementasi List sing paling populer . Nanging, sampeyan bisa uga ketemu kahanan, nalika nambah / mbusak operasi dibutuhake asring banget. Ing kasus kasebut, LinkedList kabeh bebarengan karo Iterator bisa migunani. Punika conto. Kita duwe dhaptar sing dawa, lan kita kudu mbusak kabeh unsur saka dhaptar iki. Ayo nindakake tugas iki karo ArrayList lan LinkedList + Iterator . Kita mbandhingake wektu saben operasi lan dicithak menyang konsol. Iki kode:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Asil kanggo ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Hasil LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Kaya sing sampeyan ngerteni ing kasus iki, LinkedList luwih efektif. Ayo dadi jujur. Ing pangembangan piranti lunak nyata, panggunaan LinkList minangka acara langka. Nanging, profesional kudu ngerti babagan struktur data iki lan kaluwihan. Yen ing kode nyata LinkedList minangka tamu langka, ing wawancara Java Junior banget populer. Nanging, iki sing ditulis Joshua Bloch babagan LinkedList :

AddOn: Singly Linked List Java

Ora ana Singly Linked List ing antarane Koleksi klasik ing Jawa, Singly Linked List minangka struktur ing ngendi saben simpul ngemot Obyek lan referensi menyang Node sabanjure, nanging ora kanggo sing sadurunge. Java LinkedList ana rong pranala, nanging ora ana sing ngganggu sampeyan nggawe Struktur Data dhewe, kayata Singly ,code>Linked List. Ing ngisor iki sawetara langkah kanggo ngrampungake tugas kasebut:

1. Nggawe kelas Node kanthi rong atribut, data lan sabanjure. Sabanjure minangka referensi menyang simpul sabanjure.
2. Gawe kelas FirstLast kanthi rong atribut, sirah, lan buntut.
3. Nggawe metode add () kanggo nambah simpul anyar menyang dhaptar. Priksa manawa dhaptar kosong dhisik ( kepala == null ). Yen mangkono, sirah lan buntut nuduhake simpul anyar. Yen dhaptar ora kosong, simpul anyar bakal ditambahake ing pungkasan, mula atribut buntut sabanjure nuduhake simpul sing ditambahake lan simpul anyar dadi buntut dhaptar.

Miturut cara, sampeyan bisa uga nyoba nggawe LinkedList dhewe minangka latihan uga. Good luck ing sinau.