Java LinkedList

Hai! Semua pelajaran terkini telah ditumpukan kepada ArrayList . Struktur data ini sangat mudah dan berguna. Ia boleh mengendalikan banyak tugas. Tetapi Java mempunyai banyak struktur data lain. kenapa? Di atas semua itu, kerana julat tugas adalah sangat besar, dan struktur data yang paling cekap adalah berbeza untuk tugasan yang berbeza. Hari ini kita akan bertemu dengan struktur baharu: Java LinkedList , senarai dua pautan.

Mari lihat bagaimana ia disusun, mengapa ia dipanggil berkait berganda, bagaimana ia berbeza daripada ArrayList . Unsur-unsur dalam Java LinkedList sebenarnya adalah pautan dalam satu rantaian. Selain data, setiap elemen menyimpan rujukan kepada elemen sebelumnya dan seterusnya. Rujukan ini membolehkan anda berpindah dari satu elemen ke elemen yang lain. Beginilah cara anda menciptanya:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Output: [Hello World! Nama saya Earl, saya suka Java, saya tinggal di Kanada] Begini rupa senarai kami: Senarai Berpaut - 2

Mari lihat cara menambah elemen baharu. Ini dilakukan menggunakan kaedah add() .

earlBio.add(str2);

Pada titik dalam kod, senarai kami terdiri daripada satu elemen: String str1 . Mari lihat apa yang berlaku seterusnya dalam gambar: Senarai Berpaut - 3

Akibatnya, str2 dan str1 menjadi dipautkan melalui pautan seterusnya dan sebelumnya yang disimpan dalam nod senarai ini: Senarai Berpaut - 4

Sekarang anda harus memahami idea utama senarai berganda. Rangkaian pautan inilah yang menjadikan elemen LinkedList satu senarai. Tidak seperti ArrayList , LinkedList tidak mempunyai tatasusunan atau apa-apa tatasusunan seperti di dalamnya. Mana-mana (baik, kebanyakan) kerja dengan ArrayList bermuara kepada bekerja dengan tatasusunan dalaman. Sebarang kerja dengan Java LinkedListbermuara kepada menukar pautan. Ini boleh dilihat dengan jelas dengan menambahkan elemen pada bahagian tengah senarai:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Seperti yang anda lihat, kaedah tambah () yang terlampau beban membolehkan anda menentukan indeks khusus untuk item baharu. Dalam kes ini, kami ingin menambah String str2 antara str1 dan str3 . Inilah yang akan berlaku secara dalaman: Senarai Berpaut - 5

Selepas menukar pautan dalaman, str2 telah berjaya ditambahkan ke senarai: Senarai Berpaut - 6

Kini semua 3 elemen disambungkan. Anda boleh bergerak melalui pautan seterusnya dari elemen pertama pada rantai ke yang terakhir dan kembali lagi. Jadi, kami agak selesa dengan sisipan, tetapi bagaimana pula dengan mengalih keluar elemen? Prinsipnya betul-betul sama. Kami hanya mengemas kini pautan dalam dua elemen "ke kiri dan kanan" elemen yang dialih keluar:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

Inilah yang berlaku jika kami memadamkan item dengan indeks 1 (ia berada di tengah-tengah senarai): Senarai Berpaut - 7

Selepas mengemas kini pautan, kami mendapat hasil yang diingini: Senarai Berpaut - 8

Tidak seperti operasi penyingkiran dalam ArrayList , di sini tidak perlu mengalih elemen tatasusunan atau melakukan apa-apa jenis. Kami hanya mengemas kini pautan untuk str1 dan str3 . Mereka kini menunjuk satu sama lain, dan str2 telah " keluar " daripada rantaian pautan dan bukan lagi sebahagian daripada senarai.

Gambaran keseluruhan kaedah

