Vi introduserer LinkedList-samlingen

1. Historien omLinkedList

Java har en annen samlingsklasse Java arvet fra C++-språket. Dette er LinkedListklassen som implementerer en "lenket liste".

Utad ser a LinkedListut til å være det samme som en ArrayList. Klassen LinkedListhar alle de samme metodene som ArrayListklassen. I prinsippet kan du alltid bruke en LinkedListi stedet for en ArrayListog alt vil fungere.

Så hvorfor trenger vi en annen listeklasse?

Svaret har alt å gjøre med den interne strukturen i LinkedListklassen. I stedet for en matrise bruker den en dobbeltlenket liste . Vi vil forklare hva det er litt senere.

Klassens LinkedListulike interne struktur gjør den raskest til å sette inn elementer midt på listen.

På Internett kan du ofte finne sammenligninger av klassene ArrayListog LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Alt virker klart nok: hvis du trenger å sette inn elementer i listen ofte, bruk LinkedList; hvis sjelden, bruk ArrayList. Men virkeligheten er litt annerledes.

2. Ingen brukerLinkedList

Ingen bruker LinkedList.

Til og med forfatteren av klassen LinkedListtwitret nylig: "Bruker noen faktisk LinkedList? Jeg skrev det, og jeg bruker det aldri."

Så hva er greia?

Først begynte klassen ArrayListveldig raskt å kunne sette inn elementer midt på listen. Når du setter inn et element i midten av listen, må du flytte alle elementene etter innsettingspunktet med 1 mot slutten av listen. Dette pleide å ta tid.

Men nå har alt endret seg. Alle elementene i en matrise er nær hverandre i den samme minneblokken, så operasjonen for å skifte elementene utføres av en veldig rask lavnivåkommando: .System.arraycopy()

I tillegg har dagens prosessorer en stor cache som vanligvis kan inneholde hele arrayet, noe som gjør at array-elementene kan flyttes inne i cachen i stedet for i minnet. En million elementer forskyves lett på et enkelt millisekund.

For det andre kan klassen LinkedListsette inn elementer raskt hvis du setter dem inn ved hjelp av en iterator. Hvis du bruker en iterator for å gå gjennom en LinkedListog hele tiden sette inn nye elementer (eller fjerne eksisterende), er operasjonen superrask.

Hvis du ganske enkelt legger til elementer til et LinkedListobjekt inne i en løkke, blir hver hurtiginnsettingsoperasjon ledsaget av en langsom "hent element"-operasjon.

Virkeligheten er mye nærmere dette:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

LinkedListHvorfor er det så treg å få et element fra en operasjon?

Du kan svare på det spørsmålet etter å ha satt deg litt inn i hvordan LinkedLister strukturert.

3. Hvordan LinkedLister strukturert

LinkedListhar en annen intern struktur enn ArrayList. Den har ikke en intern matrise for lagring av elementer. I stedet bruker den en datastruktur som kalles en liste med dobbelt blekk .

Hvert element i en dobbeltlenket liste lagrer en referanse til det forrige elementet og det neste elementet. Dette er litt som en linje i en butikk, der hver person husker personen som står foran dem, så vel som personen som står bak dem.

Slik ser en slik liste ut i minnet:

Hodet og halen (celler med grå bakgrunn) er variablene firstog last, som lagrer referanser til Nodeobjekter.

I midten har du en kjede av Nodeobjekter (objekter, ikke variabler). Hver av dem består av tre felt:

• prev— lagrer en referanse (lenke) til forrige Nodeobjekt (celler med gul bakgrunn).
• value— lagrer verdien til dette elementet i listen (celler med grønn bakgrunn).
• next— lagrer en referanse (lenke) til neste Nodeobjekt (celler med blå bakgrunn)

Det andre objektet (adresse F24) er det neste ( next) for det første objektet og det forrige ( prev) for det tredje objektet. Det gule feltet til det tredje objektet inneholder adressen F24 og det blå feltet til det første objektet inneholder adressen F24.

Pilene fra det første og tredje objektet peker til det samme andre objektet. Så det ville vært mer riktig å tegne pilene slik.

4. Sett inn et element i en koblet liste

For å legge til noen i linjen som dette, trenger du bare å få tillatelse til to personer som står ved siden av hverandre. Den første personen husker nykommeren som "personen bak meg", og den andre personen husker dem som "personen foran meg".

Alt du trenger å gjøre er å endre referansene til de to naboobjektene:

Vi la til et nytt element i listen vår ved å endre referansene til det andre og tredje objektet. Det nye objektet er det neste for det gamle andre objektet og det forrige for det gamle tredje objektet. Og selvfølgelig må det nye objektet selv lagre de riktige referansene: dets forrige objekt er det gamle andre objektet, og det neste objektet er det gamle tredje objektet.

Å fjerne et element er enda enklere: Hvis vi ønsker å fjerne, la oss si, det 100. objektet fra listen, trenger vi bare å endre feltet nextfor det 99. objektet slik at det peker til det 101. objektet, og endre feltet prevfor det 101. objekt slik at det peker mot 99. Det er det.

Men å få det 100. objektet er ikke så lett.

5. Fjern et element fra en liste

For å få det 100. elementet i en koblet liste, må du:

Hent 1. objekt: Dette gjør du ved å bruke firstvariabelen i LinkedListobjektet. Feltet nexttil det 1. objektet lagrer en referanse til det 2. objektet. Slik får vi det andre objektet. Det andre objektet har en referanse til det tredje, og så videre.

Hvis vi trenger å få en referanse til det 100. objektet, må vi sekvensielt bevege oss gjennom alle objektene fra det 1. til det 100. Og hvis vi trenger det millionte elementet i en liste, må vi iterere over en million objekter etter hverandre!

Og hvis disse objektene ble lagt til listen på forskjellige tidspunkter, vil de være plassert i forskjellige deler av minnet og vil neppe havne i prosessorens cache samtidig. Dette betyr at det å iterere over elementene i en koblet liste ikke bare er sakte, men veldig sakte.

Det er det vi har med å gjøre.

Så hvorfor lærer vi deg hvordan dette trege LinkedListfungerer?

Vel, under jobbintervjuer vil du bli spurt om hvordan LinkedListforskjellen er fraArrayList . Helt sikkert.