Java Academy · Lektion

LinkedList internt

Undersøg den dobbeltkædede nodalstruktur i LinkedList og dens tidskompleksitet.

Lektion 1 af 413 trin

LinkedList internt er en gratis Java Academy-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Java Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Java Academy-kurset indeholder 4 lektioner i alt.

LinkedList' interne opbygning

Javas LinkedList er en dobbeltkædet liste: Hver knude indeholder en reference til den forrige og næste knude samt elementets værdi. I modsætning til ArrayList findes der ikke noget underliggende array — hukommelsen allokeres pr. knude.

class Node<T> {
    T data;
    Node<T> prev;
    Node<T> next;
    Node(T data) { this.data = data; }
}

Profil for tidskompleksitet

Ydeevneegenskaberne for LinkedList adskiller sig markant fra ArrayList:

addFirst / addLast: O(1)
get(index): O(n) — skal gennemløbe listen fra starten eller slutningen
remove(index): O(n) for at finde elementet og derefter O(1) for at fjerne det fra kæden
Gennemløb med Iterator: O(n)

Brug LinkedList, når du har brug for hyppige indsættelser i starten eller slutningen, ikke til direkte opslag.

Oprettelse og gennemløb af en LinkedList

Oprettelse af en LinkedList og iteration følger den samme List-grænseflade, som du allerede kender. Forskellen ligger i den interne struktur.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");

for (String name : list) {
    System.out.println(name);
}

System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: "  + list.getLast());  // Carol

addFirst, addLast, removeFirst, removeLast

LinkedList tilbyder operationer i starten og slutningen, som ArrayList ikke udfører effektivt:

LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10);   // [10]
nums.addLast(20);   // [10, 20]
nums.addFirst(5);   // [5, 10, 20]

System.out.println(nums.removeFirst()); // 5  → [10, 20]
System.out.println(nums.removeLast());  // 20 → [10]

Frakobling af knude: O(1)-sletning efter at knuden er fundet

Når du har en reference til en knude via en iterator, tager fjernelsen O(1), fordi det kun er pegefelterne next/prev, der skal opdateres — ingen elementer skal flyttes som i ArrayList.

import java.util.*;

LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
    String t = it.next();
    if (t.equals("B") || t.equals("D")) {
        it.remove(); // O(1) unlink
    }
}
System.out.println(tasks); // [A, C]

Hukommelsesforbrug sammenlignet med ArrayList

Hver knude i LinkedList indeholder to ekstra referencer (prev, next) samt en reference til elementet — cirka 48 byte pr. element på en 64-bit JVM. ArrayList gemmer kun referencen til elementet (8 byte) i et sammenhængende array.

Til store datamængder med mange læseoperationer er ArrayList normalt mere cache-venlig og bruger mindre hukommelse.

Deque-operationer: Stak og kø

LinkedList implementerer Deque-grænsefladen, så den kan bruges både som stak og kø.

import java.util.LinkedList;
import java.util.Deque;

// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first

// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // top

Oversigt over PriorityQueue

PriorityQueue er en heap-baseret kø, hvor det mindste element efter naturlig rækkefølge eller komparator altid tages først ud af køen. Den er ikke baseret på en kædet liste — den bruger et array med en binær heap.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);

System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40

PriorityQueue med tilpasset Comparator

Angiv en Comparator for at vende sorteringsrækkefølgen eller sortere efter et tilpasset felt:

import java.util.*;

record Task(String name, int priority) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));

while (!tasks.isEmpty()) {
    System.out.println(tasks.poll().name());
}
// High, Med, Low

Valg mellem LinkedList og ArrayList

Tommelfingerregel:

Brug ArrayList til direkte opslag, gennemløb og de fleste situationer.
Brug LinkedList, når du har brug for hyppige O(1)-indsættelser og -fjernelser i begge ender og ikke har brug for opslag efter indeks.
Brug PriorityQueue, når du har brug for behandling i sorteret rækkefølge, f.eks. opgaveplanlægning eller Dijkstras algoritme.

Almindelige faldgruber

Undgå at kalde get(i) i en løkke på en LinkedList — det giver samlet O(n²):

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);

// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
    int val = list.get(i); // slow!
}

// GOOD: O(n) — use iterator
for (int val : list) {
    // process val
}

Hurtigt tjek

Hvilken operation på LinkedList er O(1) uanset listestørrelsen?

Besvar den i den interaktive lektion

Opsummering: LinkedList og Deque

Vigtigste pointer:

LinkedList er en dobbeltkædet liste med O(1)-operationer i starten og slutningen
Direkte opslag med get/set efter indeks er O(n)
Implementerer Deque og kan bruges som stak eller kø
PriorityQueue giver behandling i heap-sorteret rækkefølge
Foretræk ArrayList til de fleste anvendelser; LinkedList er velegnet til hyppige ændringer i starten eller slutningen

Gratis at komme i gang

Lær Java med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 104
Lektioner: 374

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “LinkedList internt” gratis?

Ja — hele teksten til “LinkedList internt” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Java Academy-kurset, skal du opgradere til CoddyKit PRO. Java Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “LinkedList internt”?

Undersøg den dobbeltkædede nodalstruktur i LinkedList og dens tidskompleksitet. Du øver dig i Java Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Java Academy?

Der kræves ingen tidligere erfaring. Java Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.

Hvor lang tid tager lektionen “LinkedList internt”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Java Academy-lektion?

Ja. Alle Java Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til Java Academy