LinkedList dalam Java

hello! Semua kuliah baru-baru ini telah ditumpukan untuk mengkaji senarai ArrayList . Struktur data ini sangat mudah dan membolehkan anda menyelesaikan banyak masalah. Walau bagaimanapun, Java mempunyai banyak struktur data lain. kenapa? Pertama sekali, kerana julat tugas sedia ada sangat luas, dan untuk tugas yang berbeza struktur data yang berbeza adalah paling berkesan . Hari ini kita akan berkenalan dengan struktur baharu - senarai pautan berganda LinkedList . Mari kita fikirkan cara ia berfungsi, sebab ia dipanggil dua kali bersambung dan bagaimana ia berbeza daripada ArrayList . Dalam LinkedList, unsur-unsur sebenarnya adalah pautan dalam rantai. Setiap elemen, sebagai tambahan kepada data yang disimpannya, mempunyai pautan ke elemen sebelumnya dan seterusnya . Pautan ini membolehkan anda berpindah dari satu elemen ke elemen yang lain. Ia dicipta seperti ini:

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Kesimpulan:

[Hello World! My name is Earl, I love Java, I live in Moscow]

Beginilah rupa struktur senarai kami: Mari lihat bagaimana elemen baharu ditambah. Ini dilakukan menggunakan add().

earlBio.add(str2);

Pada masa baris kod ini, senarai kami terdiri daripada satu elemen - rentetan str1. Mari lihat apa yang berlaku seterusnya dalam gambar: Akibatnya str2, dan str1disambungkan melalui pautan yang disimpan di dalamnya nextdan previous: Sekarang anda harus memahami idea utama senarai berganda. Unsur-unsur LinkedListadalah satu senarai dengan tepat terima kasih kepada rangkaian pautan ini. Tiada tatasusunan di dalam LinkedList, seperti dalam ArrayList, atau apa-apa yang serupa. Semua kerja dengan ArrayList (secara keseluruhannya) adalah untuk bekerja dengan tatasusunan dalaman. Semua kerja dengan LinkedListdatang kepada menukar pautan. Ini sangat jelas dilihat dengan menambahkan elemen ke tengah senarai:

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Seperti yang anda lihat, kaedah terlebih beban add()membolehkan anda menentukan indeks khusus untuk elemen baharu. Dalam kes ini, kami ingin menambah baris str2antara str1dan str3. Inilah yang akan berlaku di dalam: Dan sebagai hasil daripada menukar pautan dalaman, elemen str2berjaya ditambahkan ke senarai: Kini semua 3 elemen dipautkan. Dari elemen pertama di sepanjang rantai nextanda boleh pergi ke yang terakhir dan belakang. Kami telah mengetahui lebih kurang sisipan itu, tetapi bagaimana pula dengan memadamkan elemen? Prinsip operasi adalah sama. Kami hanya mentakrifkan semula pautan dua elemen "di sisi" yang dialih keluar:

public class Main {

   public static void main(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 Moscow");

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

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

Inilah yang akan berlaku jika kita memadamkan elemen dengan indeks 1 (ia berada di tengah-tengah senarai): Selepas mentakrifkan semula pautan, kita mendapat hasil yang diingini: Tidak seperti pemadaman, ArrayListtiada anjakan elemen tatasusunan dan seumpamanya. Kami hanya mentakrifkan semula rujukan unsur str1dan str3. Kini mereka menunjuk satu sama lain, dan objek itu str2telah "keluar" daripada rantaian pautan ini dan bukan lagi sebahagian daripada senarai.

Gambaran keseluruhan kaedah

Ia LinkedListmempunyai banyak persamaan dengan ArrayListkaedah. Sebagai contoh, kaedah seperti add(), remove(), indexOf(), clear(), contains()(adalah elemen yang terkandung dalam senarai), set()(memasukkan elemen dengan penggantian) size()terdapat dalam kedua-dua kelas. Walaupun (seperti yang kami dapati dalam contoh add()dan remove()) ramai daripada mereka bekerja secara berbeza secara dalaman, tetapi akhirnya mereka melakukan perkara yang sama. Walau bagaimanapun, ia LinkedListmempunyai kaedah berasingan untuk bekerja dengan permulaan dan akhir senarai, yang tidak terdapat dalam ArrayList:

• addFirst(), addLast(): kaedah 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 + '\'' +
               '}';
   }
}

Kesimpulan:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

Akibatnya, Ford berada di bahagian atas senarai, dan Fiat di penghujungnya.

• peekFirst(), peekLast(): kembalikan elemen pertama/terakhir senarai. Kembali nulljika 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());
}

Kesimpulan:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): kembalikan elemen pertama/terakhir senarai dan keluarkannya daripada senarai . Kembali nulljika 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 left on the list?");
   System.out.println(cars);
}

Kesimpulan:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): mengembalikan tatasusunan elemen 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));
}

Kesimpulan:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Sekarang kita tahu cara ia berfungsi LinkedListdan bagaimana ia berbeza daripada ArrayList. Apakah faedah menggunakan LinkedList? Pertama sekali, dalam bekerja dengan bahagian tengah senarai . Memasukkan dan memadam di tengah LinkedListadalah lebih mudah daripada di ArrayList. Kami hanya mentakrifkan semula pautan elemen jiran, dan elemen yang tidak perlu "jatuh" daripada rantai pautan. Semasa di dalam ArrayListkita:

