Daftar Tertaut di Java

Halo! Semua kuliah baru-baru ini dikhususkan untuk mempelajari daftar ArrayList . Struktur data ini sangat nyaman dan memungkinkan Anda memecahkan banyak masalah. Namun, Java memiliki banyak struktur data lainnya. Mengapa? Pertama-tama, karena jangkauan tugas yang ada sangat luas, dan untuk tugas yang berbeda, struktur data yang berbeda adalah yang paling efektif . Hari ini kita akan berkenalan dengan struktur baru - daftar tertaut ganda LinkedList . Mari kita cari tahu cara kerjanya, mengapa disebut terhubung ganda, dan apa bedanya dengan ArrayList . Dalam LinkedList, elemen sebenarnya adalah tautan dalam sebuah rantai. Setiap elemen, selain data yang disimpannya, memiliki link ke elemen sebelumnya dan berikutnya . Tautan ini memungkinkan Anda berpindah dari satu elemen ke elemen lainnya. Itu dibuat 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]

Struktur daftar kita akan terlihat seperti ini: Mari kita lihat bagaimana elemen baru ditambahkan. Ini dilakukan dengan menggunakan add().

earlBio.add(str2);

Pada saat baris kode ini dibuat, daftar kami terdiri dari satu elemen - string str1. Mari kita lihat apa yang terjadi selanjutnya pada gambar: Hasilnya str2, dan str1menjadi terhubung melalui tautan yang tersimpan di dalamnya nextdan previous: Sekarang Anda harus memahami gagasan utama dari daftar tertaut ganda. Elemen-elemennya LinkedListmenjadi satu daftar berkat rantai tautan ini. Tidak ada array di dalamnya LinkedList, seperti in ArrayList, atau yang serupa. Semua pekerjaan dengan ArrayList (pada umumnya) dilakukan dengan bekerja dengan array internal. Semua pekerjaan LinkedListbermuara pada mengubah tautan. Ini terlihat jelas dengan menambahkan elemen ke tengah daftar:

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, metode kelebihan beban add()memungkinkan Anda menentukan indeks spesifik untuk elemen baru. Dalam hal ini, kami ingin menambahkan garis str2antara str1dan str3. Inilah yang akan terjadi di dalam: Dan sebagai hasil dari perubahan tautan internal, elemen tersebut str2berhasil ditambahkan ke daftar: Sekarang ketiga elemen tersebut telah ditautkan. Dari elemen pertama di sepanjang rantai, nextAnda dapat melanjutkan ke elemen terakhir dan sebaliknya. Kami kurang lebih telah mengetahui penyisipannya, tetapi bagaimana dengan menghapus elemen? Prinsip pengoperasiannya sama. Kita cukup mendefinisikan ulang hubungan dua elemen “di sisi” elemen yang akan dihapus:

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 terjadi jika kita menghapus elemen dengan indeks 1 (ada di tengah daftar): Setelah mendefinisikan ulang tautan, kita mendapatkan hasil yang diinginkan: Berbeda dengan menghapus, ArrayListtidak ada pergeseran elemen array dan sejenisnya. Kami hanya mendefinisikan ulang referensi elemen str1dan str3. Sekarang mereka menunjuk satu sama lain, dan objek tersebut str2telah “keluar” dari rantai tautan ini dan tidak lagi menjadi bagian dari daftar.

Ikhtisar metode

Ini LinkedListmemiliki banyak kesamaan dengan ArrayListmetodenya. Misalnya, metode seperti add(), remove(), indexOf(), clear(), contains()(adalah elemen yang terdapat dalam daftar), set()(memasukkan elemen dengan penggantian) size()ada di kedua kelas. Meskipun (seperti yang kita temukan dalam contoh add()dan remove()) banyak dari mereka bekerja secara internal secara berbeda, tetapi pada akhirnya mereka melakukan hal yang sama. Namun, ia LinkedListmemiliki metode terpisah untuk bekerja dengan awal dan akhir daftar, yang tidak ada di ArrayList:

• addFirst(), addLast(): metode untuk menambahkan elemen ke awal/akhir daftar

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'}]

Hasilnya, Ford berada di urutan teratas daftar, dan Fiat di urutan terakhir.

• peekFirst(), peekLast(): mengembalikan elemen pertama/terakhir dari daftar. Kembalikan nulljika daftarnya 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(): mengembalikan elemen pertama/terakhir dari daftar dan menghapusnya dari daftar . Kembalikan nulljika daftarnya 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 array elemen daftar

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 kerjanya LinkedListdan perbedaannya ArrayList. Apa manfaat menggunakannya LinkedList? Pertama-tama, dalam bekerja dengan bagian tengah daftar . Memasukkan dan menghapus di tengah LinkedListjauh lebih sederhana daripada di ArrayList. Kami hanya mendefinisikan ulang tautan elemen-elemen tetangga, dan elemen yang tidak perlu “jatuh” dari rantai tautan. Sementara di dalam ArrayListkita:

