Maak kennis met de LinkedList-collectie

1. Geschiedenis vanLinkedList

Java heeft een andere verzamelklasse die Java heeft geërfd van de C++-taal. Dit is de LinkedListklasse die een "gekoppelde lijst" implementeert.

Uiterlijk LinkedListlijkt een hetzelfde te zijn als een ArrayList. De LinkedListklasse heeft allemaal dezelfde methoden als de ArrayListklasse. In principe kun je altijd een gebruiken LinkedListin plaats van een ArrayListen dan werkt alles.

Dus waarom hebben we nog een lijstklasse nodig?

Het antwoord heeft alles te maken met de interne structuur van de LinkedListklas. In plaats van een array gebruikt het een dubbel gekoppelde lijst . Wat dat is, leggen we later uit.

De LinkedListverschillende interne structuur van de klasse maakt het het snelst in het invoegen van elementen in het midden van de lijst.

Op internet kun je vaak vergelijkingen vinden van de klassen ArrayListen LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Alles lijkt duidelijk genoeg: als je vaak elementen in de lijst moet invoegen, gebruik dan LinkedList; indien zelden, gebruik dan ArrayList. Maar de realiteit is een beetje anders.

2. Niemand gebruiktLinkedList

Niemand gebruikt LinkedList.

Zelfs de auteur van de LinkedListklas tweette onlangs: "Gebruikt iemand het eigenlijk LinkedList? Ik heb het geschreven en ik gebruik het nooit."

Dus wat is de deal?

Ten eerste begon de klas heel snel elementen in het midden van de lijst in te voegen. ArrayListWanneer u een element in het midden van de lijst invoegt, moet u alle elementen na het invoegpunt met 1 naar het einde van de lijst verschuiven. Vroeger kostte dit tijd.

Maar nu is alles veranderd. Alle elementen van een array bevinden zich dicht bij elkaar in hetzelfde geheugenblok, dus de bewerking om de elementen te verschuiven wordt uitgevoerd door een zeer snel commando op laag niveau: .System.arraycopy()

Bovendien hebben de huidige processors een grote cache die meestal de hele array kan bevatten, waardoor de array-elementen in de cache kunnen worden verplaatst in plaats van in het geheugen. Een miljoen elementen worden gemakkelijk verschoven in een enkele milliseconde.

Ten tweede kan de LinkedListklasse snel elementen invoegen als je ze invoegt met een iterator. Als je een iterator gebruikt om door a te gaan LinkedListen constant nieuwe elementen invoegt (of bestaande verwijdert), is de operatie supersnel.

Als u eenvoudigweg elementen toevoegt aan een LinkedListobject binnen een lus, gaat elke snelle invoegbewerking gepaard met een langzame "get element"-bewerking.

De realiteit komt hier veel dichter bij:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Waarom is het verkrijgen van een element uit zo'n LinkedListtrage operatie?

U kunt die vraag beantwoorden nadat u een beetje vertrouwd bent geraakt met hoe LinkedListhet is gestructureerd.

3. Hoe LinkedListis gestructureerd

LinkedListheeft een andere interne structuur dan ArrayList. Het heeft geen interne array voor het opslaan van elementen. In plaats daarvan gebruikt het een gegevensstructuur die een dubbel geïnkte lijst wordt genoemd .

Elk element van een dubbel gelinkte lijst slaat een verwijzing op naar het vorige element en het volgende element. Dit lijkt een beetje op een rij in een winkel, waar elke persoon zich zowel de persoon die voor hem staat als de persoon die achter hem staat herinnert.

Zo ziet zo'n lijst er in het geheugen uit:

De kop en staart (cellen met een grijze achtergrond) zijn de firsten lastvariabelen, die verwijzingen naar Nodeobjecten opslaan.

In het midden heb je een keten van Nodeobjecten (objecten, geen variabelen). Elk van hen bestaat uit drie velden:

• prev— slaat een verwijzing (link) op naar het vorige Nodeobject (cellen met een gele achtergrond).
• value— slaat de waarde op van dit element van de lijst (cellen met een groene achtergrond).
• next— slaat een verwijzing (link) op naar het volgende Nodeobject (cellen met een blauwe achtergrond)

Het tweede object (adres F24) is het volgende ( next) voor het eerste object en het vorige ( prev) voor het derde object. Het gele veld van het derde object bevat het adres F24 en het blauwe veld van het eerste object bevat het adres F24.

De pijlen van het eerste en derde object wijzen naar hetzelfde tweede object. Het zou dus juister zijn om de pijlen zo te tekenen.

4. Voeg een element toe aan een gekoppelde lijst

Om iemand op deze manier aan de lijn toe te voegen, heb je alleen toestemming nodig van twee mensen die naast elkaar staan. De eerste persoon herinnert zich de nieuwkomer als "de persoon achter mij", en de tweede persoon herinnert zich hen als "de persoon voor mij".

Het enige dat u hoeft te doen, is de referenties van de twee aangrenzende objecten wijzigen:

We hebben een nieuw item aan onze lijst toegevoegd door de referenties van het tweede en derde object te wijzigen. Het nieuwe object is het volgende voor het oude tweede object en het vorige voor het oude derde object. En natuurlijk moet het nieuwe object zelf de juiste referenties opslaan: het vorige object is het oude tweede object en het volgende object is het oude derde object.

Het verwijderen van een element is nog eenvoudiger: als we bijvoorbeeld het 100e object uit de lijst willen verwijderen, hoeven we alleen het veld voor het 99e object te wijzigen nextzodat het naar het 101e object verwijst, en het prevveld voor het 101e object te wijzigen object zodat het naar de 99e wijst. Dat is het.

Maar het 100ste object krijgen is niet zo eenvoudig.

5. Verwijder een element uit een lijst

Om het 100ste element van een gelinkte lijst te krijgen, moet u:

Haal het 1e object op: Dit doe je met behulp van de firstvariabele in het LinkedListobject. Het nextveld van het 1e object bevat een verwijzing naar het 2e object. Zo krijgen we het tweede object. Het 2e object heeft een verwijzing naar het derde, enzovoort.

Als we een verwijzing naar het 100e object nodig hebben, moeten we achtereenvolgens door alle objecten van het 1e tot het 100e gaan. En als we het miljoenste element in een lijst nodig hebben, moeten we meer dan een miljoen objecten achter elkaar herhalen!

En als deze objecten op verschillende tijdstippen aan de lijst zijn toegevoegd, bevinden ze zich in verschillende delen van het geheugen en zullen ze waarschijnlijk niet tegelijkertijd in de cache van de processor terechtkomen. Dit betekent dat het herhalen van de elementen van een gelinkte lijst niet alleen traag is, maar ook erg traag.

Dat is waar we mee te maken hebben.

Dus waarom leren we je hoe deze slow LinkedListwerkt?

Welnu, tijdens sollicitatiegesprekken wordt u gevraagd hoe LinkedListverschilt vanArrayList . Zeker.