Vă prezentăm colecția LinkedList

1. IstoriaLinkedList

Java are o altă clasă de colecție Java moștenită din limbajul C++. Aceasta este LinkedListclasa, care implementează o „listă legată”.

În exterior, a LinkedListpare să fie la fel cu un ArrayList. Clasa LinkedListare toate aceleași metode ca și ArrayListclasa. În principiu, puteți folosi întotdeauna a LinkedListîn loc de a ArrayListși totul va funcționa.

Deci, de ce avem nevoie de o altă clasă de listă?

Răspunsul are totul de-a face cu structura internă a LinkedListclasei. În loc de o matrice, folosește o listă dublu legată . Vom explica ce este asta puțin mai târziu.

Structura internă diferită a clasei LinkedListo face cel mai rapid la inserarea elementelor în mijlocul listei.

Pe Internet, puteți găsi adesea comparații ale claselor ArrayListși LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Totul pare suficient de clar: dacă trebuie să inserați des elemente în listă, utilizați LinkedList; dacă este rar, atunci utilizați ArrayList. Dar realitatea este puțin diferită.

2. Nimeni nu foloseșteLinkedList

Nimeni nu folosește LinkedList.

Chiar și autorul clasei LinkedLista postat recent pe Twitter: „Folosește cineva cu adevărat LinkedList? L-am scris și nu îl folosesc niciodată”.

Deci care e treaba?

În primul rând, clasa ArrayLista început să poată introduce foarte repede elemente în mijlocul listei. Când inserați un element în mijlocul listei, trebuie să mutați toate elementele după punctul de inserare cu 1 spre sfârșitul listei. Asta obișnuia să ia timp.

Dar acum totul s-a schimbat. Toate elementele unui tablou sunt unul lângă celălalt în același bloc de memorie, astfel încât operația de deplasare a elementelor este efectuată printr-o comandă foarte rapidă de nivel scăzut: .System.arraycopy()

În plus, procesoarele de astăzi au un cache mare care poate ține de obicei întreaga matrice, ceea ce permite ca elementele matricei să fie mutate în interiorul cache-ului, mai degrabă decât în ​​memorie. Un milion de elemente sunt ușor deplasate într-o singură milisecundă.

În al doilea rând, clasa LinkedListpoate insera elemente rapid dacă le inserați folosind un iterator. Dacă folosiți un iterator pentru a parcurge un LinkedListși a introduce constant elemente noi (sau le eliminați pe cele existente), operația este super rapidă.

Dacă pur și simplu adăugați elemente la un LinkedListobiect în interiorul unei bucle, atunci fiecare operație de inserare rapidă este însoțită de o operație lentă de „obținere a elementului”.

Realitatea este mult mai aproape de asta:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

De ce obținerea unui element dintr-o LinkedListoperațiune atât de lentă?

Puteți răspunde la această întrebare după ce vă familiarizați puțin cu modul în care LinkedListeste structurat.

3. Cum LinkedListeste structurat

LinkedListare o structură internă diferită de ArrayList. Nu are o matrice internă pentru stocarea elementelor. În schimb, folosește o structură de date numită listă dublu cu cerneală .

Fiecare element dintr-o listă dublu legată stochează o referință la elementul anterior și următorul element. Este oarecum ca o linie la un magazin, în care fiecare persoană își amintește de persoana care stă în fața ei, precum și de persoana care stă în spatele ei.

Iată cum arată o astfel de listă în memorie:

Capul și coada (celule cu fundal gri) sunt variabilele firstși last, care stochează referințe la Nodeobiecte.

În mijloc, aveți un lanț de Nodeobiecte (obiecte, nu variabile). Fiecare dintre ele constă din trei câmpuri:

• prev— stochează o referință (link) la Nodeobiectul anterior (celule cu fundal galben).
• value— stochează valoarea acestui element din listă (celule cu fundal verde).
• next— stochează o referință (link) la următorul Nodeobiect (celule cu fundal albastru)

Al doilea obiect (adresa F24) este următorul ( next) pentru primul obiect și precedentul ( prev) pentru al treilea obiect. Câmpul galben al celui de-al treilea obiect conține adresa F24, iar câmpul albastru al primului obiect conține adresa F24.

Săgețile de la primul și al treilea obiect indică același al doilea obiect. Deci ar fi mai corect să desenezi săgețile astfel.

4. Inserați un element într-o listă legată

Pentru a adăuga pe cineva la rândul acesta, trebuie doar să obțineți permisiunea a două persoane care stau una lângă alta. Prima persoană își amintește de nou venit ca fiind „persoana din spatele meu”, iar a doua persoană își amintește de ei ca „persoana din fața mea”.

Tot ce trebuie să faceți este să schimbați referințele celor două obiecte învecinate:

Am adăugat un nou element la lista noastră prin modificarea referințelor celui de-al doilea și al treilea obiect. Noul obiect este următorul pentru al doilea obiect vechi și anterior pentru al treilea obiect vechi. Și, desigur, noul obiect în sine trebuie să stocheze referințele corecte: obiectul său anterior este vechiul al doilea obiect, iar următorul său obiect este vechiul al treilea obiect.

Eliminarea unui element este și mai ușoară: dacă vrem să eliminăm, să spunem, al 100-lea obiect din listă, trebuie doar să schimbăm câmpul nextpentru al 99-lea obiect, astfel încât să indice cel de-al 101-lea obiect și să schimbăm câmpul prevpentru al 101-lea. obiect astfel încât să indice al 99-lea. Asta este.

Dar obținerea celui de-al 100-lea obiect nu este atât de ușoară.

5. Eliminați un element dintr-o listă

Pentru a obține al 100-lea element al unei liste conectate, trebuie să:

Obțineți primul obiect: faceți acest lucru folosind firstvariabila din LinkedListobiect. Câmpul nextprimului obiect stochează o referință la al doilea obiect. Așa obținem al doilea obiect. Al 2-lea obiect are o referință la al treilea și așa mai departe.

Dacă trebuie să obținem o referință la al 100-lea obiect, trebuie să ne deplasăm secvențial prin toate obiectele de la primul la al 100-lea. Și dacă avem nevoie de milionul de element dintr-o listă, trebuie să repetăm ​​peste un milion de obiecte unul după altul!

Și dacă aceste obiecte au fost adăugate în listă în momente diferite, ele vor fi localizate în diferite părți ale memoriei și este puțin probabil să ajungă în memoria cache a procesorului în același timp. Aceasta înseamnă că repetarea elementelor unei liste legate nu este doar lentă, ci și foarte lentă.

Cu asta avem de-a face.

Deci, de ce vă învățăm cum LinkedListfuncționează acest lent?

Ei bine, în timpul interviurilor de angajare veți fi întrebat cu ce LinkedListdiferă deArrayList . Categoric.