• periksa apakah ada cukup ruang (saat memasukkan)
• jika dirasa kurang, buat array baru dan copy data disana (saat paste)
• hapus/masukkan elemen, dan geser semua elemen lainnya ke kanan/kiri (tergantung pada jenis operasinya). Selain itu, kerumitan proses ini sangat bergantung pada besarnya daftar. Menyalin/memindahkan 10 elemen adalah satu hal, tetapi melakukan hal yang sama dengan sejuta elemen adalah hal lain.

Artinya, jika operasi penyisipan/penghapusan dalam program Anda lebih sering terjadi di bagian tengah daftar, LinkedListmaka operasi tersebut akan 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! Tampaknya kami melakukan operasi yang LinkedListseharusnya jauh lebih efisien - memasukkan 100 elemen ke tengah daftar. Dan daftar kami sangat banyak - 5.000.000 elemen: ArrayListkami harus menggeser beberapa juta elemen setiap kali kami memasukkannya! Apa alasan kemenangannya? Pertama, suatu elemen diakses dalam ArrayListjangka waktu yang tetap. Saat Anda menunjukkan:

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

maka dalam kasus ArrayList[2_000_000] ini adalah alamat khusus di memori, karena memiliki array di dalamnya. Sedangkan LinkedListarraynya tidak. Ini akan mencari elemen nomor 2_000_000 di sepanjang rantai tautan. Baginya, ini bukanlah alamat yang ada di ingatan, melainkan link yang masih perlu dijangkau:

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 penyisipan (penghapusan) di tengah daftar, ArrayListia sudah mengetahui alamat pasti di memori yang harus diaksesnya, namun LinkedListmasih perlu “mencari tahu” ke tempat yang tepat. Kedua , persoalannya ada pada struktur ArrayList'a itu sendiri. Memperluas array internal, menyalin semua elemen dan menggeser elemen dilakukan oleh fungsi internal khusus - System.arrayCopy(). Ia bekerja sangat cepat karena dioptimalkan secara khusus untuk pekerjaan ini. Namun dalam situasi di mana tidak perlu “menginjak” indeks yang diinginkan, LinkedListini benar-benar menunjukkan dirinya lebih baik. Misalnya, jika penyisipan terjadi di awal daftar. Mari kita coba memasukkan 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 sangat berbeda! Butuh lebih dari 43 detik untuk memasukkan sejuta elemen ke awal daftar ArrayList, sementara LinkedListitu selesai dalam 0,1 detik! Faktanya adalah bahwa dalam situasi ini LinkedListkita tidak harus “berlari” melalui rantai tautan ke tengah daftar setiap saat. Dia segera menemukan indeks yang diperlukan di awal daftar, dan di sana perbedaan prinsip pengoperasian sudah ada di pihaknya :) Faktanya, diskusi “ ArrayListversus LinkedList” sangat luas, dan kami tidak akan membahasnya lebih dalam saat ini. tingkat. Hal utama yang perlu Anda ingat:

• Tidak semua keuntungan dari koleksi tertentu “di atas kertas” akan berfungsi dalam kenyataan (kami melihatnya menggunakan contoh dari tengah daftar)
• Anda tidak boleh berlebihan dalam memilih koleksi (“ ArrayListselalu lebih cepat, gunakan dan Anda tidak akan salah. LinkedListSudah lama tidak ada yang menggunakannya”).

Meskipun pencipta LinkedListJoshua Bloch mengatakan demikian :) Namun, sudut pandang ini jauh dari 100% benar, dan kami yakin akan hal ini. Dalam contoh kami sebelumnya, LinkedListini bekerja 400 (!) kali lebih cepat. Hal lainnya adalah hanya ada sedikit situasi di mana LinkedListitu akan menjadi pilihan terbaik. Tapi mereka ada, dan pada saat yang tepat LinkedListmereka bisa sangat membantu Anda. Jangan lupa apa yang kita bicarakan di awal kuliah: struktur data yang berbeda paling efektif untuk tugas yang berbeda. Tidak mungkin untuk mengatakan dengan keyakinan 100% struktur data mana yang lebih baik sampai semua kondisi masalahnya diketahui. Nantinya Anda akan mengetahui lebih banyak tentang koleksi-koleksi tersebut, dan akan lebih mudah dalam menentukan pilihan. Namun opsi paling sederhana dan efektif selalu sama: uji keduanya pada data nyata dari program Anda. Kemudian Anda bisa melihat sendiri hasil dari kedua daftar tersebut dan Anda pasti tidak akan salah :)