Ipinapakilala ang LinkedList na koleksyon

1. Kasaysayan ngLinkedList

Ang Java ay may isa pang collection class na Java na minana mula sa C++ na wika. Ito ang LinkedListklase, na nagpapatupad ng "naka-link na listahan".

Sa panlabas, ang isang LinkedListay mukhang kapareho ng isang ArrayList. Ang LinkedListklase ay may lahat ng parehong pamamaraan tulad ng ArrayListklase. Sa prinsipyo, maaari mong palaging gumamit ng isang LinkedListsa halip na isang ArrayListat lahat ay gagana.

Kaya bakit kailangan namin ng isa pang klase ng listahan?

Ang sagot ay may kinalaman sa panloob na istraktura ng LinkedListklase. Sa halip na array, gumagamit ito ng dobleng naka-link na listahan . Ipapaliwanag namin kung ano iyon sa ibang pagkakataon.

Ang LinkedListiba't ibang panloob na istraktura ng klase ay ginagawang pinakamabilis sa pagpasok ng mga elemento sa gitna ng listahan.

Sa Internet, madalas kang makakahanap ng mga paghahambing ng ArrayListat LinkedListmga klase:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Ang lahat ay tila sapat na malinaw: kung kailangan mong magpasok ng mga elemento nang madalas sa listahan, gamitin ang LinkedList; kung bihira, gamitin ang ArrayList. Ngunit ang katotohanan ay medyo naiiba.

2. Walang gumagamitLinkedList

Walang gumagamit LinkedList.

Maging ang may-akda ng LinkedListklase kamakailan ay nag-tweet: "May gumagamit ba LinkedListng ? Isinulat ko ito, at hindi ko kailanman ginagamit ito."

Kaya ano ang deal?

Una, ang ArrayListklase ay nagsimulang makapagpasok ng mga elemento sa gitna ng listahan nang napakabilis. Kapag naglalagay ng elemento sa gitna ng listahan, kailangan mong ilipat ang lahat ng elemento pagkatapos ng insertion point ng 1 patungo sa dulo ng listahan. Ito ay dating tumagal ng oras.

Pero ngayon nagbago na ang lahat. Ang lahat ng mga elemento ng isang array ay malapit sa isa't isa sa parehong bloke ng memorya, kaya ang operasyon upang ilipat ang mga elemento ay isinasagawa sa pamamagitan ng isang napakabilis na low-level na command: .System.arraycopy()

Bilang karagdagan, ang mga processor ngayon ay may malaking cache na kadalasang maaaring hawakan ang buong array, na nagpapahintulot sa mga elemento ng array na ilipat sa loob ng cache kaysa sa memorya. Ang isang milyong elemento ay madaling ilipat sa isang millisecond.

Pangalawa, mabilis na maipasok ng klase ang mga elemento kung ilalagay mo ang mga ito gamit ang isang iterator. LinkedListKung gumagamit ka ng isang iterator upang dumaan sa isang LinkedListat patuloy na magpasok ng mga bagong elemento (o mag-alis ng mga umiiral na), ang operasyon ay napakabilis.

Kung nagdaragdag ka lang ng mga elemento sa isang LinkedListbagay sa loob ng isang loop, ang bawat mabilis na operasyon ng pagpasok ay sinamahan ng isang mabagal na "get element" na operasyon.

Ang katotohanan ay mas malapit dito:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Bakit ang pagkuha ng isang elemento mula sa isang LinkedListnapakabagal na operasyon?

Masasagot mo ang tanong na iyan pagkatapos na medyo pamilyar sa kung paano LinkedListnakabalangkas.

3. Paano LinkedListnakabalangkas

LinkedListay may ibang panloob na istraktura kaysa sa ArrayList. Wala itong panloob na hanay para sa pag-iimbak ng mga elemento. Sa halip, gumagamit ito ng istruktura ng data na tinatawag na listahan na may dobleng tinta .

Ang bawat elemento ng isang dobleng naka-link na listahan ay nag-iimbak ng reference sa nakaraang elemento at sa susunod na elemento. Ito ay medyo tulad ng isang linya sa isang tindahan, kung saan naaalala ng bawat tao ang taong nakatayo sa harap nila pati na rin ang taong nakatayo sa likuran nila.

