Struktur Data Daftar Tertaut di Jawa

Struktur data yang berbeda dibuat untuk tujuan yang berbeda. Anda mungkin tahu tentang ArrayList (jika masih belum, kami sarankan Anda untuk membacanya terlebih dahulu). Pada artikel ini, kita akan belajar tentang LinkedList dan menyadari manfaat dari koleksi ini. Jika Anda melihat sumber kode kelas LinkedList Java 8 (atau versi bahasa yang lebih baru) (di situs web Oracle atau di IDE Anda, dalam hal IDEA: crtl+B pada nama kelas), Anda akan melihat deklarasi berikutnya:

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

Saat ini informasi terpenting dari kode adalah fakta bahwa LinkedList mengimplementasikan antarmuka List dan Deque . Antarmuka Daftar menyimpan urutan penambahan item dan memungkinkan akses ke item berdasarkan indeks. Antrean "biasa" mendukung penambahan elemen hingga akhir dan mengekstraknya dari awal. Deque adalah antrian dua arah, dan mendukung penambahan dan penghapusan elemen dari kedua sisi. Anda mungkin menganggapnya sebagai kombinasi tumpukan dan antrian. Jadi, LinkedList adalah implementasi dari keduanya, dan ini memungkinkan kita membuat antrean dua arah yang terdiri dari objek apa pun termasuk null. LinkedListadalah kumpulan elemen. Kita bisa melihatnya di sumber kode kelas, kali ini perhatikan bidang:

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

Setiap elemen, biasanya kami menyebutnya Node , berisi sebuah objek dan referensi ke dua objek yang berdekatan — yang sebelumnya dan yang berikutnya. Oleh karena itu, tidak terlalu efektif dalam hal penggunaan memori. Karena LinkedList sebenarnya adalah struktur dua arah, kita dapat dengan mudah menambah atau menghapus elemen dari kedua sisi.

Konstruktor LinkedList

Kembali ke sumber kode, kita dapat mengetahui bahwa LinkedList memiliki dua konstruktor

• LinkedList() tanpa parameter digunakan untuk membuat daftar kosong.
• >LinkedList(Collection<? extends E> c) adalah untuk membuat daftar yang berisi elemen dari koleksi yang ditentukan, agar dikembalikan oleh iterator koleksi.

Deklarasi LinkedList

Faktanya, daftar tertaut (Java atau dalam bahasa lain) terdiri dari urutan node. Setiap node dirancang untuk menyimpan objek dari tipe yang ditentukan saat membuat. Jadi untuk membuat LinkedList , kode Java adalah sebagai berikut:

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

Kami punya objek untuk menyimpan urutan bilangan bulat dan tautan ke tetangga. Namun, saat ini kosong.

Operasi Utama LinkedList

Seperti biasa, dalam kasus Collections Anda dapat memasukkan elemen ke dalam LinkedList (ke ujung atau ke tengah), hapus dari sana, dan dapatkan elemen berdasarkan indeks. Jadi inilah mereka:

• add(E element) Menambahkan elemen yang ditentukan ke akhir daftar ini;
• add(int index, E element) Menyisipkan elemen pada posisi yang ditentukan index ;
• get(int index) Mengembalikan elemen pada posisi yang ditentukan dalam daftar ini;
• remove(int index) Menghapus elemen yang berada pada indeks posisi;
• hapus(Objek o) Menghapus kemunculan pertama ? o elemen dari daftar ini jika ada.
• remove() Mengambil dan menghapus elemen pertama dari daftar.

Implementasi daftar tertaut di Jawa, menambah dan menghapus elemen. Contoh

Mari kita coba operasi ini dalam latihan. Pertama, implementasi Java LinkedList: membuat LinkedList of Strings, menambahkan 3 elemen di sana. Kemudian hapus satu, lalu tambahkan satu di 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);
   }

Hasil menjalankan program ini:

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 adalah bagian dari kerangka Koleksi , Anda dapat menggunakan Iterator untuk menghapus elemen, serta iterator khusus untuk daftar — ListIterator . Terlebih lagi, operasi dengan iterator memberikan manfaat utama dari kelas LinkedList : kinerja operasi penyisipan/penghapusan yang baik. Menggunakan Iterator Anda mungkin mendapatkan waktu yang konstan untuk mereka. Nanti di artikel ini, kita akan menulis contoh kode untuk membandingkan ArrayList dan LinkedList+Iterator

• Iterator.remove() menghapus elemen terakhir yang dikembalikan oleh iterator ini.
• ListIterator.add(E element) menyisipkan elemen ke dalam daftar

Contoh Java LinkedList: cara kerja Iterator

Di sini kami memiliki kode Contoh Java LinkedList kecil , tempat kami mencoba menambah dan menghapus melalui 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);
 
   }
}

Hasil menjalankan program ini:

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

Lebih Banyak Operasi Java LinkedList :

• addFirst() , addLast() menambahkan elemen ke awal/akhir daftar
• clear() menghapus semua elemen dari daftar
• berisi(Objek o) mengembalikan nilai true jika daftar berisi elemen o.
• indexOf(Object o) mengembalikan indeks kemunculan pertama elemen o, atau -1 jika tidak ada dalam daftar.
• set(int index, elemen E) mengganti elemen pada posisi indeks dengan elemen
• size()Mengembalikan jumlah elemen dalam daftar.
• toArray() mengembalikan array yang berisi semua elemen daftar dari elemen pertama hingga elemen terakhir.

BTW menjadi antrian dua ukuran, LinkedList di Jawa memiliki operasi khusus tumpukan:

• pop() yang memunculkan elemen dari tumpukan (diwakili oleh daftar)
• push(E e) yang mendorong elemen ke tumpukan (diwakili oleh daftar ini)

Cara membalikkan LinkedList: contoh

Ini adalah contoh kecil, tugas yang populer namun mudah bagi pemula. Kami memiliki LinkedList dan harus membalikkannya. Algoritme termudah adalah melalui LinkedList dalam urutan terbalik dan memasukkan setiap elemen ke dalam yang baru. Namun, mungkin Anda akan menemukan cara yang lebih baik? Berikut adalah kode program java daftar tertaut terbalik:

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;
   }
}

Hasil:

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

LinkedList vs ArrayList: kapan harus menggunakan yang pertama

Baik LinkedList dan ArrayList adalah implementasi dari antarmuka Daftar . LinkedList mengimplementasikannya dengan double-linked list. ArrayList mengimplementasikannya menggunakan array yang mengubah ukuran secara dinamis. Seperti yang sudah Anda ketahui, setiap node LinkedList berisi Objek dan dua referensi ke tetangga. Itu berarti biaya memori tambahan untuk menyimpan referensi antar elemen dalam kasus Java LinkedList . ArrayList mengimplementasikannya dengan array yang mengubah ukuran secara dinamis. Beberapa operasi LinkedList dan ArrayList terlihat sama, tetapi cara kerjanya berbeda. Di dalam ArrayListkasus, Anda memanipulasi dengan array internal, di LinkedList — dengan referensi. ArrayList adalah implementasi Daftar yang paling populer . Anda pasti harus menggunakan ArrayList ketika akses indeks adalah prioritas karena operasi ini dilakukan dalam waktu yang konstan. Menambahkan ke akhir daftar rata-rata juga dilakukan dalam waktu yang konstan. Terlebih lagi, ArrayList tidak memiliki biaya tambahan untuk menyimpan banyak elemen. Anda dapat menghitung sebagai Kontra kecepatan operasi penyisipan dan penghapusan jika dilakukan bukan di akhir daftar. LinkedListlebih berguna dalam hal kinerja operasi penyisipan dan penghapusan dalam beberapa hal: jika Anda menggunakan iterator, ini terjadi dalam waktu yang konstan. Operasi akses berdasarkan indeks dilakukan dengan mencari dari awal hingga akhir (mana yang lebih dekat) ke elemen yang diinginkan. Namun, jangan lupakan biaya tambahan untuk menyimpan referensi antar elemen. Jadi di sini standar operasi LinkedList dan ArrayList dengan runtime algoritmik. N mengacu pada jumlah item yang sudah ada dalam daftar. O(N) berarti bahwa dalam kasus terburuk kita harus "menelusuri" seluruh daftar sampai posisi yang diperlukan ditemukan, misalnya, untuk memasukkan elemen baru ke dalam daftar. O(1)berarti bahwa operasi terjadi dalam waktu yang konstan, secara independen pada jumlah item.

Kompleksitas Waktu LinkedList

Kompleksitas Waktu ArrayList

Kapan menggunakan LinkedList: Contoh

Jelas, ArrayList adalah implementasi Daftar yang paling populer . Namun, Anda mungkin menemui situasi, ketika operasi tambah/hapus diperlukan terlalu sering. Dalam hal ini, LinkedList bersama dengan Iterator dapat bermanfaat. Ini sebuah contoh. Kami punya daftar panjang, dan kami harus menghapus setiap elemen dari daftar ini. Ayo lakukan tugas ini dengan ArrayList dan LinkedList + Iterator . Kami membandingkan waktu setiap operasi dan mencetaknya ke konsol. Ini kodenya:

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);
       }
   }
}

Hasil untuk ArrayList:

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

Hasil untuk LinkedList:

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

Seperti yang Anda lihat dalam kasus ini LinkedList jauh lebih efektif. Mari jujur. Dalam pengembangan perangkat lunak nyata, penggunaan LinkedList adalah kejadian langka. Namun demikian, seorang profesional harus mengetahui keberadaan struktur data ini dan kelebihannya. Jika dalam kode asli LinkedList adalah tamu langka, di wawancara Java Junior sangat populer. Namun, inilah yang ditulis Joshua Bloch tentang LinkedList :

AddOn: Daftar Tertaut Tunggal Java

Tidak ada Daftar Tertaut Tunggal di antara Koleksi klasik di Jawa, Daftar Tertaut Tunggal adalah struktur di mana setiap node berisi Objek dan referensi ke Node berikutnya, tetapi tidak untuk Node sebelumnya. Java LinkedList adalah dua-tertaut, tetapi tidak ada yang mengganggu Anda untuk membuat Struktur Data Anda sendiri, seperti Singly ,code>Linked List. Berikut beberapa langkah untuk menyelesaikan tugas ini:

1. Buat kelas Node dengan dua atribut, data dan berikutnya. Next adalah referensi ke node berikutnya.
2. Buat kelas FirstLast dengan dua atribut, head, dan tail.
3. Buat metode add() untuk menambahkan node baru ke daftar. Periksa apakah daftarnya kosong dulu ( head == null ). Jika demikian, kepala dan ekor merujuk ke simpul baru. Jika daftar tidak kosong, simpul baru akan ditambahkan ke akhir, sehingga atribut berikutnya dari ekor mengacu pada simpul yang ditambahkan dan simpul baru menjadi ekor dari daftar.

Omong-omong, Anda juga dapat mencoba membuat LinkedList Anda sendiri sebagai latihan. Semoga berhasil dalam pembelajaran Anda.