Eine verkettete Liste (englisch Linked List) ist eine lineare Datenstruktur, deren Elemente nicht nebeneinander im Speicher liegen, sondern als Knoten organisiert sind. Jeder Knoten enthält die eigentlichen Daten und einen Zeiger auf den nächsten Knoten. Dadurch lässt sich die Liste zur Laufzeit beliebig erweitern und verkürzen — ein häufiger Gegenentwurf zum Array.
Aufbau und Varianten
Der erste Knoten heißt Kopf (Head); der letzte zeigt auf einen leeren Verweis (null) und markiert damit das Ende. Es gibt drei klassische Varianten:
- Einfach verkettete Liste: Jeder Knoten zeigt nur auf den Nachfolger.
- Doppelt verkettete Liste: Jeder Knoten zeigt zusätzlich auf den Vorgänger — Rückwärtslaufen ist damit in O(1) möglich.
- Zyklische Liste: Der letzte Knoten zeigt wieder auf den Kopf; nützlich für Ringpuffer.
Die Verbindungen zwischen den Knoten sind Pointer (Zeiger): statt Daten zu kopieren, wird nur die Adresse des nächsten Knotens gespeichert.
Stärken und Schwächen
- Einfügen und Löschen: An einer bekannten Position kostet das nur das Umhängen von Zeigern — O(1). Beim Array müssten dagegen alle nachfolgenden Elemente verschoben werden (O(n)).
- Zugriff: Es gibt keinen Indexzugriff wie beim Array. Um das k-te Element zu finden, muss die Liste vom Kopf aus durchlaufen werden — O(n).
- Speicher: Jeder Knoten trägt zusätzlich zum Datum einen oder zwei Zeiger. Dafür wächst die Liste ohne Reservierung großer Blöcke.
Damit sind verkettete Listen ideal, wenn häufig eingefügt oder gelöscht wird und ein wahlfreier Zugriff selten gebraucht wird.
Typische Anwendungen
- Grundlage für Stack und Queue: LIFO- und FIFO-Verhalten lassen sich mit Listen direkt abbilden.
- Adjazenzlisten in Graphen: Für jeden Knoten speichert eine Liste seine Nachbarn.
- Speicherverwaltung: Freispeicherlisten (Free Lists) verwalten freie Speicherblöcke.
- Kollisionsbehandlung in Hash-Tabellen (Separate Chaining).
- Undo-Funktionen, bei denen die Reihenfolge der Aktionen durchlaufen wird.
Beim Durchlaufen einer Liste fallen natürlicherweise Rekursion und Iteratoren als Werkzeuge an: Rekursive Funktionen verarbeiten „Knoten und Rest“, Iteratoren kapseln den Lauf durch die Knoten.
Verwandte Grundlagen: Array, Pointer, Datentyp, Hash-Tabelle.