Daftar Tertaut Java

Hai! Semua pelajaran terbaru telah dikhususkan untuk ArrayList . Struktur data ini sangat nyaman dan berguna. Itu dapat menangani banyak tugas. Tetapi Java memiliki banyak struktur data lainnya. Mengapa? Di atas segalanya, karena rentang tugas sangat besar, dan struktur data yang paling efisien berbeda untuk tugas yang berbeda. Hari ini kita akan menemui sebuah struktur baru: Java LinkedList , sebuah daftar berantai ganda.

Mari kita lihat bagaimana pengaturannya, mengapa disebut tautan ganda, perbedaannya dengan ArrayList . Elemen-elemen dalam Java LinkedList sebenarnya adalah tautan dalam satu rantai. Selain data, setiap elemen menyimpan referensi ke elemen sebelumnya dan selanjutnya. Referensi ini memungkinkan Anda berpindah dari satu elemen ke elemen lainnya. Inilah cara Anda membuatnya:

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

   }
}

Keluaran: [Halo Dunia! Nama saya Earl, saya suka Java, saya tinggal di Kanada] Berikut tampilan daftar kami: Daftar Tertaut - 2

Mari kita lihat cara menambahkan elemen baru. Ini dilakukan dengan menggunakan metode add() .

earlBio.add(str2);

Pada titik di dalam kode, daftar kita terdiri dari satu elemen: String str1 . Mari kita lihat apa yang terjadi selanjutnya pada gambar: Daftar Tertaut - 3

Akibatnya, str2 dan str1 menjadi terhubung melalui tautan berikutnya dan sebelumnya yang disimpan dalam node daftar ini: LinkedList - 4

Sekarang Anda harus memahami gagasan utama dari daftar bertaut ganda. Rantai tautan inilah yang membuat elemen LinkedList menjadi satu daftar. Tidak seperti ArrayList , LinkedList tidak memiliki larik atau apa pun yang mirip larik di dalamnya. Pekerjaan apa pun (yah, sebagian besar) dengan ArrayList bermuara pada bekerja dengan array internal. Pekerjaan apa pun dengan Java LinkedListbermuara pada mengubah link. Ini dapat dilihat dengan sangat jelas dengan menambahkan elemen di tengah daftar:

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, metode add() yang kelebihan muatan memungkinkan Anda menentukan indeks khusus untuk item baru. Dalam hal ini, kami ingin menambahkan String str2 antara str1 dan str3 . Inilah yang akan terjadi secara internal: LinkedList - 5

Setelah mengubah tautan internal, str2 telah berhasil ditambahkan ke daftar: LinkedList - 6

Sekarang ketiga elemen telah terhubung. Anda dapat berpindah melalui tautan berikutnya dari elemen pertama pada rantai ke yang terakhir dan kembali lagi. Jadi, kami cukup nyaman dengan penyisipan, tetapi bagaimana dengan menghapus elemen? Prinsipnya persis sama. Kami baru saja memperbarui tautan di dua elemen "ke kiri dan kanan" dari elemen yang dihapus:

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 terjadi jika kita menghapus item dengan indeks 1 (ada di tengah daftar): LinkedList - 7

Setelah memperbarui tautan, kita mendapatkan hasil yang diinginkan: Daftar Tertaut - 8

Tidak seperti operasi penghapusan di ArrayList , di sini tidak perlu menggeser elemen array atau melakukan apa pun dari jenisnya. Kami baru saja memperbarui tautan untuk str1 dan str3 . Mereka sekarang saling menunjuk, dan str2 telah " keluar " dari rantai tautan dan tidak lagi menjadi bagian dari daftar.

Tinjauan metode

LinkedList memiliki banyak kesamaan metode dengan ArrayList . Misalnya, kedua kelas memiliki metode seperti add() , remove() , indexOf() , clear() , contains() (menunjukkan apakah suatu item ada dalam daftar), set() (menggantikan elemen yang ada), dan ukuran() . Meskipun banyak dari mereka bekerja secara berbeda secara internal (seperti yang kami temukan dengan add() dan remove() ), hasil akhirnya sama. Namun, LinkedList memiliki metode terpisah untuk bekerja dengan awal dan akhir daftar, yang tidak dimiliki ArrayList :

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

Keluaran: [Mobil{model='Ferrari 360 Spider'}, Mobil{model='Bugatti Veyron'}, Mobil{model='Lamborghini Diablo'}] [Mobil{model='Ford Mondeo'}, Mobil{model=' Ferrari 360 Spider'}, Mobil{model='Bugatti Veyron'}, Mobil{model='Lamborghini Diablo'}, Mobil{model='Fiat Ducato'}] Kami berakhir dengan "Ford" di bagian atas daftar , dan "Fiat" di akhir.

peekFirst() , peekLast() : Metode mengembalikan elemen pertama/terakhir dalam daftar. Mereka mengembalikan nol jika daftar 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());
}

Keluaran: Mobil{model='Ferrari 360 Spider'} Mobil{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Metode ini mengembalikan elemen pertama/terakhir dalam daftar dan menghapusnya dari daftar. Mereka mengembalikan nol jika daftar 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);
}

Keluaran: Mobil{model='Ferrari 360 Spider'} Mobil{model='Lamborghini Diablo'} Apa yang tersisa di daftar? [Mobil{model='Bugatti Veyron'}]

toArray() : Metode ini mengembalikan larik yang berisi item 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));
}

