Memperkenalkan koleksi LinkedList

1. SejarahLinkedList

Java memiliki kelas koleksi lain yang diwarisi dari bahasa C++. Ini adalah LinkedListkelas, yang mengimplementasikan "linked list".

Secara lahiriah, a LinkedListtampak sama dengan ArrayList. Kelas LinkedListmemiliki semua metode yang sama dengan ArrayListkelas. Pada prinsipnya, Anda selalu dapat menggunakan LinkedListalih-alih an ArrayListdan semuanya akan berfungsi.

Jadi mengapa kita membutuhkan kelas daftar lain?

Jawabannya ada hubungannya dengan struktur internal kelas LinkedList. Alih-alih array, ia menggunakan daftar tertaut ganda . Kami akan menjelaskan apa itu nanti.

Struktur internal kelas LinkedListyang berbeda membuatnya tercepat dalam memasukkan elemen di tengah daftar.

Di Internet, Anda sering dapat menemukan perbandingan kelas ArrayListdan LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Segalanya tampak cukup jelas: jika Anda perlu sering memasukkan elemen ke dalam daftar, gunakan LinkedList; jika jarang, gunakan ArrayList. Tetapi kenyataannya sedikit berbeda.

2. Tidak ada yang menggunakanLinkedList

Tidak ada yang menggunakan LinkedList.

Bahkan penulis LinkedListkelas tersebut baru-baru ini men-tweet: "Apakah ada yang benar-benar menggunakan LinkedList? Saya menulisnya, dan saya tidak pernah menggunakannya."

Jadi apa masalahnya?

Pertama, kelas ArrayListmulai dapat memasukkan elemen ke tengah daftar dengan sangat cepat. Saat memasukkan elemen di tengah daftar, Anda harus menggeser semua elemen setelah titik penyisipan sebesar 1 ke arah akhir daftar. Ini dulu memakan waktu.

Tapi sekarang semuanya telah berubah. Semua elemen array berdekatan satu sama lain dalam blok memori yang sama, sehingga operasi untuk menggeser elemen dilakukan dengan perintah tingkat rendah yang sangat cepat: .System.arraycopy()

Selain itu, prosesor saat ini memiliki cache besar yang biasanya dapat menampung seluruh larik, yang memungkinkan elemen larik dipindahkan di dalam cache daripada di memori. Satu juta elemen mudah digeser dalam satu milidetik.

Kedua, kelas LinkedListdapat memasukkan elemen dengan cepat jika Anda memasukkannya menggunakan iterator. Jika Anda menggunakan iterator untuk melewati a LinkedListdan terus-menerus memasukkan elemen baru (atau menghapus elemen yang sudah ada), operasinya sangat cepat.

Jika Anda hanya menambahkan elemen ke LinkedListobjek di dalam lingkaran, maka setiap operasi penyisipan cepat disertai dengan operasi "ambil elemen" yang lambat.

Kenyataannya jauh lebih dekat dengan ini:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Mengapa mendapatkan elemen dari LinkedListoperasi yang begitu lambat?

Anda bisa menjawab pertanyaan itu setelah sedikit mengenal bagaimana LinkedListstrukturnya.

3. Bagaimana LinkedListstrukturnya

LinkedListmemiliki struktur internal yang berbeda dari ArrayList. Itu tidak memiliki array internal untuk menyimpan elemen. Sebagai gantinya, ia menggunakan struktur data yang disebut daftar bertinta ganda .

Setiap elemen dari daftar tertaut ganda menyimpan referensi ke elemen sebelumnya dan elemen berikutnya. Ini seperti sebuah barisan di sebuah toko, di mana setiap orang mengingat orang yang berdiri di depan mereka serta orang yang berdiri di belakang mereka.

Seperti inilah tampilan daftar di memori:

Kepala dan ekor (sel dengan latar belakang abu-abu) adalah variabel firstdan last, yang menyimpan referensi ke Nodeobjek.

Di tengah, Anda memiliki rangkaian Nodeobjek (objek, bukan variabel). Masing-masing terdiri dari tiga bidang:

• prev— menyimpan referensi (tautan) ke objek sebelumnya Node(sel dengan latar belakang kuning).
• value— menyimpan nilai elemen daftar ini (sel dengan latar belakang hijau).
• next— menyimpan referensi (tautan) ke objek berikutnya Node(sel dengan latar belakang biru)

Objek kedua (alamat F24) adalah objek berikutnya ( next) untuk objek pertama dan objek sebelumnya ( prev) untuk objek ketiga. Bidang kuning objek ketiga berisi alamat F24 dan bidang biru objek pertama berisi alamat F24.

Panah dari objek pertama dan ketiga menunjuk ke objek kedua yang sama. Jadi akan lebih tepat menggambar panah seperti ini.

4. Masukkan elemen ke daftar tertaut

Untuk menambahkan seseorang ke baris seperti ini, Anda hanya perlu mendapatkan izin dari dua orang yang berdiri bersebelahan. Orang pertama mengingat pendatang baru sebagai "orang di belakang saya", dan orang kedua mengingat mereka sebagai "orang di depan saya".

Yang perlu Anda lakukan hanyalah mengubah referensi dari dua objek yang berdekatan:

Kami menambahkan item baru ke daftar kami dengan mengubah referensi objek kedua dan ketiga. Objek baru adalah yang berikutnya untuk objek kedua yang lama dan yang sebelumnya untuk objek ketiga yang lama. Dan, tentu saja, objek baru itu sendiri perlu menyimpan referensi yang benar: objek sebelumnya adalah objek kedua yang lama, dan objek berikutnya adalah objek ketiga yang lama.

Menghapus elemen bahkan lebih mudah: Jika kita ingin menghapus, katakanlah, objek ke-100 dari daftar, kita hanya perlu mengubah bidang nextuntuk objek ke-99 sehingga menunjuk ke objek ke-101, dan mengubah prevbidang untuk objek ke-101 objek sehingga menunjuk ke 99. Itu dia.

Tetapi mendapatkan objek ke-100 tidaklah mudah.

5. Hapus elemen dari daftar

Untuk mendapatkan elemen ke-100 dari daftar tertaut, Anda perlu:

Dapatkan objek pertama: Anda melakukannya dengan menggunakan firstvariabel di LinkedListobjek. Bidang nextobjek pertama menyimpan referensi ke objek kedua. Begitulah cara kita mendapatkan objek kedua. Objek ke-2 memiliki referensi ke objek ketiga, dan seterusnya.

Jika kita perlu mendapatkan referensi ke objek ke-100, kita perlu menelusuri semua objek secara berurutan dari tanggal 1 hingga ke-100. Dan jika kita membutuhkan elemen sepersejuta dalam daftar, kita perlu mengulangi lebih dari satu juta objek satu per satu!

Dan jika objek ini ditambahkan ke daftar pada waktu yang berbeda, objek tersebut akan ditempatkan di bagian memori yang berbeda dan kemungkinan besar tidak akan berakhir di cache prosesor pada saat yang bersamaan. Ini berarti iterasi pada elemen linked list tidak hanya lambat, tetapi juga sangat lambat.

Itulah yang sedang kita hadapi.

Jadi mengapa kami mengajari Anda cara LinkedListkerja lambat ini?

Nah, saat wawancara kerja Anda akan ditanya apa LinkedListbedanya denganArrayList . Tentu saja.