Memperkenalkan koleksi LinkedList

1. SejarahLinkedList

Java mempunyai satu lagi kelas koleksi Java yang diwarisi daripada bahasa C++. Ini ialah LinkedListkelas, yang melaksanakan "senarai terpaut".

Secara luaran, a LinkedListnampaknya sama dengan ArrayList. Kelas LinkedListmempunyai semua kaedah yang sama seperti ArrayListkelas. Pada dasarnya, anda sentiasa boleh menggunakan a LinkedListdan bukannya an ArrayListdan semuanya akan berfungsi.

Jadi mengapa kita memerlukan kelas senarai lain?

Jawapannya ada kaitan dengan struktur dalaman kelas LinkedList. Daripada tatasusunan, ia menggunakan senarai terpaut dua kali . Kami akan menerangkan apa itu sedikit kemudian.

Struktur LinkedListdalaman kelas yang berbeza menjadikannya paling pantas untuk memasukkan elemen di tengah senarai.

Di Internet, anda selalunya boleh mencari perbandingan dan ArrayListkelas LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Semuanya kelihatan cukup jelas: jika anda perlu memasukkan elemen ke dalam senarai dengan kerap, gunakan LinkedList; jika jarang, gunakan ArrayList. Tetapi realitinya sedikit berbeza.

2. Tiada siapa yang menggunakanLinkedList

Tiada siapa yang menggunakan LinkedList.

Malah pengarang LinkedListkelas itu baru-baru ini menulis tweet: "Adakah sesiapa yang benar-benar menggunakan LinkedList? Saya menulisnya, dan saya tidak pernah menggunakannya."

Jadi apa urusannya?

Pertama, kelas ArrayListmula dapat memasukkan elemen ke tengah senarai dengan cepat. Apabila memasukkan elemen di tengah-tengah senarai, anda perlu mengalihkan semua elemen selepas titik sisipan sebanyak 1 ke arah penghujung senarai. Ini pernah mengambil masa.

Tetapi kini semuanya telah berubah. Semua elemen tatasusunan berada berdekatan antara satu sama lain dalam blok memori yang sama, jadi operasi untuk mengalihkan elemen dilakukan oleh perintah peringkat rendah yang sangat pantas: .System.arraycopy()

Di samping itu, pemproses hari ini mempunyai cache besar yang biasanya boleh memuatkan keseluruhan tatasusunan, yang membolehkan elemen tatasusunan dialihkan di dalam cache dan bukannya dalam ingatan. Sejuta elemen mudah dialihkan dalam satu milisaat.

Kedua, kelas LinkedListboleh memasukkan elemen dengan cepat jika anda memasukkannya menggunakan iterator. Jika anda menggunakan iterator untuk melalui LinkedListdan sentiasa memasukkan elemen baharu (atau mengalih keluar yang sedia ada), operasinya sangat pantas.

Jika anda hanya menambah elemen pada LinkedListobjek di dalam gelung, maka setiap operasi sisipan pantas disertakan dengan operasi "dapatkan elemen" yang perlahan.

Realitinya lebih dekat dengan ini:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Mengapa mendapatkan elemen daripada LinkedListoperasi yang begitu perlahan?

Anda boleh menjawab soalan itu selepas membiasakan diri dengan cara LinkedListberstruktur.

3. Bagaimana LinkedListtersusun

LinkedListmempunyai struktur dalaman yang berbeza daripada ArrayList. Ia tidak mempunyai tatasusunan dalaman untuk menyimpan elemen. Sebaliknya, ia menggunakan struktur data yang dipanggil senarai berdakwat berganda .

Setiap elemen senarai terpaut berganda menyimpan rujukan kepada elemen sebelumnya dan elemen seterusnya. Ini agak seperti barisan di kedai, di mana setiap orang mengingati orang yang berdiri di hadapan mereka serta orang yang berdiri di belakang mereka.

Inilah rupa senarai sedemikian dalam ingatan:

Kepala dan ekor (sel dengan latar belakang kelabu) ialah firstdan lastpembolehubah, yang menyimpan rujukan kepada Nodeobjek.

Di tengah, anda mempunyai rantaian Nodeobjek (objek, bukan pembolehubah). Setiap daripada mereka terdiri daripada tiga bidang:

• prev— menyimpan rujukan (pautan) ke objek sebelumnya Node(sel dengan latar belakang kuning).
• value— menyimpan nilai elemen senarai ini (sel dengan latar belakang hijau).
• next— menyimpan rujukan (pautan) ke objek seterusnya Node(sel dengan latar belakang biru)

Objek kedua (alamat F24) ialah seterusnya ( next) untuk objek pertama dan sebelumnya ( prev) untuk objek ketiga. Medan kuning objek ketiga mengandungi alamat F24 dan medan biru objek pertama mengandungi alamat F24.

Anak panah dari objek pertama dan ketiga menghala ke objek kedua yang sama. Jadi lebih tepat untuk melukis anak panah seperti ini.

4. Masukkan elemen ke senarai terpaut

Untuk menambahkan seseorang ke barisan seperti ini, anda hanya perlu mendapatkan kebenaran dua orang berdiri bersebelahan. Orang pertama mengingati pendatang baru sebagai "orang di belakang saya", dan orang kedua mengingati mereka sebagai "orang di hadapan saya".

Apa yang anda perlu lakukan ialah menukar rujukan dua objek bersebelahan:

Kami menambah item baharu pada senarai kami dengan menukar rujukan objek kedua dan ketiga. Objek baru ialah yang seterusnya untuk objek kedua yang lama dan yang sebelumnya untuk objek ketiga yang lama. Dan, sudah tentu, objek baharu itu sendiri perlu menyimpan rujukan yang betul: objek sebelumnya ialah objek kedua lama, dan objek seterusnya ialah objek ketiga lama.

Mengalih keluar elemen adalah lebih mudah: Jika kita ingin mengalih keluar, katakan, objek ke-100 daripada senarai, kita hanya perlu menukar medan nextuntuk objek ke-99 supaya ia menunjuk ke objek ke-101, dan menukar medan prevuntuk objek ke-101 objek supaya ia menunjuk ke 99. Itu sahaja.

Tetapi untuk mendapatkan objek ke-100 tidak begitu mudah.

5. Alih keluar elemen daripada senarai

Untuk mendapatkan elemen ke-100 senarai terpaut, anda perlu:

Dapatkan objek pertama: Anda melakukan ini menggunakan pembolehubah firstdalam LinkedListobjek. Medan nextobjek pertama menyimpan rujukan kepada objek ke-2. Begitulah cara kita mendapatkan objek kedua. Objek ke-2 mempunyai rujukan kepada yang ketiga, dan seterusnya.

Jika kita perlu mendapatkan rujukan kepada objek ke-100, kita perlu bergerak secara berurutan melalui semua objek dari yang pertama hingga ke-100. Dan jika kita memerlukan elemen kejuta dalam senarai, kita perlu mengulangi lebih sejuta objek satu demi satu!

Dan jika objek ini ditambahkan pada senarai pada masa yang berbeza, ia akan ditempatkan di bahagian memori yang berbeza dan tidak mungkin berada dalam cache pemproses pada masa yang sama. Ini bermakna bahawa mengulangi elemen senarai terpaut bukan sahaja perlahan, tetapi sangat perlahan.

Itu yang kita hadapi.

Jadi mengapa kami mengajar anda cara perlahan ini LinkedListberfungsi?

Nah, semasa temu duga kerja anda akan ditanya bagaimana LinkedListperbezaannya denganArrayList . Pasti.