Mit Google fortfahren
Verkettete Listen: Aufbau und Laufzeiten
Eine verkettete Liste speichert geordnete Daten in einzelnen Knoten. Jeder Knoten verweist auf den nächsten Knoten; deshalb müssen die Knoten nicht nebeneinander im Speicher liegen. Du kannst eine Liste dynamisch vergrößern, erreichst eine bestimmte Position aber nur durch schrittweises Durchlaufen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Was macht eine verkettete Liste aus?
Stell dir die Zahlenfolge 7, 4, 9 als Kette vor:
Kopf → 7 → 4 → 9 → NULL
Der Kopf ist der gespeicherte Zugang zum ersten Knoten. NULL kennzeichnet hier das Ende der Liste.
Knoten
Ein Knoten enthält Nutzdaten und mindestens einen Verweis. In einer einfach verketteten Liste zeigt dieser Verweis auf den nächsten Knoten.
Die Reihenfolge entsteht durch die Verweise, nicht durch benachbarte Speicherplätze. Der Knoten mit 7 kann daher an einer ganz anderen Speicherstelle liegen als der Knoten mit 4.
Eine leere Liste besitzt keinen Datenknoten. Ihr Kopf verweist unmittelbar auf NULL. Bei einer Liste mit genau einem Datenknoten zeigt der Kopf auf diesen Knoten und dessen Nachfolger auf NULL.
Wie fügst du einen Knoten ein?
In die Liste 7 → 4 → NULL soll der Wert 5 zwischen 7 und 4 eingefügt werden.
- Erzeuge den neuen Knoten
5. - Setze den Nachfolger von
5auf den bisherigen Nachfolger von7, also auf4. - Setze anschließend den Nachfolger von
7auf5.
Das Ergebnis lautet: 7 → 5 → 4 → NULL.
Die Reihenfolge der Änderungen ist entscheidend. Würdest du zuerst den Verweis von 7 überschreiben, könntest du den Zugang zu 4 und zum restlichen Listenteil verlieren.
Am Anfang ist kein Vorgängerknoten vorhanden. Deshalb wird zuerst der Nachfolger des neuen Knotens auf den bisherigen ersten Knoten gesetzt. Danach wird der Kopf auf den neuen Knoten umgestellt.
Beim Einfügen sicherst du zuerst den Zugang zum bisherigen Nachfolger. Erst danach leitest du den Vorgänger oder den Kopf auf den neuen Knoten um.
Wie funktionieren Suchen und Löschen?
Beim Suchen beginnst du am Kopf. Du vergleichst nacheinander die Nutzdaten jedes erreichbaren Knotens mit dem gesuchten Wert. Die Suche endet bei einem Treffer oder bei NULL.
Um in 7 → 5 → 4 → NULL den Knoten 5 zu löschen, brauchst du bei einfacher Verkettung seinen Vorgänger 7.
Der Nachfolger von 7 wird nicht mehr auf 5, sondern direkt auf den Nachfolger von 5 gesetzt. Dieser ist 4.
Vorher: 7 → 5 → 4 → NULL
Nachher: 7 → 4 → NULL
Der Knoten 5 ist nun vom Kopf aus nicht mehr erreichbar.
Das Löschen des ersten Knotens ist ein Randfall: Es gibt keinen vorherigen Datenknoten. Stattdessen wird der Kopf auf den zweiten Knoten gesetzt. War nur ein Knoten vorhanden, zeigt der Kopf danach auf NULL.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Beim Suchen beginnt der Durchlauf am . Zum Löschen eines mittleren Knotens wird sein mit dem Nachfolger verbunden. Beim Löschen des ersten Knotens muss der angepasst werden.
Welche Laufzeiten gelten wirklich?
Die Schreibweise O(1) bedeutet, dass die Zahl der nötigen Schritte nicht mit der Listenlänge wächst. O(n) bedeutet, dass im ungünstigsten Fall eine Zahl von Schritten nötig ist, die mit der Anzahl n der Elemente wächst.
Für eine einfach verkettete Liste gelten wichtige Bedingungen:
- Einfügen am Anfang:
O(1). - Einfügen hinter einem bereits bekannten Knoten:
O(1)für die Verweisänderungen. - Suchen eines Wertes: im ungünstigsten Fall
O(n). - Zugriff auf eine Position:
O(n), weil die Liste vom Anfang durchlaufen werden muss. - Anhängen ohne gespeicherten Endezeiger:
O(n), weil zuerst das Ende gesucht wird. - Anhängen mit aktuellem Endezeiger:
O(1). - Löschen hinter einem bereits bekannten Vorgänger:
O(1)für das Überbrücken.
Die Aussage „Einfügen und Löschen dauern O(1)“ ist nur dann vollständig, wenn der benötigte Vorgänger oder Einfügepunkt schon bekannt ist. Muss er zuerst gesucht werden, kann der gesamte Vorgang O(n) dauern.
Welche Varianten gibt es?
Bei einer doppelt verketteten Liste enthält jeder Datenknoten einen Nachfolger- und einen Vorgängerverweis. Du kannst die Liste deshalb vorwärts und rückwärts durchlaufen.
Liegt bereits eine Referenz auf einen zu löschenden mittleren Knoten vor, sind auch seine beiden Nachbarn unmittelbar erreichbar. Diese können direkt miteinander verbunden werden. Dafür benötigt jeder Knoten zusätzlichen Speicher, und beim Verändern müssen mehr Verweise konsistent bleiben.
Bei einer kreisförmig verketteten Liste verweist der letzte Knoten wieder auf den ersten. NULL markiert dann nicht das Ende. Ein festgelegter Kopf oder Wächter ist nötig, damit der Anfang und das Ende eines vollständigen Durchlaufs erkennbar bleiben.
Ein Wächterknoten enthält keine normalen Nutzdaten. Er kann Randfälle vereinheitlichen, etwa das Einfügen oder Löschen am Anfang. Algorithmen müssen ihn jedoch ausdrücklich von Datenknoten unterscheiden.
Eine gültige doppelt verkettete Liste muss in beide Richtungen zusammenpassen: Zeigt A vorwärts auf B, muss B rückwärts auf A zeigen.
Wann passt eine Liste besser als ein Array?
Ein Array bietet direkten Zugriff über einen Index. Ein Element an einer bekannten Position ist deshalb in O(1) erreichbar. Beim Einfügen oder Löschen in der Mitte müssen jedoch möglicherweise viele Elemente verschoben werden.
Eine verkettete Liste verschiebt keine Nutzdaten. Sie passt besonders dann, wenn die Elementzahl veränderlich ist und häufig an bereits bekannten Stellen eingefügt oder gelöscht wird. Für häufige Zugriffe wie „Gib mir Element 800“ ist sie meist ungeeignet, weil der Weg am Kopf beginnt.
| Anforderung | Häufig passende Struktur | Begründung |
|---|---|---|
| häufiger Zugriff über einen Index | Array | direkter Zugriff in O(1) |
| häufiges Einfügen hinter einem bekannten Knoten | verkettete Liste | lokale Verweisänderung in O(1) |
| häufige Vorwärts- und Rückwärtsläufe | doppelt verkettete Liste | beide Richtungen sind gespeichert |
| dynamische Folge mit schnellem Anhängen | Liste mit Endezeiger | letzter Knoten ist direkt bekannt |
Die Begriffe Liste und verkettete Liste sind nicht immer gleichbedeutend: Eine Liste kann als abstrakter Datentyp durch ihre erlaubten Operationen beschrieben werden. Eine konkrete Bibliothek kann diese Operationen intern durch ein Array oder durch verkettete Knoten umsetzen.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Verkettete Liste
- Aufbau
- Kopf
- Knoten mit Nutzdaten und Verweis
- Listenende oder Kreisverbindung
- Operationen
- Suchen durch schrittweises Durchlaufen
- Einfügen durch sichere Verweisreihenfolge
- Löschen durch Überbrücken
- Varianten
- einfach verkettet
- doppelt verkettet
- kreisförmig verkettet
- Auswahl
- dynamisches Wachstum
- kein direkter Indexzugriff
- Laufzeit hängt von bekannten Referenzen ab
- Aufbau
Abschluss-Check
Wenn du alle drei Abschlussfragen begründen kannst, verstehst du nicht nur den Aufbau der Liste, sondern auch die entscheidenden Bedingungen hinter ihren Laufzeiten.