Ngenalke koleksi LinkedList

1. RiwayatLinkedList

Jawa nduweni kelas koleksi liyane sing diwarisake saka basa C++. Iki minangka LinkedListkelas, sing ngetrapake "dhaptar sing disambung".

Ing njaba, a LinkedListkaton padha karo ArrayList. Kelas LinkedListduwe kabeh cara sing padha karo ArrayListkelas. Ing asas, sampeyan bisa tansah nggunakake LinkedListtinimbang ArrayListlan kabeh bakal bisa.

Dadi kenapa kita butuh kelas dhaptar liyane?

Jawaban iki ana hubungane karo struktur internal kelas LinkedList. Tinimbang array, nggunakake dhaptar sing disambung kaping pindho . Kita bakal nerangake apa sing sethitik mengko.

Struktur internal kelas LinkedListsing beda ndadekake paling cepet kanggo nglebokake unsur ing tengah dhaptar.

Ing Internet, sampeyan kerep bisa nemokake perbandingan lan ArrayListkelas LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Kabeh katon cukup cetha: yen sampeyan kudu nglebokake unsur ing dhaptar asring, gunakake LinkedList; yen arang, banjur nggunakake ArrayList. Nanging kasunyatane rada beda.

2. Ora ana sing nggunakakeLinkedList

Ora ana sing nggunakake LinkedList.

Malah penulis kelas LinkedListbubar tweeted: "Apa ana wong sing bener-bener nggunakake LinkedList? Aku nulis, lan aku ora tau nggunakake."

Dadi apa sing menehi hasil?

Kaping pisanan, kelas ArrayListwiwit bisa nglebokake unsur ing tengah dhaptar kanthi cepet. Nalika nglebokake unsur ing tengah dhaftar, sampeyan kudu ngalih kabeh unsur sawise titik sisipan dening 1 menyang mburi dhaftar. Iki digunakake kanggo njupuk wektu.

Nanging saiki kabeh wis owah. Kabeh unsur Uploaded cedhak siji liyane ing blok memori sing padha, supaya operasi kanggo mindhah unsur dileksanakake dening printah tingkat kurang cepet banget :.System.arraycopy()

Kajaba iku, prosesor saiki duwe cache gedhe sing biasane bisa nahan kabeh array, sing ngidini unsur array bisa dipindhah ing cache tinimbang ing memori. A yuta unsur gampang dipindhah ing milidetik siji.

Kapindho, kelas LinkedListbisa nglebokake unsur kanthi cepet yen sampeyan nglebokake kanthi nggunakake iterator. Yen sampeyan nggunakake iterator menyang liwat LinkedListlan terus-terusan masang unsur anyar (utawa mbusak sing wis ana), operasi super cepet.

Yen sampeyan mung nambah unsur menyang LinkedListobyek ing daur ulang, saben operasi insert cepet diiringi dening alon "njaluk unsur" operasi.

Kasunyatane luwih cedhak karo iki:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Napa entuk unsur saka LinkedListoperasi sing alon?

Sampeyan bisa mangsuli pitakon kasebut sawise ngerti kepiye LinkedListstrukture.

3. Carane LinkedListwis kabentuk

LinkedListnduweni struktur internal sing beda karo ArrayList. Ora duwe array internal kanggo nyimpen unsur. Nanging, nggunakake struktur data sing diarani dhaptar tinta tikel kaping pindho .

Saben unsur saka dhaptar sing disambung kaping pindho nyimpen referensi menyang unsur sadurunge lan unsur sabanjure. Iki kaya garis ing toko, ing ngendi saben wong ngelingi wong sing ngadeg ing ngarep lan uga wong sing ngadeg ing mburi.

Iki minangka dhaptar kaya ing memori:

Sirah lan buntut (sèl kanthi latar mburi abu-abu) minangka variabel firstlan last, sing nyimpen referensi kanggo Nodeobyek.

Ing tengah, sampeyan duwe ranté Nodeobyek (obyek, dudu variabel). Saben wong kasusun saka telung lapangan:

• prev- nyimpen referensi (link) menyang Nodeobyek sadurunge (sel karo latar mburi kuning).
• value— nyimpen Nilai saka unsur iki dhaftar (sel karo latar mburi ijo).
• next- nyimpen referensi (link) menyang obyek sabanjure Node(sel kanthi latar mburi biru)

Obyek kapindho (alamat F24) yaiku jejere ( next) kanggo obyek pisanan lan sadurunge ( prev) kanggo obyek katelu. Kolom kuning obyek katelu ngemot alamat F24 lan kolom biru obyek pisanan ngemot alamat F24.

Panah saka obyek pisanan lan katelu nuding obyek kapindho padha. Dadi bakal luwih bener kanggo nggambar panah kaya iki.

4. Lebokake unsur menyang dhaptar sing disambung

Kanggo nambah wong menyang baris kaya iki, sampeyan mung kudu njaluk ijin saka wong loro ngadeg jejere. Wong pisanan ngelingi wong anyar minangka "wong ing mburiku", lan wong liya ngelingi dheweke minangka "wong ing ngarepku".

Sampeyan mung kudu ngganti referensi saka rong obyek tetanggan:

Kita nambahake item anyar menyang dhaptar kanthi ngganti referensi obyek kapindho lan katelu. Obyek anyar yaiku sabanjure kanggo obyek kapindho lawas lan sadurunge kanggo obyek katelu lawas. Lan, mesthine, obyek anyar dhewe kudu nyimpen referensi sing bener: obyek sadurunge minangka obyek kapindho lawas, lan obyek sabanjure minangka obyek katelu lawas.

Mbusak unsur luwih gampang: Yen kita pengin mbusak, ayo ngomong, obyek kaping 100 saka dhaptar, kita mung kudu ngganti lapangan nextkanggo obyek kaping 99 supaya nuduhake obyek kaping 101, lan ngganti prevlapangan kanggo obyek kaping 101 obyek supaya nuding menyang 99. Mekaten.

Nanging entuk obyek kaping 100 ora gampang.

5. Mbusak unsur saka dhaftar

Kanggo entuk unsur kaping 100 saka dhaptar sing disambung, sampeyan kudu:

Entuk obyek 1st: Sampeyan nindakake iki nggunakake firstvariabel ing LinkedListobyek kasebut. Bidang nextobyek 1 nyimpen referensi kanggo obyek kaping 2. Mangkene carane kita entuk obyek kapindho. Objek kaping 2 nduweni referensi kanggo katelu, lan liya-liyane.

Yen kita kudu njaluk referensi kanggo obyek 100th, kita kudu sequentially pindhah liwat kabeh obyek saka 1 kanggo 100th. Lan yen kita butuh unsur yuta ing dhaptar, kita kudu ngulang luwih saka yuta obyek siji-sijine!

Lan yen obyek iki ditambahake menyang dhaftar ing wektu sing beda-beda, padha bakal dumunung ing macem-macem bagean saka memori lan ora kamungkinan kanggo mungkasi munggah ing cache prosesor ing wektu sing padha. Iki tegese iterasi liwat unsur dhaptar sing disambung ora mung alon, nanging alon banget.

Mekaten ingkang kita tindakaken.

Dadi kenapa kita mulang sampeyan carane alon iki LinkedListbisa digunakake?

Ya, sajrone wawancara kerja, sampeyan bakal ditakoni kepiye LinkedListbedane karoArrayList . temtunipun.