streamalism.org

1. Introduktion

LinkedList er en dobbeltkoblet listeimplementering af Liste og Deque grænseflader. Den implementerer alle valgfri listehandlinger og tillader alle elementer (inklusive nul).

2. Funktioner

Nedenfor kan du finde de vigtigste egenskaber ved LinkedList:

• Handlinger, der indekseres på listen, krydser listen fra begyndelsen eller slutningen, alt efter hvad der er tættest på det angivne indeks
• Det er ikke synkroniseret
• Dens Iterator og ListIterator iteratorer er fail-hurtige (hvilket betyder, at hvis listen er ændret efter iteratorens oprettelse, a ConcurrentModificationException vil blive kastet)
• Hvert element er en knude, som holder en henvisning til den næste og forrige
• Den opretholder indsætningsrækkefølgen

Selvom LinkedList ikke er synkroniseret, kan vi hente en synkroniseret version af den ved at ringe til Collections.synchronizedList metode, som:

Liste liste = Collections.synchronizedList (ny LinkedList (...));

3. Sammenligning med ArrayList

Selvom begge implementerer Liste interface har de forskellige semantik - hvilket helt sikkert vil påvirke beslutningen om hvilken man skal bruge.

3.1. Struktur

En ArrayList er en indeksbaseret datastruktur understøttet af en Array. Det giver tilfældig adgang til dets elementer med en ydeevne svarende til O (1).

På den anden side er en LinkedList gemmer sine data som en liste over elementer, og hvert element er knyttet til dets forrige og næste element. I dette tilfælde har søgefunktionen efter et element eksekveringstid lig med O (n).

3.2. Operationer

Indsættelses-, tilføjelses- og fjernelsesoperationer af en vare er hurtigere i en LinkedList fordi der ikke er behov for at ændre størrelsen på en matrix eller opdatere indekset, når et element føjes til en vilkårlig position inde i samlingen, vil kun referencer i omgivende elementer ændre sig.

3.3. Hukommelsesbrug

EN LinkedList bruger mere hukommelse end en ArrayList på grund af hver knude i en LinkedList gemmer to referencer, en for det forrige element og en for det næste element, hvorimod ArrayList har kun data og dets indeks.

4. Anvendelse

Her er nogle kodeeksempler, der viser, hvordan du kan bruge LinkedList:

4.1. Skabelse

LinkedList linkedList = ny LinkedList ();

4.2. Tilføjer element

LinkedList redskaber Liste og Deque interface, udover standard tilføje() og tilføjAlle () metoder, du kan finde addFirst () og addLast (), som tilføjer et element i henholdsvis begyndelsen eller slutningen.

4.3. Fjernelse af element

På samme måde som elementtilsætning tilbyder denne liste implementering removeFirst () og removeLast ().

Der er også en praktisk metode removeFirstOccurence () og removeLastOccurence () som returnerer boolsk (sand hvis samlingen indeholdt specificeret element).

4.4. Køoperationer

Deque interface giver kø-lignende opførsel (faktisk Deque strækker sig Kø interface):

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

Disse metoder henter det første element og fjerner det fra listen.

Forskellen på afstemning() og pop () er det pop vil kaste NoSuchElementException () på tom liste, hvorimod afstemning returnerer null. API'erne pollFirst () og pollLast () er også tilgængelige.

Her er for eksempel hvordan skubbe API fungerer:

linkedList.push (Objekt o);

Hvilket indsætter elementet som samlingens hoved.

LinkedList har mange andre metoder, hvoraf de fleste burde være bekendt med en bruger, der allerede har brugt Lister. Andre, der leveres af Deque kan være et praktisk alternativ til "standard" -metoder.

Den fulde dokumentation kan findes her.

5. Konklusion

ArrayList er normalt standard Liste implementering.

Der er dog visse brugstilfælde, hvor man bruger LinkedList passer bedre, såsom præferencer for konstant indsættelse / sletningstid (f.eks. hyppige indsættelser / sletninger / opdateringer), over konstant adgangstid og effektiv hukommelsesforbrug.

Kodeprøver kan findes på GitHub.