Ganito ang hitsura ng naturang listahan sa memorya:

Ang ulo at buntot (mga cell na may kulay abong background) ay ang firstat lastmga variable, na nag-iimbak ng mga sanggunian sa Nodemga bagay.

Sa gitna, mayroon kang isang hanay ng Nodemga bagay (mga bagay, hindi mga variable). Ang bawat isa sa kanila ay binubuo ng tatlong larangan:

• prev— nag-iimbak ng reference (link) sa nakaraang Nodebagay (mga cell na may dilaw na background).
• value— iniimbak ang halaga ng elementong ito ng listahan (mga cell na may berdeng background).
• next— nag-iimbak ng sanggunian (link) sa susunod na Nodebagay (mga cell na may asul na background)

Ang pangalawang bagay (address F24) ay ang susunod na ( next) para sa unang bagay at ang nauna ( prev) para sa ikatlong bagay. Ang dilaw na patlang ng ikatlong bagay ay naglalaman ng address F24 at ang asul na patlang ng unang bagay ay naglalaman ng address F24.

Ang mga arrow mula sa una at pangatlong bagay ay tumuturo sa parehong pangalawang bagay. Kaya ito ay magiging mas tama upang iguhit ang mga arrow tulad nito.

4. Magpasok ng elemento sa isang naka-link na listahan

Upang magdagdag ng isang tao sa linyang tulad nito, kailangan mo lang kumuha ng pahintulot ng dalawang taong nakatayo sa tabi ng isa't isa. Ang unang tao ay naaalala ang bagong dating bilang "ang taong nasa likod ko", at ang pangalawang tao ay naaalala sila bilang "ang taong nasa harap ko".

Ang kailangan mo lang gawin ay baguhin ang mga sanggunian ng dalawang kalapit na bagay:

Nagdagdag kami ng bagong item sa aming listahan sa pamamagitan ng pagbabago ng mga sanggunian ng pangalawa at pangatlong bagay. Ang bagong bagay ay ang susunod para sa lumang pangalawang bagay at ang nauna para sa lumang pangatlong bagay. At, siyempre, ang bagong bagay mismo ay kailangang mag-imbak ng mga tamang sanggunian: ang dati nitong bagay ay ang lumang pangalawang bagay, at ang susunod na bagay ay ang lumang ikatlong bagay.

Ang pag-alis ng isang elemento ay mas madali: Kung gusto nating tanggalin, sabihin natin, ang ika-100 bagay mula sa listahan, kailangan lang nating baguhin ang field nextpara sa ika-99 na bagay upang tumuro ito sa ika-101 bagay, at baguhin ang prevpatlang para sa ika-101 tumutol upang tumuro ito sa ika-99. Ayan yun.

Ngunit ang pagkuha ng ika-100 bagay ay hindi ganoon kadali.

5. Alisin ang isang elemento mula sa isang listahan

Upang makuha ang ika-100 elemento ng isang naka-link na listahan, kailangan mong:

Kunin ang 1st object: Ginagawa mo ito gamit ang firstvariable sa LinkedListobject. Ang nextfield ng 1st object ay nag-iimbak ng reference sa 2nd object. Iyan ay kung paano namin makuha ang pangalawang bagay. Ang 2nd object ay may reference sa pangatlo, at iba pa.

Kung kailangan nating makakuha ng sanggunian sa ika-100 bagay, kailangan nating sunud-sunod na ilipat ang lahat ng mga bagay mula sa ika-1 hanggang ika-100. At kung kailangan natin ang ika-milyong elemento sa isang listahan, kailangan nating umulit ng higit sa isang milyong bagay nang isa-isa!

At kung ang mga bagay na ito ay idinagdag sa listahan sa iba't ibang oras, sila ay matatagpuan sa iba't ibang bahagi ng memorya at malamang na hindi mapupunta sa cache ng processor sa parehong oras. Nangangahulugan ito na ang pag-ulit sa mga elemento ng isang naka-link na listahan ay hindi lamang mabagal, ngunit napakabagal.

Iyon ang pinag-uusapan natin.

Kaya bakit namin itinuturo sa iyo kung paano LinkedListgumagana ang mabagal na ito?

Buweno, sa mga panayam sa trabaho tatanungin ka kung ano ang LinkedListpagkakaiba saArrayList . Siguradong.