Interna von LinkedList
Untersuchen Sie die Struktur der doppelt verketteten Knoten von LinkedList und ihre Eigenschaften hinsichtlich der Zeitkomplexität.
Interna von LinkedList ist eine kostenlose Java Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Java Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.
Interna von LinkedList
Java's LinkedList ist eine doppelt verkettete Liste: Jeder Knoten enthält eine Referenz auf den vorherigen und den nächsten Knoten sowie den Elementwert. Anders als bei ArrayList gibt es kein zugrunde liegendes Array – der Speicher wird für jeden Knoten einzeln reserviert.
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}Zeitkomplexität im Überblick
Die Leistungsmerkmale von LinkedList unterscheiden sich deutlich von denen von ArrayList:
- addFirst / addLast: O(1)
- get(index): O(n) – der Anfang oder das Ende muss durchlaufen werden
- remove(index): O(n) zum Auffinden, danach O(1) zum Entfernen der Verknüpfung
- Iterator-Durchlauf: O(n)
Verwenden Sie LinkedList, wenn Sie häufig am Anfang oder Ende Elemente einfügen müssen, aber keinen wahlfreien Zugriff benötigen.
Eine LinkedList erstellen und durchlaufen
Das Erstellen einer LinkedList und das Durchlaufen erfolgen über dieselbe List-Schnittstelle, die Sie bereits kennen. Der Unterschied liegt in der internen 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()); // CaroladdFirst, addLast, removeFirst, removeLast
LinkedList bietet Operationen für den Anfang und das Ende, die ArrayList nicht effizient unterstützt:
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]Knoten entfernen: O(1) nach dem Auffinden
Sobald Sie eine Referenz auf einen Knoten haben (über einen Iterator), erfolgt das Entfernen in O(1), da nur die next-/prev-Zeiger aktualisiert werden müssen – anders als bei ArrayList ist kein Verschieben von Elementen erforderlich.
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]Speicheraufwand im Vergleich zu ArrayList
Jeder LinkedList-Knoten enthält zwei zusätzliche Referenzen (prev, next) sowie die Elementreferenz – auf einer 64-Bit-JVM etwa 48 Byte pro Eintrag. ArrayList speichert nur die Elementreferenz (8 Byte) in einem zusammenhängenden Array.
Für große, leseintensive Datenmengen ist ArrayList in der Regel cachefreundlicher und benötigt weniger Speicher.
Deque-Operationen: Stack und Queue
LinkedList implementiert die Deque-Schnittstelle und kann daher sowohl als Stack als auch als Queue verwendet werden.
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Überblick über PriorityQueue
PriorityQueue ist eine heapbasierte Warteschlange, aus der das kleinste Element (nach natürlicher Reihenfolge oder gemäß Comparator) immer zuerst entnommen wird. Sie basiert NICHT auf einer verketteten Liste, sondern verwendet ein Array mit einem binären 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()); // 40PriorityQueue mit benutzerdefiniertem Comparator
Übergeben Sie einen Comparator, um die Reihenfolge umzukehren oder nach einem benutzerdefinierten Feld zu sortieren:
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, LowLinkedList oder ArrayList auswählen
Als Faustregel gilt:
- Verwenden Sie ArrayList für wahlfreien Zugriff, Iteration und die meisten Szenarien.
- Verwenden Sie LinkedList, wenn Sie häufig O(1)-Einfügungen und -Entfernungen an beiden Enden benötigen und keinen Zugriff über Indizes brauchen.
- Verwenden Sie PriorityQueue, wenn Sie eine Verarbeitung in sortierter Reihenfolge benötigen (Aufgabenplanung, Dijkstra-Algorithmus).
Häufige Fehlerquellen
Vermeiden Sie es, get(i) in einer Schleife für eine LinkedList aufzurufen – insgesamt ergibt das 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
}Kurztest
Welche LinkedList-Operation hat unabhängig von der Größe der Liste die Komplexität O(1)?
Zusammenfassung: LinkedList und Deque
Die wichtigsten Erkenntnisse:
- LinkedList ist eine doppelt verkettete Liste mit O(1)-Operationen am Anfang und Ende
- Wahlfreier Zugriff (get/set über einen Index) hat die Komplexität O(n)
- Implementiert Deque und kann als Stack oder Queue verwendet werden
- PriorityQueue ermöglicht eine Verarbeitung in Heap-Reihenfolge
- Bevorzugen Sie ArrayList für die meisten Anwendungsfälle; LinkedList eignet sich besonders für häufige Änderungen am Anfang oder Ende
Häufig gestellte Fragen
Ist die Lektion „Interna von LinkedList“ kostenlos?
Ja — der vollständige Text von „Interna von LinkedList“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Java Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Interna von LinkedList“?
Untersuchen Sie die Struktur der doppelt verketteten Knoten von LinkedList und ihre Eigenschaften hinsichtlich der Zeitkomplexität. Du übst Java Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Java Academy zu starten?
Keine Vorkenntnisse erforderlich. Java Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Interna von LinkedList“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Java Academy-Lektion Code schreiben und ausführen?
Ja. Jede Java Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Interna von LinkedList
- Deque-Operationen: Stack und Queue
- LinkedList vs. ArrayList: Abwägungen
- PriorityQueue für geordnete Verarbeitung