Struktur Data Senarai Terpaut dalam Java

Struktur data yang berbeza dicipta untuk tujuan yang berbeza. Anda mungkin tahu tentang ArrayList (jika masih belum, kami mengesyorkan anda membacanya terlebih dahulu). Dalam artikel ini, kita akan belajar tentang LinkedList dan untuk menyedari kegunaan koleksi ini. Jika anda melihat sumber kod kelas LinkedList Java 8 (atau versi bahasa yang lebih baru) (di tapak web Oracle atau dalam IDE anda, sekiranya IDEA: crtl+B pada nama kelas) anda akan melihat pengisytiharan seterusnya:

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

Pada masa ini, maklumat yang paling penting daripada kod adalah fakta bahawa LinkedList melaksanakan antara muka Senarai dan Deque . Antara muka Senarai menyimpan urutan penambahan item dan membenarkan akses kepada item mengikut indeks. Barisan "biasa" menyokong penambahan elemen pada penghujung dan mengekstraknya dari awal. Deque ialah baris gilir dua hala, dan ia menyokong menambah dan mengalih keluar elemen dari kedua-dua belah pihak. Anda mungkin menganggapnya sebagai gabungan timbunan dan baris gilir. Jadi, LinkedList ialah pelaksanaan kedua-dua ini, dan ia membolehkan kami membuat baris gilir dua hala yang terdiri daripada sebarang objek termasuk null. LinkedListialah himpunan unsur. Kita boleh melihatnya dalam sumber kod kelas, kali ini perhatikan medan:

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

Setiap elemen, biasanya kami panggil Node , mengandungi objek dan rujukan kepada dua objek bersebelahan — sebelumnya dan seterusnya. Oleh itu, ia tidak begitu berkesan dari segi penggunaan memori. Memandangkan LinkedList sebenarnya adalah struktur dua arah, kami boleh menambah atau mengalih keluar elemen dengan mudah daripada kedua-dua belah pihak.

Pembina LinkedList

Kembali ke sumber kod, kita boleh mengetahui bahawa LinkedList mempunyai dua pembina

• LinkedList() tanpa parameter digunakan untuk membina senarai kosong.
• >LinkedList(Collection<? extends E> c) adalah untuk mencipta senarai yang mengandungi unsur-unsur koleksi yang ditentukan, supaya ia dikembalikan oleh iterator koleksi.

Pengisytiharan LinkedList

Malah, senarai terpaut (Java atau dalam mana-mana bahasa lain) terdiri daripada urutan nod. Setiap nod direka bentuk untuk menyimpan objek daripada jenis yang ditentukan semasa mencipta. Jadi untuk membuat LinkedList , kod Java ialah yang seterusnya:

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

Kami mempunyai objek untuk menyimpan jujukan integer dan pautan ke jiran. Walau bagaimanapun, ia kosong pada masa ini.

Operasi Utama LinkedList

Seperti biasa, dalam kes Koleksi, anda boleh meletakkan elemen ke dalam LinkedList (hingga hujungnya atau ke tengah), alih keluar dari sana dan dapatkan elemen mengikut indeks. Jadi inilah mereka:

• add(E element) Menambahkan elemen yang ditentukan pada penghujung senarai ini;
• add(int index, E element) Memasukkan elemen pada indeks kedudukan yang ditentukan ;
• get(int index) Mengembalikan elemen pada kedudukan yang ditentukan dalam senarai ini;
• remove(int index) Mengeluarkan elemen yang berada pada indeks kedudukan;
• remove(Object o) Mengeluarkan kejadian pertama ? o elemen daripada senarai ini jika ia ada.
• remove() Mengambil dan mengalih keluar elemen pertama senarai.

Pelaksanaan senarai terpaut dalam Java, menambah dan mengalih keluar elemen. Contoh

Mari cuba operasi ini dalam amalan. Pertama, pelaksanaan Java LinkedList: mencipta LinkedList of Strings, menambah di sana 3 elemen. Kemudian keluarkan satu, kemudian tambah 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 daripada 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 ialah sebahagian daripada rangka kerja Koleksi , anda boleh menggunakan Iterator untuk mengalih keluar elemen, serta lelaran khas untuk senarai — ListIterator . Lebih-lebih lagi, operasi dengan iterator memberikan faedah utama kelas LinkedList : prestasi operasi sisip/padam yang baik. Menggunakan Iterator anda mungkin mendapat masa yang tetap untuk mereka. Kemudian dalam artikel ini, kami akan menulis contoh kod untuk membandingkan ArrayList dan LinkedList+Iterator

• Iterator.remove() mengalih keluar elemen terakhir yang dikembalikan oleh iterator ini.
• ListIterator.add(elemen E) memasukkan elemen ke dalam senarai

Contoh Java LinkedList: cara Iterator berfungsi

Di sini kami mempunyai kod Contoh Java LinkedList yang kecil , di mana kami cuba menambah dan memadam 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 daripada 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() menambah elemen pada permulaan/akhir senarai
• clear() mengalih keluar semua elemen daripada senarai
• mengandungi(Objek o) mengembalikan benar jika senarai mengandungi elemen o.
• indexOf(Objek o) mengembalikan indeks kejadian pertama unsur o, atau -1 jika ia tiada dalam senarai.
• set(int index, E element) menggantikan elemen pada kedudukan indeks dengan elemen
• size()Mengembalikan kuantiti elemen dalam senarai.
• toArray() mengembalikan tatasusunan yang mengandungi semua elemen senarai dari elemen pertama hingga terakhir.

BTW sebagai baris gilir bersaiz dua, LinkedList dalam Java mempunyai tindanan operasi khusus:

• pop() yang memaparkan elemen dari timbunan (diwakili oleh senarai)
• push(E e) yang menolak elemen ke dalam timbunan (diwakili oleh senarai ini)

