Was ist eine verkettete Liste?
Eine verkettete Liste besteht aus Knoten, und jeder Knoten kennt nur seinen Nachfolger. Damit fügen Sie mitten in einer Folge Werte ein oder löschen sie, ohne andere Werte zu verschieben.
Denken Sie an eine Schnitzeljagd: Jeder Zettel nennt nur den Ort des nächsten. Ein Zettel lässt sich leicht dazwischenlegen. Zettel Nummer 50 finden Sie aber nur über alle davor.
Am Ende dieser Lektion
Notiz
Ich kann eine verkettete Liste aufbauen und durchlaufen.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Knoten | ein Stück der Liste mit einem Wert und einem Verweis |
| Verweis | die Angabe, welcher Knoten als Nächstes kommt |
| Kopf | der erste Knoten der Liste |
| None | kein Knoten, also das Ende der Liste |
| Durchlaufen | Knoten für Knoten dem Verweis folgen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Knoten hält einen Wert und einen Verweis
Wir bauen einen Knoten als Wörterbuch (dictionary) mit zwei Einträgen: wert und weiter. weiter zeigt auf den nächsten Knoten. Beim letzten Knoten ist es None, also kein Knoten. Die Liste kennt nur ihren Kopf. Alle anderen Knoten erreichen Sie über die Verweise.
Knoten bauen und durchlaufen
# Drei Knoten von hinten nach vorn bauen und dann durchlaufen.
c = {"wert": 8, "weiter": None}
b = {"wert": 5, "weiter": c}
a = {"wert": 3, "weiter": b}
kopf = a
aktuell = kopf
while aktuell is not None:
print(aktuell["wert"])
aktuell = aktuell["weiter"]
# Aendern Sie den Wert von c auf 9 und fuehren Sie erneut aus.
Verweisen von Hand folgen
Der Befehl baut dieselben drei Knoten in einer Zeile. Dann folgt er von a aus zweimal dem Verweis weiter und gibt den Wert dort aus. Der zweite Befehl hängt an einen Knoten einen Nachfolger an.
Zweimal dem Verweis folgen
python3 -c "c = {'wert': 8, 'weiter': None}; b = {'wert': 5, 'weiter': c}; a = {'wert': 3, 'weiter': b}; print(a['weiter']['weiter']['wert'])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Einen Nachfolger anhängen
python3 -c "k = {'wert': 1, 'weiter': None}; k['weiter'] = {'wert': 2, 'weiter': None}; print(k['weiter']['wert'])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Einfügen ändert nur zwei Verweise
Um nach dem Knoten b einen neuen Knoten n einzufügen, setzen Sie zwei Verweise. Zuerst zeigt n auf den Nachfolger von b. Dann zeigt b auf n. Die Reihenfolge ist wichtig, sonst geht der Rest der Liste verloren. Das Löschen von n setzt nur den Verweis davor um.
Beispiel: die 6 zwischen 5 und 8
| Schritt | Verweis | Kette danach |
|---|---|---|
| Start | Keiner | 3, 5, 8 |
| 1 | n zeigt auf den Nachfolger von b (die 8) | 3, 5, 8 und 6 zeigt auf 8 |
| 2 | b zeigt auf n | 3, 5, 6, 8 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Einen Knoten dazwischen einhängen
# Die 6 hinter den Knoten b einhaengen.
c = {"wert": 8, "weiter": None}
b = {"wert": 5, "weiter": c}
kopf = {"wert": 3, "weiter": b}
n = {"wert": 6, "weiter": None}
n["weiter"] = b["weiter"] # zuerst den Rest merken
b["weiter"] = n # dann den neuen Knoten einhaengen
aktuell = kopf
while aktuell is not None:
print(aktuell["wert"])
aktuell = aktuell["weiter"]
# Loeschen Sie die Zeile mit der Notiz zuerst den Rest merken und fuehren Sie aus.
Array und verkettete Liste im Vergleich
| Aufgabe | Array | Verkettete Liste |
|---|---|---|
| Wert mit Nummer i lesen | Ein Schritt | i Schritte |
| Einfügen an bekannter Stelle | Viele Werte verschieben | Zwei Verweise ändern |
| Einfügen am Anfang | Alle Werte verschieben | Neuer Kopf |
| Speicher | Plätze direkt nebeneinander | Knoten verstreut, Verweise kosten Platz |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Umdrehen biegt jeden Verweis um
Zum Umdrehen laufen Sie einmal durch die Liste. Bei jedem Knoten biegen Sie den Verweis nach hinten. Dafür brauchen Sie drei Namen: vorher, aktuell und naechster. Sie merken sich den Nachfolger, biegen den Verweis um und rücken weiter. Am Ende ist vorher der neue Kopf.
Beispiel: 3, 5, 8 umdrehen
| Runde | Knoten | Verweis danach | Kette bis hier |
|---|---|---|---|
| 1 | 3 | Zeigt auf None | 3 |
| 2 | 5 | Zeigt auf 3 | 5, 3 |
| 3 | 8 | Zeigt auf 5 | 8, 5, 3 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele denken, beim Einfügen genüge es, b auf n zeigen zu lassen. Dann verliert die Liste alles hinter b, denn niemand kennt die 8 mehr. Setzen Sie zuerst den Verweis des neuen Knotens und danach den des Vorgängers.