Introduktion af LinkedList-kollektionen

1. Historie afLinkedList

Java har en anden samlingsklasse Java arvet fra C++ sproget. Dette er LinkedListklassen, som implementerer en "sammenkædet liste".

Udadtil ser a LinkedListud til at være det samme som en ArrayList. Klassen LinkedListhar alle de samme metoder som ArrayListklassen. I princippet kan du altid bruge en LinkedListi stedet for en ArrayListog alt vil virke.

Så hvorfor har vi brug for endnu en listeklasse?

Svaret har alt at gøre med den interne struktur i LinkedListklassen. I stedet for et array bruger den en dobbelt linket liste . Hvad det er, forklarer vi lidt senere.

Klassens LinkedListanderledes interne struktur gør den hurtigst til at indsætte elementer i midten af ​​listen.

På internettet kan du ofte finde sammenligninger af klasserne ArrayListog LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Alt virker klart nok: Hvis du ofte skal indsætte elementer i listen, skal du bruge LinkedList; hvis sjældent, så brug ArrayList. Men virkeligheden er lidt anderledes.

2. Ingen brugerLinkedList

Ingen bruger LinkedList.

Selv forfatteren af ​​klassen LinkedListtweetede for nylig: "Bruger nogen rent faktisk LinkedList? Jeg skrev det, og jeg bruger det aldrig."

Så hvad er aftalen?

Først begyndte klassen ArrayListmeget hurtigt at kunne indsætte elementer i midten af ​​listen. Når du indsætter et element i midten af ​​listen, skal du flytte alle elementerne efter indsættelsespunktet med 1 mod slutningen af ​​listen. Dette plejede at tage tid.

Men nu har alt ændret sig. Alle elementerne i et array er tæt på hinanden i den samme hukommelsesblok, så operationen for at flytte elementerne udføres af en meget hurtig lav-niveau kommando: .System.arraycopy()

Derudover har dagens processorer en stor cache, der normalt kan rumme hele arrayet, hvilket gør det muligt at flytte array-elementerne inde i cachen frem for i hukommelsen. En million elementer flyttes let på et enkelt millisekund.

For det andet kan klassen LinkedListindsætte elementer hurtigt, hvis du indsætter dem ved hjælp af en iterator. Hvis du bruger en iterator til at gennemgå en LinkedListog hele tiden indsætte nye elementer (eller fjerne eksisterende), er operationen super hurtig.

Hvis du blot tilføjer elementer til et LinkedListobjekt inde i en løkke, så ledsages hver hurtig indsættelsesoperation af en langsom "hent element"-operation.

Virkeligheden er meget tættere på dette:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Hvorfor får man et element fra en LinkedListsådan langsom operation?

Det spørgsmål kan du besvare efter at have sat dig lidt ind i, hvordan LinkedLister opbygget.

3. Hvordan LinkedLister opbygget

LinkedListhar en anden indre struktur end ArrayList. Den har ikke et internt array til lagring af elementer. I stedet bruger den en datastruktur kaldet en dobbeltfarvet liste .

Hvert element i en dobbelt-linket liste gemmer en reference til det forrige element og det næste element. Dette er lidt ligesom en linje i en butik, hvor hver person husker den person, der står foran dem, såvel som den person, der står bag dem.

Sådan ser sådan en liste ud i hukommelsen:

Hovedet og halen (celler med en grå baggrund) er variablerne firstog last, som gemmer referencer til Nodeobjekter.

I midten har du en kæde af Nodeobjekter (objekter, ikke variable). Hver af dem består af tre felter:

• prev— gemmer en reference (link) til det forrige Nodeobjekt (celler med gul baggrund).
• value— gemmer værdien af ​​dette element i listen (celler med grøn baggrund).
• next— gemmer en reference (link) til det næste Nodeobjekt (celler med blå baggrund)

Det andet objekt (adresse F24) er det næste ( next) for det første objekt og det forrige ( prev) for det tredje objekt. Det gule felt på det tredje objekt indeholder adressen F24, og det blå felt på det første objekt indeholder adressen F24.

Pilene fra det første og tredje objekt peger på det samme andet objekt. Så det ville være mere korrekt at tegne pilene sådan her.

4. Indsæt et element til en sammenkædet liste

For at tilføje nogen til linje som denne, skal du blot have tilladelse fra to personer, der står ved siden af ​​hinanden. Den første person husker den nytilkomne som "personen bag mig", og den anden person husker dem som "personen foran mig".

Alt du skal gøre er at ændre referencerne for de to naboobjekter:

Vi tilføjede et nyt element til vores liste ved at ændre referencerne for det andet og tredje objekt. Det nye objekt er det næste for det gamle andet objekt og det forrige for det gamle tredje objekt. Og selvfølgelig skal det nye objekt selv gemme de korrekte referencer: dets forrige objekt er det gamle andet objekt, og dets næste objekt er det gamle tredje objekt.

Det er endnu nemmere at fjerne et element: Hvis vi ønsker at fjerne, lad os sige, det 100. objekt fra listen, skal vi bare ændre feltet nextfor det 99. objekt, så det peger på det 101. objekt, og ændre feltet prevfor det 101. objekt, så det peger på den 99. Det er det.

Men at få det 100. objekt er ikke så let.

5. Fjern et element fra en liste

For at få det 100. element i en linket liste skal du:

Hent det 1. objekt: Det gør du ved at bruge firstvariablen i LinkedListobjektet. Feltet nextfor det 1. objekt gemmer en reference til det 2. objekt. Det er sådan, vi får det andet objekt. Det 2. objekt har en reference til det tredje, og så videre.

Hvis vi skal have en reference til det 100. objekt, skal vi sekventielt bevæge os gennem alle objekterne fra det 1. til det 100. Og hvis vi har brug for det millionte element i en liste, skal vi iterere over en million objekter efter hinanden!

Og hvis disse objekter blev tilføjet til listen på forskellige tidspunkter, vil de være placeret i forskellige dele af hukommelsen og er usandsynligt, at de ender i processorens cache på samme tid. Det betyder, at gentagelse af elementerne i en sammenkædet liste ikke bare er langsom, men meget langsom.

Det er det, vi har med at gøre.

Så hvorfor lærer vi dig, hvordan dette langsomme LinkedListvirker?

Nå, under jobsamtaler bliver du spurgt, hvordan LinkedListadskiller sig fraArrayList . Helt bestemt.