Bagaimana untuk membalikkan LinkedList: contoh

Berikut adalah contoh kecil, tugas yang popular, namun mudah untuk pemula. Kami mempunyai LinkedList dan harus membalikkannya. Algoritma yang paling mudah ialah melalui LinkedList dalam susunan terbalik dan meletakkan setiap elemen ke dalam yang baharu. Walau bagaimanapun, mungkin anda akan menemui cara yang lebih baik? Berikut ialah kod program java senarai pautan 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;
   }
}

Keputusan:

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

LinkedList vs ArrayList: bila hendak menggunakan yang pertama

Kedua-dua LinkedList dan ArrayList ialah pelaksanaan antara muka Senarai . LinkedList melaksanakannya dengan senarai berganda. ArrayList melaksanakannya menggunakan tatasusunan mengubah saiz secara dinamik. Seperti yang anda sedia maklum, setiap nod LinkedList mengandungi Objek dan dua rujukan kepada jiran. Ini bermakna kos memori tambahan untuk menyimpan rujukan antara elemen dalam kes Java LinkedList . ArrayList melaksanakannya dengan tatasusunan mengubah saiz secara dinamik. Beberapa operasi LinkedList dan ArrayList kelihatan sama, tetapi ia berfungsi dengan cara yang berbeza. Dalam ArrayListkes, anda memanipulasi dengan tatasusunan dalaman, dalam LinkedList — dengan rujukan. ArrayList ialah pelaksanaan Senarai yang paling popular . Anda pastinya harus menggunakan ArrayList apabila akses indeks menjadi keutamaan kerana operasi ini dilakukan dalam masa yang tetap. Menambah pada akhir senarai secara purata juga dilakukan dalam masa yang tetap. Lebih-lebih lagi, ArrayList tidak mempunyai kos tambahan untuk menyimpan sekumpulan elemen. Anda boleh mengira sebagai Keburukan kelajuan memasukkan dan mengalih keluar operasi apabila ia dilakukan bukan di penghujung senarai. LinkedListadalah lebih berguna sekiranya prestasi operasi masukkan dan padam dalam beberapa cara: jika anda menggunakan iterator, ia berlaku dalam masa yang tetap. Operasi capaian mengikut indeks dilakukan dengan mencari dari awal penghujung (yang mana lebih dekat) kepada elemen yang dikehendaki. Walau bagaimanapun, jangan lupa tentang kos tambahan untuk menyimpan rujukan antara elemen. Jadi di sini operasi LinkedList dan ArrayList standard dengan masa jalan algoritma. N merujuk kepada bilangan item yang sudah ada dalam senarai. O(N) bermakna dalam kes yang paling teruk kita harus "berjalan" melalui keseluruhan senarai sehingga kedudukan yang diperlukan ditemui, sebagai contoh, untuk memasukkan elemen baharu ke dalam senarai. O(1)bermakna bahawa operasi berlaku dalam masa yang tetap, secara bebas pada bilangan item.

Kerumitan Masa LinkedList

Kerumitan Masa ArrayList

Bila hendak menggunakan LinkedList: Contoh

Sudah tentu, ArrayList ialah pelaksanaan Senarai yang paling popular . Walau bagaimanapun, anda mungkin menghadapi situasi, apabila operasi tambah/buang diperlukan terlalu kerap. Dalam kes itu, LinkedList bersama-sama dengan Iterator boleh memberi manfaat. Berikut adalah contoh. Kami mempunyai senarai yang panjang, dan kami harus memadamkan setiap elemen daripada senarai ini. Mari lakukan tugas ini dengan ArrayList dan LinkedList + Iterator . Kami membandingkan masa setiap operasi dan mencetaknya ke dalam konsol. Berikut kodnya:

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

Keputusan untuk ArrayList:

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

Keputusan untuk LinkedList:

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

Seperti yang anda lihat dalam kes ini LinkedList adalah cara yang lebih berkesan. Jujurlah. Dalam pembangunan perisian sebenar, penggunaan LinkList adalah sejenis peristiwa yang jarang berlaku. Namun begitu, seorang profesional harus mengetahui tentang kewujudan struktur data ini dan kelebihannya. Jika dalam kod sebenar LinkedList adalah tetamu yang jarang ditemui, pada wawancara Java Junior ia sangat popular. Namun, inilah yang ditulis Joshua Bloch tentang LinkedList :

AddOn: Senarai Berpaut Tunggal Java

Tiada Senarai Berpaut Tunggal antara Koleksi klasik di Jawa, Senarai Berpaut Tunggal ialah struktur di mana setiap nod mengandungi Objek dan rujukan kepada Nod seterusnya, tetapi bukan untuk Nod sebelumnya. Java LinkedList adalah dua pautan, tetapi tiada siapa yang mengganggu anda untuk mencipta Struktur Data anda sendiri, seperti Singlely ,code>Linked List. Berikut ialah beberapa langkah untuk menyelesaikan tugasan ini:

1. Buat kelas Node dengan dua atribut, data dan seterusnya. Seterusnya ialah rujukan kepada nod seterusnya.
2. Buat kelas FirstLast dengan dua atribut, kepala dan ekor.
3. Buat kaedah add() untuk menambah nod baharu pada senarai. Semak sama ada senarai itu kosong dahulu ( head == null ). Jika ya, kepala dan ekor merujuk kepada nod baharu. Jika senarai tidak kosong, nod baharu akan ditambah ke penghujungnya, jadi atribut ekor seterusnya merujuk kepada nod yang ditambah dan nod baharu menjadi ekor senarai.

Dengan cara ini anda boleh cuba membuat LinkedList anda sendiri sebagai latihan juga. Semoga berjaya dalam pembelajaran anda.