Java LinkedList-Klasse | W3Docs Learn Java

LinkedList<E> ist eine doppelt verkettete Liste: Jedes Element lebt in einem eigenen Heap-Knoten mit einem Zeiger auf den nächsten und einem auf den vorherigen Knoten. Das ergibt das gegenteilige Performance-Profil zu ArrayList: Einfügen und Entfernen an den Enden ist O(1), aber get(i) muss von einem Ende bis zum Index laufen — O(n). Die Klasse ist auch Javas einzige eingebaute List, die zusätzlich Deque<E> implementiert, und verdoppelt sich damit als Queue. Dieses Kapitel erklärt, wann diese Kombination das richtige Werkzeug ist — und die (etwas längere) Liste der Fälle, in denen sie es nicht ist.

Die Datenstruktur

Jedes Element ist ein Knoten:

node:  prev ←—— element ——→ next

Die Liste hält zwei Feldreferenzen — first und last — sowie einen size-Zähler. Um an einem Ende einzufügen, wird ein Knoten allokiert, durch Anpassen von zwei Zeigern eingehängt und size erhöht. Kein Array, kein Resize, kein ungenutzter Speicher. Das ist der Reiz.

Die Kosten entstehen überall sonst:

Jedes Element bezahlt für ein Knotenobjekt — drei Referenzen und einen Objekt-Header. Der Speicher-Overhead pro Element ist deutlich höher als das flache Array von ArrayList.
get(i), set(i, x), add(i, x), remove(i) laufen alle vom näheren Ende. Daher ist list.get(size/2) O(n/2). Bei langen Listen summiert sich das ungünstig.
Cache-Lokalität ist schlecht — Knoten sind über den Heap verstreut, sodass die Traversierung den CPU-Cache verfehlt und die Ausführung verlangsamt, selbst wenn der Algorithmus linear aussieht.

Wann `LinkedList` die richtige Wahl ist

Die ehrliche Antwort im Jahr 2026: selten als List, manchmal als Deque, fast nie um „Einfügungen zu beschleunigen." Das Klischee „nimm LinkedList, weil du viel einfügst" hat sich nicht bewährt — für die meisten Workloads schlägt die Cache-Freundlichkeit von ArrayList plus sein amortisiertes O(1)-Anhängen das zusätzliche Pointer-Chasing einer verketteten Liste, selbst wenn der Algorithmus manchmal add(0, x) aufruft. Die Fälle, in denen LinkedList tatsächlich gewinnt:

Du brauchst eine Deque (Hinzufügen/Entfernen an beiden Enden) und hast kein ArrayDeque zur Hand. ArrayDeque ist schneller; LinkedList ist vertrauter.
Du hältst persistente Referenzen auf bestimmte Knoten (über ListIterator) und möchtest O(1)-Einfügen/Entfernen an genau diesen Positionen. Das ist der Lehrbuch-Anwendungsfall für verkettete Listen — und er kommt im alltäglichen Java fast nie vor.
Du willst eine Queue-Implementierung, die auch List-Methoden zur Inspektion bietet. Reales Beispiel: eine Job-Queue, die gelegentlich in ein Log geschrieben wird.

Für „Liste, an die ich anhänge und nach Index lese," greife zu ArrayList. Für „Queue oder Deque," greife zu ArrayDeque. LinkedList liegt zwischen beiden und ist selten die beste Wahl für einen der beiden Jobs.

Eine erstellen und als `List` verwenden

Die List-Hälfte der API ist identisch mit ArrayList:

List<String> tasks = new LinkedList<>();
tasks.add("compile");
tasks.add("test");
tasks.add(0, "lint");          // O(1) — at the head
String first = tasks.get(0);   // O(1) — head
String last  = tasks.get(tasks.size() - 1);   // O(1) — tail
String mid   = tasks.get(tasks.size() / 2);   // O(n/2) — has to walk

Der Konstruktor hat keinen Kapazitätsparameter — es gibt nichts vorzubelegen, da Knoten einzeln allokiert werden.

Als `Queue` und `Deque` verwenden

Da LinkedList sowohl Queue<E> als auch Deque<E> implementiert, stehen die Queue-Methoden zusätzlich zu den List-Methoden zur Verfügung:

Deque<String> stack = new LinkedList<>();
stack.push("a");          // adds to head
stack.push("b");
String top = stack.pop(); // removes from head → "b"

Queue<String> jobs = new LinkedList<>();
jobs.offer("j1");         // adds to tail
jobs.offer("j2");
String next = jobs.poll();// removes from head → "j1"

Wenn dein Bedarf rein „FIFO-Queue" oder „LIFO-Stack" ist, deklariere die Variable als Queue<E> oder Deque<E> — und bevorzuge new ArrayDeque<>() als Implementierung. Das Interface ist dasselbe; die Array-gestützte Implementierung ist messbar schneller.

Iteration und `ConcurrentModificationException`

Gleiches Fail-Fast-Modell wie bei ArrayList. Änderungen während einer For-each-Schleife werfen eine Exception:

LinkedList<Integer> xs = new LinkedList<>(List.of(1, 2, 3, 4));
for (int x : xs) if (x % 2 == 0) xs.remove(Integer.valueOf(x));  // throws

removeIf und das explizite Iterator.remove() sind die zwei sicheren Formen — identisch zum ArrayList-Kapitel. Die interessante Besonderheit bei LinkedList ist der ListIterator: Da der Iterator eine direkte Referenz auf den aktuellen Knoten hält, sind sein add und remove wirklich O(1). Wenn du wirklich schnelles Einfügen an einer bestimmten Position während der Iteration brauchst, ist LinkedList.listIterator() die API, die das Lehrbuchversprechen einlöst.

Thread-Sicherheit

Gleiche Geschichte wie bei ArrayList: keine. Verwende Collections.synchronizedList(new LinkedList<>()) für pauschale Synchronisation, oder — viel besser — eine ConcurrentLinkedDeque, wenn dein Anwendungsfall wirklich eine nebenläufige Queue ist.

Der `ArrayDeque`-Vergleich in einem Absatz

Wenn du zu LinkedList greifst, um es als Queue oder Stack zu nutzen, schau zuerst auf ArrayDeque. ArrayDeque ist ein zirkuläres Array — kein Knoten pro Element, kein Pointer-Chasing, keine null-Ablehnungsregeln zum Merken. Bei großen, realen Stack/Queue-Workloads übertrifft es LinkedList typischerweise — manchmal deutlich — weil es keinen Heap-Knoten und keinen Header pro Element allokiert und seine Daten zusammenhängend im Speicher hält. Es implementiert kein List, was sein einziger echter Nachteil ist. (Überinterpretiere keinen kleinen Benchmark in eine Richtung; sieh das ausgearbeitete Beispiel unten.)

Ein ausgearbeitetes Beispiel: gleicher Job, zwei Datenstrukturen

Das folgende Programm baut dieselbe Queue mit ArrayList, LinkedList und ArrayDeque — schiebt an ein Ende, holt vom anderen Ende 200 000 Mal — und gibt die Wanduhrzeit für jede Variante aus. Lies die Zahlen im Kontext: Sie sind ein grober Einzel-Micro-Benchmark auf einer kalten JVM, kein rigoroses Ergebnis, also betrachte die relative Reihenfolge — nicht die exakten Millisekunden — als die eigentliche Lehre. ArrayList ist deutlich langsamer als die anderen beiden, weil remove(0) O(n) ist und die Entleerungsschleife damit quadratisch wird. LinkedList und ArrayDeque sind beide schnell: Beide leisten O(1)-Arbeit am Kopf. Welches der beiden vorne liegt, hängt vom Rechner, dem JIT und Integer-Boxing ab — genau deshalb solltest du dich niemals auf einen so kleinen Benchmark stützen, um zwischen ihnen zu wählen.

java— editable, runs on the server

import java.util.*;

