streamalism.org

1. Introduksjon

LinkedList er en dobbeltkoblet listeimplementering av Liste og Deque grensesnitt. Den implementerer alle valgfrie listeoperasjoner og tillater alle elementer (inkludert null).

2. Funksjoner

Nedenfor finner du de viktigste egenskapene til LinkedList:

• Operasjoner som indekserer i listen vil krysse listen fra begynnelsen eller slutten, avhengig av hva som er nærmere den angitte indeksen
• Den er ikke synkronisert
• Det er Iterator og ListIterator iteratorer er feilsnelle (noe som betyr at etter at listen er endret, hvis listen er endret, a ConcurrentModificationException vil bli kastet)
• Hvert element er en node som holder en referanse til neste og forrige
• Den opprettholder innsettingsrekkefølgen

Selv om LinkedList ikke er synkronisert, kan vi hente en synkronisert versjon av den ved å ringe Collections.synchronizedList metode, som:

Listeliste = Collections.synchronizedList (ny LinkedList (...));

3. Sammenligning med ArrayList

Selv om begge implementerer Liste grensesnitt, har de forskjellige semantikk - som definitivt vil påvirke avgjørelsen om hvilken du skal bruke.

3.1. Struktur

An ArrayList er en indeksbasert datastruktur støttet av en Array. Den gir tilfeldig tilgang til elementene med en ytelse lik O (1).

På den annen side, a LinkedList lagrer dataene som en liste over elementer, og hvert element er knyttet til det forrige og neste elementet. I dette tilfellet har søkeoperasjonen for en vare kjøringstid lik O (n).

3.2. Operasjoner

Innsettings-, tilleggs- og fjerningsoperasjonene til en vare er raskere i en LinkedList fordi det ikke er behov for å endre størrelse på en matrise eller oppdatere indeksen når et element legges til en vilkårlig posisjon inne i samlingen, vil bare referanser i omgivende elementer endres.

3.3. Minnebruk

EN LinkedList bruker mer minne enn en ArrayList på grunn av hver node i en LinkedList lagrer to referanser, en for sitt forrige element og en for sitt neste element, mens ArrayList inneholder bare data og dens indeks.

4. Bruk

Her er noen kodeeksempler som viser hvordan du kan bruke LinkedList:

4.1. Opprettelse

LinkedList linkedList = ny LinkedList ();

4.2. Legger til element

LinkedList redskaper Liste og Deque grensesnitt, i tillegg til standard legge til() og Legg til alle() metoder du kan finne addFirst () og addLast (), som legger til et element i henholdsvis begynnelsen eller slutten.

4.3. Fjerner elementet

På samme måte som elementtillegg tilbyr denne listen implementering removeFirst () og removeLast ().

Det er også praktisk metode removeFirstOccurence () og removeLastOccurence () som returnerer boolsk (sant hvis samlingen inneholdt spesifisert element).

4.4. Køoperasjoner

Deque grensesnittet gir kø-lignende atferd (faktisk Deque strekker Kø grensesnitt):

linkedList.poll (); linkedList.pop ();

Disse metodene henter det første elementet og fjerner det fra listen.

Forskjellen mellom avstemming() og pop () er det pop vil kaste NoSuchElementException () på tom liste, mens avstemming returnerer null. API-ene pollFirst () og pollLast () er også tilgjengelig.

Her er for eksempel hvordan trykk API fungerer:

linkedList.push (Objekt o);

Som setter inn elementet som leder av samlingen.

LinkedList har mange andre metoder, hvorav de fleste bør være kjent for en bruker som allerede har brukt Lister. Andre som er levert av Deque kan være et praktisk alternativ til "standard" -metoder.

Den fullstendige dokumentasjonen finner du her.

5. Konklusjon

ArrayList er vanligvis standard Liste gjennomføring.

Imidlertid er det visse brukstilfeller der du bruker LinkedList vil passe bedre, for eksempel preferanser for konstant innsetting / slettingstid (f.eks. hyppige innsettinger / slettinger / oppdateringer), over konstant tilgangstid og effektiv minnebruk.

Kodeeksempler finner du på GitHub.