Vi presenterar LinkedList-samlingen

1. Historia omLinkedList

Java har en annan samlingsklass Java ärvt från C++-språket. Det här är LinkedListklassen som implementerar en "länkad lista".

Till det yttre LinkedListverkar a vara detsamma som ett ArrayList. Klassen LinkedListhar alla samma metoder som ArrayListklassen. I princip kan du alltid använda en LinkedLististället för en ArrayListoch allt kommer att fungera.

Så varför behöver vi en annan listklass?

Svaret har allt att göra med klassens interna struktur LinkedList. Istället för en array använder den en dubbellänkad lista . Vi kommer att förklara vad det är lite senare.

Klassens LinkedListolika interna struktur gör den snabbast på att infoga element i mitten av listan.

På Internet kan du ofta hitta jämförelser av klasserna ArrayListoch LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Allt verkar tydligt nog: om du behöver infoga element i listan ofta, använd LinkedList; om sällan, använd ArrayList. Men verkligheten är lite annorlunda.

2. Ingen använderLinkedList

Ingen använder LinkedList.

Till och med klassens författare LinkedListtwittrade nyligen: "Använder någon faktiskt LinkedList? Jag skrev det, och jag använder det aldrig."

Så vad är affären?

Först började klassen ArrayListmycket snabbt kunna infoga element i mitten av listan. När du infogar ett element i mitten av listan måste du flytta alla element efter insättningspunkten med 1 mot slutet av listan. Detta brukade ta tid.

Men nu har allt förändrats. Alla element i en array är nära varandra i samma minnesblock, så operationen för att flytta elementen utförs av ett mycket snabbt lågnivåkommando: .System.arraycopy()

Dessutom har dagens processorer en stor cache som vanligtvis rymmer hela arrayen, vilket gör att arrayelementen kan flyttas inuti cachen snarare än i minnet. En miljon element skiftas lätt på en enda millisekund.

För det andra kan klassen LinkedListinfoga element snabbt om du infogar dem med en iterator. Om du använder en iterator för att gå igenom en LinkedListoch hela tiden infoga nya element (eller ta bort befintliga) går operationen supersnabb.

Om du helt enkelt lägger till element till ett LinkedListobjekt inuti en loop, så åtföljs varje snabb infogningsoperation av en långsam "get element"-operation.

Verkligheten är mycket närmare detta:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

LinkedListVarför är det så långsamt att få ett element från en operation?

Du kan svara på den frågan efter att ha bekantat dig lite med hur det LinkedListär uppbyggt.

3. Hur LinkedListär uppbyggt

LinkedListhar en annan intern struktur än ArrayList. Den har ingen intern array för att lagra element. Istället använder den en datastruktur som kallas en dubbelfärgad lista .

Varje element i en dubbellänkad lista lagrar en referens till föregående element och nästa element. Detta är ungefär som en rad i en butik, där varje person kommer ihåg personen som står framför dem såväl som personen som står bakom dem.

Så här ser en sådan lista ut i minnet:

Huvudet och svansen (celler med grå bakgrund) är variablerna firstoch lastsom lagrar referenser till Nodeobjekt.

I mitten har du en kedja av Nodeobjekt (objekt, inte variabler). Var och en av dem består av tre fält:

• prev— lagrar en referens (länk) till föregående Nodeobjekt (celler med gul bakgrund).
• value— lagrar värdet för detta element i listan (celler med grön bakgrund).
• next— lagrar en referens (länk) till nästa Nodeobjekt (celler med blå bakgrund)

Det andra objektet (adress F24) är nästa ( next) för det första objektet och det föregående ( prev) för det tredje objektet. Det gula fältet för det tredje objektet innehåller adressen F24 och det blå fältet för det första objektet innehåller adressen F24.

Pilarna från det första och tredje objektet pekar på samma andra objekt. Så det vore mer korrekt att rita pilarna så här.

4. Infoga ett element i en länkad lista

För att lägga till någon i rad som denna behöver du bara få tillstånd från två personer som står bredvid varandra. Den första personen minns nykomlingen som "personen bakom mig", och den andra personen minns dem som "personen framför mig".

Allt du behöver göra är att ändra referenserna för de två angränsande objekten:

Vi lade till ett nytt objekt till vår lista genom att ändra referenserna för det andra och tredje objektet. Det nya objektet är nästa för det gamla andra objektet och det föregående för det gamla tredje objektet. Och, naturligtvis, måste det nya objektet självt lagra de korrekta referenserna: dess tidigare objekt är det gamla andra objektet, och dess nästa objekt är det gamla tredje objektet.

Att ta bort ett element är ännu enklare: Om vi ​​vill ta bort, låt oss säga, det 100:e objektet från listan, behöver vi bara ändra fältet nextför det 99:e objektet så att det pekar på det 101:a objektet och ändra fältet prevför det 101:a objektet objekt så att det pekar mot 99:an. Det är allt.

Men att få det 100:e objektet är inte så lätt.

5. Ta bort ett element från en lista

För att få det 100:e elementet i en länkad lista måste du:

Hämta det 1:a objektet: Du gör detta med firstvariabeln i LinkedListobjektet. Fältet nextför det 1:a objektet lagrar en referens till det 2:a objektet. Det är så vi får det andra objektet. Det andra objektet har en referens till det tredje, och så vidare.

Om vi ​​behöver få en referens till det 100:e objektet måste vi sekventiellt flytta igenom alla objekt från det 1:a till det 100:e. Och om vi behöver det miljonte elementet i en lista måste vi iterera över en miljon objekt efter varandra!

Och om dessa objekt lades till i listan vid olika tidpunkter, kommer de att finnas i olika delar av minnet och kommer sannolikt inte att hamna i processorns cache samtidigt. Det betyder att det att iterera över elementen i en länkad lista inte bara är långsamt, utan väldigt långsamt.

Det är vad vi har att göra med.

Så varför lär vi dig hur det här långsamt LinkedListfungerar?

Tja, under anställningsintervjuer kommer du att få frågan hur det LinkedListskiljer sig frånArrayList . Definitivt.