• semak jika terdapat ruang yang mencukupi (semasa memasukkan)
• jika tidak mencukupi, buat tatasusunan baharu dan salin data di sana (semasa menampal)
• padam/masukkan elemen, dan alihkan semua elemen lain ke kanan/kiri (bergantung pada jenis operasi). Selain itu, kerumitan proses ini sangat bergantung pada saiz senarai. Satu perkara untuk menyalin/menggerakkan 10 elemen, tetapi agak lain untuk melakukan perkara yang sama dengan sejuta elemen.

Iaitu, jika dalam program anda operasi sisipan/pemadaman berlaku lebih kerap dengan bahagian tengah senarai, LinkedListia sepatutnya lebih cepat 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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Kesimpulan:

Время работы для LinkedList (в мorсекундах) = 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 to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Kesimpulan:

Время работы для ArrayList (в миллисекундах) = 181

Tiba-tiba! Nampaknya kami sedang melakukan operasi yang LinkedListsepatutnya lebih cekap - memasukkan 100 elemen ke tengah senarai. Dan senarai kami sangat besar - 5,000,000 elemen: ArrayListkami terpaksa mengalih beberapa juta elemen setiap kali kami memasukkannya! Apakah sebab kemenangannya? Pertama, elemen diakses dalam ArrayListjumlah masa yang tetap. Apabila anda menunjukkan:

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

maka dalam kes ArrayList[2_000_000] ini ialah alamat khusus dalam ingatan, kerana ia mempunyai tatasusunan di dalamnya. Manakala LinkedListtatasusunan tidak. Ia akan mencari elemen nombor 2_000_000 di sepanjang rantaian pautan. Baginya, ini bukan alamat dalam ingatan, 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, dengan setiap sisipan (pemadaman) di tengah-tengah senarai, ArrayListia sudah mengetahui alamat tepat dalam ingatan yang harus diakses, tetapi LinkedListia masih perlu "mengetahui" ke tempat yang betul. Kedua , perkara itu adalah dalam struktur ArrayList'a itu sendiri. Memperluas tatasusunan dalaman, menyalin semua elemen dan elemen peralihan dijalankan oleh fungsi dalaman khas - System.arrayCopy(). Ia berfungsi dengan cepat kerana ia dioptimumkan khas untuk kerja ini. Tetapi dalam situasi di mana tidak perlu "menginjak" ke indeks yang dikehendaki, LinkedListia benar-benar menunjukkan dirinya lebih baik. Contohnya, jika sisipan berlaku 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("Result in milliseconds: " + msDelay);
       return msDelay;

   }

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

}

Kesimpulan:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

Hasil yang sama sekali berbeza! Ia mengambil masa lebih daripada 43 saat untuk memasukkan sejuta elemen ke dalam permulaan senarai ArrayList, manakala LinkedListia selesai dalam 0.1 saat! Ia adalah fakta bahawa dalam situasi ini LinkedListkami tidak perlu "berjalan" melalui rantaian pautan ke tengah senarai setiap kali. Dia segera menemui indeks yang diperlukan pada permulaan senarai, dan di sana perbezaan dalam prinsip operasi sudah ada di pihaknya :) Sebenarnya, perbincangan " ArrayListberbanding LinkedList" sangat meluas, dan kami tidak akan mendalaminya pada masa ini tahap. Perkara utama yang perlu anda ingat:

• Tidak semua kelebihan koleksi tertentu "di atas kertas" akan berfungsi dalam realiti (kami melihat ini menggunakan contoh dari tengah senarai)
• Anda tidak sepatutnya melampau apabila memilih koleksi (" ArrayListia sentiasa lebih pantas, gunakannya dan anda tidak akan salah. LinkedListTiada siapa yang telah menggunakannya untuk masa yang lama").

Walaupun pencipta LinkedListJoshua Bloch berkata demikian :) Walau bagaimanapun, pandangan ini jauh dari 100% betul, dan kami yakin akan hal ini. Dalam contoh terdahulu kami LinkedListia berfungsi 400 (!) kali lebih cepat. Perkara lain ialah terdapat beberapa situasi apabila LinkedListia akan menjadi pilihan terbaik. Tetapi mereka wujud, dan pada masa yang tepat LinkedListmereka boleh membantu anda dengan serius. Jangan lupa apa yang kita bincangkan pada permulaan kuliah: struktur data yang berbeza adalah paling berkesan untuk tugasan yang berbeza. Adalah mustahil untuk mengatakan dengan keyakinan 100% struktur data mana yang akan menjadi lebih baik sehingga semua keadaan masalah diketahui. Kemudian anda akan mengetahui lebih lanjut tentang koleksi ini, dan lebih mudah untuk membuat pilihan. Tetapi pilihan yang paling mudah dan paling berkesan adalah sentiasa sama: menguji kedua-duanya pada data sebenar daripada program anda. Kemudian anda boleh melihat dengan mata anda sendiri keputusan kedua-dua senarai dan anda pasti tidak akan salah :)