PricingLoginStart free
Java Academy · leksjon

LinkedList kontra ArrayList

Sammenlign ytelsen ved innsetting, sletting og tilfeldig tilgang for å velge riktig listetype.

Leksjon 3 av 413 trinn

LinkedList kontra ArrayList er en gratis leksjon i Java Academy på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Java Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Java Academy inneholder totalt 4 leksjoner.

Det sentrale spørsmålet

Både ArrayList og LinkedList implementerer List, så de deler samme API. Forskjellen ligger i de interne datastrukturene og hvilke operasjoner hver av dem utfører effektivt.

ArrayList-interne detaljer

ArrayList lagrer elementer i et sammenhengende array. Når arrayet blir fullt, erstattes det med et nytt array som er 1,5× større, og alle elementene kopieres.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

LinkedList-interne detaljer på nytt

Hvert element ligger i sitt eget Node-objekt med prev-/next-pekere. Det finnes ikke sammenhengende minne — nodene kan ligge hvor som helst på heapen.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

Direkte tilgang: ArrayList vinner

ArrayList.get(i) er O(1) — direkte tilgang via arrayindeks. LinkedList.get(i) er O(n) — går gjennom opptil n/2 noder.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

Innsetting først: LinkedList vinner

Å legge til på indeks 0 i ArrayList krever at alle elementene forskyves — O(n). LinkedList oppdaterer bare to pekere — O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

Innsetting bakerst: Omtrent likt

Både ArrayList og LinkedList tilbyr amortisert O(1)-kompleksitet når elementer legges til bakerst. ArrayList utløser av og til en kopiering ved utvidelse, men har fortsatt O(1) amortisert kostnad. LinkedList oppretter en ny node — ingen utvidelse er nødvendig.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

Minnebruk

ArrayList: ~8 byte per element (én referanse i arrayet). LinkedList: ~48 byte per element (Node-objekt med data, prev, next samt objektheader). For store datasett bruker ArrayList betydelig mindre minne.

Ytelse ved gjennomgang

Sekvensiell gjennomgang (for-each eller iterator) er O(n) for begge. ArrayList drar imidlertid fordel av forhåndshenting i CPU-cachen — elementene ligger sammenhengende i minnet. LinkedList-nodene er spredt rundt på heapen, noe som fører til cache-misser.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

Innsetting og sletting i midten

Begge krever O(n) for å finne posisjonen. Når den er funnet, forskyver ArrayList elementer med O(n), mens LinkedList bare kobler fra noden med O(1). Ved hyppige endringer i midten når du allerede har en iterator vinner LinkedList; ellers er de omtrent like.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

Veiledning for valg

Velg basert på operasjonen du utfører oftest:

  • ArrayList: direkte tilgang, gjennomgang og innsetting bakerst — dekker 90 % av bruksområdene
  • LinkedList: hyppig innsetting og fjerning først eller sist i listen, eller implementering av kø/deque/stack
  • ArrayDeque: når du trenger en ren kø eller stack (bedre enn LinkedList)

Oppsummering av ytelsesmålinger

En mental modell for ytelse:

  • get(i): ArrayList O(1) mot LinkedList O(n)
  • add(0,x): ArrayList O(n) mot LinkedList O(1)
  • add(x): Begge har amortisert O(1)
  • Fjerning med iterator: Begge har O(1) når posisjonen er funnet
  • Minne per element: ArrayList ~8 B mot LinkedList ~48 B

Kort sjekk

Du bygger en oppgavekø der oppgaver legges til bakerst og fjernes først i listen millioner av ganger per sekund. Hvilken datastruktur er best egnet?

Besvar den i den interaktive leksjonen

Oppsummering: LinkedList vs ArrayList

Viktigste poenger:

  • ArrayList egner seg godt for tilfeldig aksess (O(1)) og hurtigbuffer-vennlig iterasjon
  • LinkedList egner seg godt for O(1)-operasjoner i begynnelsen og slutten
  • Minne: ArrayList ~8 B per element; LinkedList ~48 B per element
  • For køer og stabler bør De foretrekke ArrayDeque fremfor LinkedList
  • ArrayList er det riktige standardvalget i de fleste tilfeller
Gratis å komme i gang

Lær deg Java med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs
104
Leksjoner
374
Start læringen gratisSe hele kurset

Ofte stilte spørsmål

Er leksjonen «LinkedList kontra ArrayList» gratis?

Ja – hele teksten i «LinkedList kontra ArrayList» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Java Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Java Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «LinkedList kontra ArrayList»?

Sammenlign ytelsen ved innsetting, sletting og tilfeldig tilgang for å velge riktig listetype. Du øver på Java Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Java Academy?

Ingen tidligere erfaring er nødvendig. Java Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.

Hvor lang tid tar leksjonen «LinkedList kontra ArrayList»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Java Academy-leksjonen?

Ja. Alle Java Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

  1. LinkedList internt
  2. Deque-operasjoner: stack og kø
  3. LinkedList kontra ArrayList
  4. PriorityQueue for ordnet behandling
← Tilbake til Java Academy