Linked Lists
Linked List = Liste verketteter Knoten. Jeder Knoten kennt den nächsten (oder beide Nachbarn bei Doubly-Linked).
Singly: A → B → C → D → null Doubly: null ← A ⇄ B ⇄ C ⇄ D → null
Komplexität
| Operation | Big-O | vs. Array |
|---|---|---|
| Zugriff Index | O(n) | schlechter |
| Einfügen am Anfang | O(1) | besser |
| Einfügen vor bekanntem Knoten | O(1) | besser |
| Löschen bekannter Knoten | O(1) | besser |
| Suchen Wert | O(n) | gleich |
Implementierung (TS)
class Node<T> {
constructor(public value: T, public next: Node<T> | null = null) {}
}
class LinkedList<T> {
head: Node<T> | null = null;
prepend(v: T) {
this.head = new Node(v, this.head); // O(1)
}
find(v: T): Node<T> | null {
let n = this.head;
while (n && n.value !== v) n = n.next; // O(n)
return n;
}
}Wann Linked List?
- Häufig am Anfang einfügen / löschen
- Größe extrem dynamisch
- Implementierung von Queue, LRU-Cache, Undo-History
Wann NICHT?
- Random Access nötig (Index-Zugriff teuer)
- Cache-Effizienz wichtig (Knoten verstreut im Speicher)
- In der Praxis sind Arrays oft schneller, auch wo theoretisch Linked List schneller wäre — wegen Cache
Zurück zu Informatik