public class ListVsDeque {
  public static void main(String[] args) {
    final int N = 200_000;

// --- LinkedList as a List (showing get-by-index is O(n)) ---
    LinkedList<Integer> linked = new LinkedList<>();
    for (int i = 0; i < 10_000; i++) linked.add(i);
    long t0 = System.nanoTime();
    long sum = 0;
    for (int i = 0; i < linked.size(); i++) sum += linked.get(i);   // SLOW: O(n²)
    long byIndexMs = (System.nanoTime() - t0) / 1_000_000;
    System.out.println("LinkedList 10k get(i) loop: ~" + byIndexMs + " ms (sum=" + sum + ")");

long t1 = System.nanoTime();
    sum = 0;
    for (int v : linked) sum += v;                                  // FAST: single walk
    long iterMs = (System.nanoTime() - t1) / 1_000_000;
    System.out.println("LinkedList 10k for-each:    ~" + iterMs + " ms (sum=" + sum + ")");

System.out.println();

// --- Queue: push tail, pop head, three implementations ---
    // LinkedList implements BOTH List and Deque, so a bare new LinkedList<>()
    // would make the overloaded call below ambiguous. Pin it to Deque.
    Deque<Integer> linkedDeque = new LinkedList<>();
    long aListMs   = timeQueue(new ArrayList<>(), N);
    long linkedMs  = timeQueue(linkedDeque, N);
    long arrDeqMs  = timeQueue(new ArrayDeque<>(), N);

System.out.println("queue " + N + " push/pop cycles:");
    System.out.println("  ArrayList:  ~" + aListMs  + " ms   (slow — remove(0) is O(n))");
    System.out.println("  LinkedList: ~" + linkedMs + " ms   (fast — pointer surgery at the head)");
    System.out.println("  ArrayDeque: ~" + arrDeqMs + " ms   (fast — circular array, no per-node alloc)");
  }

static long timeQueue(List<Integer> q, int n) {
    long t = System.nanoTime();
    for (int i = 0; i < n; i++) q.add(i);          // enqueue at tail
    for (int i = 0; i < n; i++) q.remove(0);       // dequeue from head
    return (System.nanoTime() - t) / 1_000_000;
  }

static long timeQueue(Deque<Integer> q, int n) {
    long t = System.nanoTime();
    for (int i = 0; i < n; i++) q.offerLast(i);    // enqueue
    for (int i = 0; i < n; i++) q.pollFirst();     // dequeue
    return (System.nanoTime() - t) / 1_000_000;
  }
}

Zwei Erkenntnisse:

Die ersten zwei Zeitmessungen zeigen, warum man eine LinkedList niemals per Index in einer Schleife durchläuft. Die For-each-Form durchläuft die Liste einmal in O(n); die Index-Form durchläuft sie einmal pro Index, was O(n²) ergibt. Bei 10 000 Elementen ist das bereits schmerzhaft; bei 100 000 dauert es Sekunden.
Die drei Queue-Zeitmessungen zeigen die eigentliche Trennlinie: Sie liegt zwischen ArrayList (quadratische Entleerung) und den beiden O(1)-am-Kopf-Strukturen, nicht zwischen LinkedList und ArrayDeque. Wenn du ArrayList für Queue-Arbeit ausgeschlossen hast, bevorzuge trotzdem ArrayDeque — es allokiert keinen Knoten pro Element und hat bei großen, langlebigen Queues deutlich bessere Cache-Lokalität, was ein 200 000-Element-Kaltstart-Loop nicht vollständig offenbart. Der verbleibende echte Grund, LinkedList zu verwenden, ist „Ich will eine Deque und eine List" — und selbst das ist selten.

Was kommt als Nächstes

LinkedList und ArrayList sind die beiden interessanten Allzweck-List-Implementierungen. Die dritte — älter, synchronisiert, meist historisch — ist Vector. Zu wissen, warum sie im neuen Code nicht die richtige Wahl ist, gehört dazu, das Framework sicher zu beherrschen.

Übungen

Übung

Du brauchst eine lange FIFO-Queue, an deren Ende du schreibst und von deren Anfang du liest, hunderttausende Male pro Sekunde. Was ist die beste Standardwahl?

`ArrayDeque` — zirkulär-Array-gestützt, O(1) an beiden Enden, keine Knoten-Allokation pro Element`LinkedList` — explizit als doppelt verkettete Deque konzipiert und schneller als ArrayDeque`ArrayList` mit `add(x)` und dann `remove(0)` — die API ist am einfachsten`Vector` — seine Synchronisation verhindert automatisch Enqueue/Dequeue-Wettlaufbedingungen

Die Datenstruktur

Wann LinkedList die richtige Wahl ist

Eine erstellen und als List verwenden

Als Queue und Deque verwenden

Iteration und ConcurrentModificationException