Verkettete Liste
Zuletzt aktualisiert
Eine verkettete Liste speichert eine Folge als Kette von Knoten, wobei jeder Knoten einen Wert und einen Zeiger auf den nächsten Knoten enthält. Anders als bei einem Array liegen die Knoten nicht zusammenhängend im Speicher - man folgt den next-Zeigern, um die Liste zu durchlaufen. Drücke oben auf Abspielen, um zu sehen, wie Knoten am Kopf und am Ende verknüpft werden, wie ein Wert durch Durchlaufen der Kette gesucht und wie ein Knoten durch Umverdrahten eines Zeigers entfernt wird.
Einfügen oder Löschen am Kopf ist O(1), weil du nur den Kopf neu setzt. Eine Position in der Mitte oder das Ende zu erreichen ist O(n), weil du erst dorthin laufen musst. Dieser Kompromiss -günstige Enden, kein wahlfreier Zugriff- unterscheidet eine verkettete Liste von einem Array.
Zeitkomplexität
| Operation | Komplexität | Anmerkungen |
|---|---|---|
| Am Kopf einfügen | O(1) | Kopf neu setzen |
| Am Ende einfügen | O(n) | Erst zum Ende laufen (O(1) mit einem Endzeiger) |
| Suchen | O(n) | Den next-Zeigern folgen |
| Kopf löschen | O(1) | Kopf über ihn hinaus neu setzen |
| Zugriff per Index | O(n) | Kein wahlfreier Zugriff |
Verkettete Liste vs Array
| Aspekt | Verkettete Liste | Array |
|---|---|---|
| Speicher | Verstreute Knoten + Zeiger | Zusammenhängender Block |
| Wahlfreier Zugriff | O(n) | O(1) |
| Einfügen/Löschen am Anfang | O(1) | O(n) (Verschieben) |
| Cache-Freundlichkeit | Schlecht | Gut |
Durchgerechnetes Beispiel
Die Liste [10, 20] aufbauen, 5 voranstellen, dann 20 löschen:
| Schritt | Struktur | Aktion |
|---|---|---|
| Start | head -> null | Leere Liste |
| Am Kopf 10 einfügen | head -> 10 -> null | Kopf auf einen neuen Knoten setzen, dessen next der alte Kopf (null) ist |
| Am Ende 20 einfügen | head -> 10 -> 20 -> null | Zum Knoten 10 laufen, dessen next auf einen neuen Knoten 20 setzen |
| Am Kopf 5 einfügen | head -> 5 -> 10 -> 20 -> null | Der neue Knoten 5 zeigt auf den alten Kopf 10; der Kopf zeigt nun auf 5 |
| 20 löschen | head -> 5 -> 10 -> null | Zu 10 laufen, dessen next von 20 auf null setzen; Knoten 20 ist ausgehängt |
Wann eine verkettete Liste verwenden
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
| Du an den Enden (oder an einem gehaltenen Knoten) weit häufiger einfügst oder löschst, als du indizierst | Du schnellen wahlfreien Zugriff per Position brauchst (O(1)-Indizierung) |
| Sich die Größe stark ändert und du keine Kosten für Neuallokation/Kopieren willst | Du enge Schleifen durchläufst, in denen Cache-Lokalität die Leistung bestimmt |
| Du eine Warteschlange, einen Stapel oder eine Adjazenzliste baust | Der Speicher knapp ist - jeder Knoten kostet einen zusätzlichen Zeiger pro Element |
| Du stabile Referenzen auf Knoten brauchst, die Einfügungen anderswo überstehen | Du meist liest und selten änderst, sodass ein Array einfacher und schneller ist |
Linked List-Code
Eine saubere, lauffähige Linked List-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Linked List-Code in Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Linked List-Code in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Linked List-Code in Java
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Linked List-Code in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Linked List-Code in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}FAQ zu verketteten Listen
Was ist der Unterschied zwischen einer verketteten Liste und einem Array?
Ein Array speichert die Elemente in einem einzigen zusammenhängenden Block und bietet so
O(1)-Wahlzugriff, aber O(n)-Einfügungen/Löschungen, die Elemente verschieben. Eine verkettete Liste speichert Knoten irgendwo im Speicher, verbunden durch Zeiger, und bietet O(1)-Einfügungen/Löschungen an einer bekannten Position, aber O(n)-Zugriff, da man die Kette durchlaufen muss.Wann sollte ich eine verkettete Liste verwenden?
Verkettete Listen glänzen, wenn du häufig an den Enden (oder an einem Knoten, dessen Referenz du bereits hältst) einfügst oder entfernst und selten wahlfreien Zugriff brauchst - zum Beispiel Warteschlangen, Stapel, Adjazenzlisten und LRU-Caches. Wenn du schnellen indizierten Zugriff brauchst, ist ein Array oder dynamisches Array meist besser.
Wie ist die Zeitkomplexität einer verketteten Liste?
Einfügen oder Löschen am Kopf ist
O(1). Suchen oder das Ende ohne Endzeiger zu erreichen ist O(n), weil man den next-Zeigern einzeln folgt. Es gibt keinen O(1)-Wahlzugriff - das Indizieren in eine verkettete Liste ist O(n).Was ist der Unterschied zwischen einer einfach und einer doppelt verketteten Liste?
Eine einfach verkettete Liste speichert pro Knoten nur einen
next-Zeiger, sodass man in eine Richtung laufen kann und das Löschen eines Knotens eine Referenz auf seinen Vorgänger erfordert. Eine doppelt verkettete Liste fügt einen prev-Zeiger hinzu, was Rückwärtsdurchlauf und das O(1)-Löschen eines gehaltenen Knotens ermöglicht - zum Preis eines zusätzlichen Zeigers pro Knoten und mehr Verwaltungsaufwand bei jedem Einfügen und Löschen.Warum ist Einfügen am Ende O(n), wenn Einfügen am Kopf O(1) ist?
Einfügen am Kopf verdrahtet nur den
head-Zeiger neu, was konstante Arbeit ist. Das Ende zu erreichen bedeutet, den next-Zeigern vom Kopf bis zum Ende zu folgen, was O(n) ist. Ein separater tail-Zeiger macht auch das Einfügen am Ende O(1), weshalb reale Listen oft beide Enden verfolgen.Haben verkettete Listen überall O(1)-Einfügung?
Nein - das ist ein verbreiteter Irrtum. Das Einfügen selbst ist nur dann
O(1), wenn du bereits einen Zeiger auf den Knoten hältst, nach dem du einfügst. Diese Position per Wert oder Index zu finden kostet weiterhin O(n), weil du die Kette durchlaufen musst, um dorthin zu gelangen.Verwandte Ressourcen
Mehr Visualisierungen