LinkedList mempunyai banyak kaedah yang sama dengan ArrayList . Sebagai contoh, kedua-dua kelas mempunyai kaedah seperti add() , remove() , indexOf() , clear() , contains() (menunjukkan sama ada item berada dalam senarai), set() (menggantikan elemen sedia ada), dan saiz() . Walaupun kebanyakannya berfungsi secara berbeza secara dalaman (seperti yang kami temui dengan add() dan remove() ), hasil akhirnya adalah sama. Walau bagaimanapun, LinkedList mempunyai kaedah berasingan untuk bekerja dengan permulaan dan akhir senarai, yang tidak ada pada ArrayList :

addFirst() , addLast() : Kaedah ini untuk menambah elemen pada permulaan/akhir senarai

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Output: [Kereta{model='Ferrari 360 Spider'}, Kereta{model='Bugatti Veyron'}, Kereta{model='Lamborghini Diablo'}] [Kereta{model='Ford Mondeo'}, Kereta{model=' Ferrari 360 Spider'}, Kereta{model='Bugatti Veyron'}, Kereta{model='Lamborghini Diablo'}, Kereta{model='Fiat Ducato'}] Kami berakhir dengan "Ford" di bahagian atas senarai, dan "Fiat" pada penghujungnya.

peekFirst() , peekLast() : Kaedah mengembalikan elemen pertama/terakhir dalam senarai. Mereka mengembalikan null jika senarai kosong.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Output: Kereta{model='Ferrari 360 Spider'} Kereta{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Kaedah ini mengembalikan elemen pertama/terakhir dalam senarai dan mengeluarkannya daripada senarai. Mereka mengembalikan null jika senarai kosong

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

Output: Kereta{model='Ferrari 360 Spider'} Kereta{model='Lamborghini Diablo'} Apakah yang tinggal dalam senarai? [Kereta{model='Bugatti Veyron'}]

toArray() : Kaedah ini mengembalikan tatasusunan yang mengandungi item senarai

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Output: [Kereta{model='Ferrari 360 Spider'}, Kereta{model='Bugatti Veyron'}, Kereta{model='Lamborghini Diablo'}] Sekarang kita tahu cara LinkedList berfungsi dan cara organisasinya berbeza daripada ArrayList . Apakah faedah menggunakan LinkedList ? Di atas segalanya, kami mendapat manfaat apabila bekerja di tengah-tengah senarai. Operasi memasukkan dan mengalih keluar di tengah LinkedList adalah lebih mudah daripada dalam ArrayList . Kami hanya mengemas kini pautan elemen jiran, dan elemen yang tidak diingini "terputus" daripada rantaian pautan. Tetapi dalam ArrayList , kita mesti

semak sama ada terdapat ruang yang mencukupi (semasa memasukkan)
jika tidak, maka kami membuat tatasusunan baru dan menyalin data di sana (semasa memasukkan)
kami keluarkan/masukkan elemen, dan alihkan semua elemen lain ke kanan/kiri (bergantung pada jenis operasi). Dan kerumitan proses ini sangat bergantung pada saiz senarai. Satu perkara untuk menyalin/menggerakkan 10 elemen, dan agak lain untuk melakukan perkara yang sama dengan sejuta elemen.

Dalam erti kata lain, jika operasi sisipan/pembuangan di tengah-tengah senarai adalah yang paling biasa dalam program anda, LinkedList sepatutnya lebih pantas daripada ArrayList .

Secara teori

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Output: Masa yang diambil oleh LinkedList (dalam milisaat) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Output: Masa yang diambil oleh ArrayList (dalam milisaat) = 181 Itu tidak dijangka! Kami melakukan operasi di mana LinkedList sepatutnya lebih cekap: memasukkan 100 item di tengah-tengah senarai. Dan senarai kami sangat besar: 5,000,000 elemen. ArrayList terpaksa mengalihkan beberapa juta item dengan setiap sisipan! Bagaimana ia menang? Pertama, masa yang diperlukan untuk ArrayList untuk mengakses elemen adalah tetap (malar). Apabila anda menulis

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

maka ArrayList [2_000_000] ialah alamat memori tertentu (lagipun, senarai itu mempunyai tatasusunan dalaman). Tetapi, LinkedList tidak mempunyai tatasusunan. Ia akan mencari unsur nombor 2_000_000 di sepanjang rantaian pautan. Untuk LinkedList, ini bukan alamat memori, tetapi pautan yang masih perlu dicapai: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… Akibatnya, semasa setiap sisipan (pembuangan) di tengah-tengah senarai , ArrayList sudah mengetahui alamat memori yang tepat untuk diakses, tetapi LinkedList masih perlu "ke sana". Kedua, terdapat struktur ArrayListsendiri. Fungsi dalaman khas ( System.arrayCopy() ) mengembangkan tatasusunan dalaman dan menyalin serta mengalihkan semua elemen. Ia sangat pantas, kerana ia dioptimumkan untuk kerja khusus ini. Tetapi apabila anda tidak perlu "mencapai" indeks tertentu, LinkedList adalah pemenang. Katakan kita memasukkan pada permulaan senarai. Mari cuba masukkan sejuta elemen di sana:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Output: Hasil dalam milisaat: 43448 Hasil dalam milisaat: 107 Sekarang kita mendapat hasil yang berbeza sama sekali! ArrayList menghabiskan lebih daripada 43 saat untuk memasukkan sejuta item di hadapan senarai yang diambil, manakala LinkedList berjaya melakukannya dalam 0.1 saat! LinkedList mendapat manfaat di sini, kerana ia tidak perlu melalui rantaian pautan ke tengah senarai setiap kali. Ia segera mencari indeks yang diperlukan pada permulaan senarai, jadi algoritma yang berbeza sudah menjadi kelebihan. :) Sebenarnya, perbincangan " ArrayList versus LinkedList " sangat meluas dan kami tidak akan menyelaminya secara mendalam pada tahap semasa. Perkara utama yang perlu anda ingat ialah ini:

Tidak semua kelebihan teori mana-mana koleksi tertentu sentiasa berfungsi dalam realiti (kami melihat ini dengan contoh yang melibatkan bahagian tengah senarai)
Jangan gunakan kedudukan yang melampau semasa memilih koleksi (" ArrayList sentiasa lebih pantas. Gunakannya dan anda tidak boleh salah. Tiada siapa yang telah menggunakan LinkedList untuk masa yang lama").

Walaupun pengarang LinkedList , Joshua Bloch, mengatakan perkara ini berlaku. :) Namun, perspektif ini jauh daripada 100% betul, dan kami telah meyakinkan diri kami tentang perkara ini. Dalam contoh terdahulu kami, LinkedList adalah 400 (!) kali lebih pantas. Perkara lain ialah terdapat beberapa situasi di mana LinkedList adalah pilihan terbaik. Tetapi mereka wujud, dan pada masa yang tepat LinkedListboleh memberi ganjaran yang lumayan. Jangan lupa apa yang kami katakan pada permulaan pelajaran: struktur data yang paling cekap adalah berbeza untuk tugasan yang berbeza. Adalah mustahil untuk memastikan 100% struktur data yang terbaik sehingga anda mengetahui semua syarat tugas anda. Anda akan mengetahui lebih lanjut tentang koleksi ini kemudian, yang akan memudahkan pilihan anda. Tetapi pilihan yang paling mudah dan paling berkesan adalah sentiasa sama: cuba kedua-duanya pada data sebenar yang digunakan dalam program anda. Kemudian anda akan dapat melihat sendiri prestasi kedua-dua jenis senarai dan anda pasti tidak akan salah. :) Untuk mengukuhkan apa yang anda pelajari, kami cadangkan anda menonton pelajaran video daripada Kursus Java kami

Bacaan lanjut:
Struktur Data Java LinkedList