Keluaran: [Mobil{model='Ferrari 360 Spider'}, Mobil{model='Bugatti Veyron'}, Mobil{model='Lamborghini Diablo'}] Sekarang kita tahu cara kerja LinkedList dan bagaimana organisasinya berbeda dari ArrayList . Apa keuntungan menggunakan LinkedList ? Yang terpenting, kami mendapat manfaat saat bekerja di tengah daftar. Operasi penyisipan dan penghapusan di tengah LinkedList jauh lebih sederhana daripada di ArrayList . Kami hanya memperbarui tautan elemen tetangga, dan elemen yang tidak diinginkan "keluar" dari rantai tautan. Tapi dalam ArrayList , kita harus

periksa apakah ada cukup ruang (saat memasukkan)
jika tidak, maka kami membuat array baru dan menyalin data di sana (saat memasukkan)
kami menghapus/memasukkan elemen, dan memindahkan semua elemen lainnya ke kanan/kiri (tergantung pada jenis operasi). Dan kerumitan proses ini sangat bergantung pada ukuran daftar. Menyalin/memindahkan 10 elemen adalah satu hal, dan melakukan hal yang sama dengan sejuta elemen adalah hal lain.

Dengan kata lain, jika operasi penyisipan/penghapusan di tengah daftar adalah yang paling umum dalam program Anda, LinkedList seharusnya 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 taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Keluaran: Waktu yang diambil oleh LinkedList (dalam milidetik) = 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));
   }
}

Keluaran: Waktu yang diambil oleh ArrayList (dalam milidetik) = 181 Itu tidak terduga! Kami melakukan operasi di mana LinkedList seharusnya jauh lebih efisien: memasukkan 100 item di tengah daftar. Dan daftar kami sangat besar: 5.000.000 elemen. ArrayList harus menggeser beberapa juta item dengan setiap penyisipan! Bagaimana cara menang? Pertama, waktu yang dibutuhkan ArrayList untuk mengakses elemen adalah tetap (konstan). Ketika Anda menulis

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

maka ArrayList [2_000_000] adalah alamat memori khusus (setelah semua, daftar tersebut memiliki larik internal). Tapi, LinkedList tidak memiliki array. Itu akan mencari nomor elemen 2_000_000 di sepanjang rantai tautan. Untuk LinkedList, ini bukan alamat memori, tetapi tautan 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, selama setiap penyisipan (penghapusan) di tengah daftar , ArrayList sudah mengetahui alamat memori yang tepat untuk diakses, tetapi LinkedList masih perlu "sampai ke sana". Kedua, ada struktur ArrayListdiri. Fungsi internal khusus ( System.arrayCopy() ) memperluas array internal, dan menyalin serta menggeser semua elemen. Ini sangat cepat, karena dioptimalkan untuk pekerjaan khusus ini. Tetapi ketika Anda tidak harus "mendapatkan" indeks tertentu, LinkedList adalah pemenangnya. Misalkan kita memasukkan di awal daftar. Mari coba 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());
       }
   }

}

Hasil: Hasil dalam milidetik: 43448 Hasil dalam milidetik: 107 Sekarang kita mendapatkan hasil yang sama sekali berbeda! ArrayList menghabiskan lebih dari 43 detik untuk memasukkan sejuta item di bagian depan daftar, sementara LinkedList berhasil melakukannya dalam 0,1 detik! LinkedList diuntungkan di sini, karena tidak harus melewati rantai tautan ke tengah daftar setiap saat. Ini segera menemukan indeks yang dibutuhkan di awal daftar, sehingga algoritma yang berbeda sudah menjadi keuntungan. :) Faktanya, diskusi " ArrayList versus LinkedList " sangat luas, dan kami tidak akan menyelami lebih dalam di level saat ini. Hal utama yang perlu Anda ingat adalah ini:

Tidak semua keuntungan teoretis dari koleksi tertentu selalu berfungsi dalam kenyataan (kami melihat ini dengan contoh yang melibatkan bagian tengah daftar)
Jangan mengambil posisi ekstrim ketika memilih koleksi (" ArrayList selalu lebih cepat. Gunakan itu dan Anda tidak akan salah. Tidak ada yang menggunakan LinkedList untuk waktu yang lama").

Meskipun penulis LinkedList , Joshua Bloch, mengatakan demikian. :) Tetap saja, perspektif ini jauh dari 100% benar, dan kami telah meyakinkan diri sendiri akan hal ini. Dalam contoh kami sebelumnya, LinkedList 400 (!) kali lebih cepat. Hal lainnya adalah hanya ada sedikit situasi di mana LinkedList adalah pilihan terbaik. Tapi mereka memang ada, dan pada saat yang tepat LinkedListdapat membalas Anda dengan mahal. Jangan lupa apa yang kami katakan di awal pelajaran: struktur data yang paling efisien berbeda untuk tugas yang berbeda. Tidak mungkin untuk 100% yakin struktur data mana yang terbaik sampai Anda mengetahui semua kondisi tugas Anda. Anda akan mengetahui lebih banyak tentang koleksi ini nanti, yang akan mempermudah pilihan. Tetapi opsi paling sederhana dan paling efektif selalu sama: coba keduanya pada data aktual yang digunakan dalam program Anda. Kemudian Anda akan dapat melihat sendiri bagaimana kinerja kedua jenis daftar tersebut dan Anda pasti tidak akan salah. :) Untuk memperkuat apa yang Anda pelajari, kami sarankan Anda menonton video pelajaran dari Kursus Java kami

Lebih banyak bacaan:
Struktur Data LinkedList Java