Verkettete Listen#

C++ · Datenstrukturen

Voraussetzungen: Grundlegende Variablen, if, while, struct und Pointer. Die Pointer-Grundlagen aus „Zeiger, nullptr und Dereferenzieren“ werden hier nicht wiederholt.

Lernziel: Du verstehst, wie eine doppelt verkettete Liste aufgebaut ist, warum jeder Knoten zwei Verbindungen braucht und was beim Einfügen und Entfernen passiert.

1. Was ist eine verkettete Liste?#

Stell dir eine Reihe von Eisenbahnwaggons vor. Jeder Waggon hat eine Zahl und ist mit dem nächsten Waggon verbunden. Die Waggons müssen dabei nicht direkt nebeneinander im Speicher liegen.

Bei einer verketteten Liste heißen diese Waggons Knoten. Jeder Knoten speichert einen Wert und mindestens eine Verbindung zu einem anderen Knoten.

1[10] ---> [20] ---> [30]

Hier gibt es drei Knoten mit den Werten 10, 20 und 30.

Anders als bei einem Array springst du nicht einfach mit einer Position wie [2] zu einem Element. Du startest normalerweise vorne und folgst den Verbindungen, bis du beim gesuchten Knoten bist.

2. Einfach oder doppelt verkettet?#

Einfach verkettete Liste#

Jeder Knoten kennt nur seinen Nachfolger.

1Kopf2 |3 v4[10] ---> [20] ---> [30] ---> nullptr

Du kannst den Verbindungen nur vorwärts folgen.

Doppelt verkettete Liste#

Jeder Knoten kennt seinen Vorgänger und seinen Nachfolger.

1           Kopf                      Ende2            |                         |3            v                         v4nullptr <- [10] <--> [20] <--> [30] -> nullptr

Die Doppelpfeile sind eine Abkürzung: Tatsächlich sind es zwei getrennte Verbindungen, eine nach links und eine nach rechts.

3. Wie sieht ein Knoten in C++ aus?#

Mit struct können wir die drei Dinge, die zu einem Knoten gehören, zusammenfassen:

1struct Knoten {2    int wert;3    Knoten* vorher = nullptr;4    Knoten* naechster = nullptr;5};

Das bedeutet:

• wert: Hier steht unsere Zahl.

• vorher: Hier steht, welcher Knoten links daneben liegt.

• naechster: Hier steht, welcher Knoten rechts daneben liegt.

Ein neuer, noch nicht verbundener Knoten sieht so aus:

1Knoten eins{10};

1nullptr <- [10] -> nullptr

Der Wert ist 10. Beide Verbindungen sind zunächst leer.

4. Drei Knoten miteinander verbinden#

Wir legen drei Knoten an und verbinden sie zu einer doppelt verketteten Liste:

1Knoten eins{10};2Knoten zwei{20};3Knoten drei{30};4 5// 10 und 20 verbinden6eins.naechster = &zwei;7zwei.vorher = &eins;8 9// 20 und 30 verbinden10zwei.naechster = &drei;11drei.vorher = &zwei;12 13Knoten* kopf = &eins;14Knoten* ende = &drei;

1           kopf                      ende2            |                         |3            v                         v4nullptr <- [10] <--> [20] <--> [30] -> nullptr

Wichtig: Für die Verbindung zwischen 10 und 20 brauchst du beide Zeilen:

1. eins.naechster = &zwei; – Von 10 geht es weiter zu 20.

2. zwei.vorher = &eins; – Von 20 geht es zurück zu 10.

Wenn du nur die erste Zeile schreibst, funktioniert die Verbindung nicht in beide Richtungen.

kopf zeigt auf das erste Element, ende auf das letzte. So müssen wir die beiden Enden nicht jedes Mal neu suchen.

5. Die Liste durchlaufen#

Durchlaufen bedeutet: Wir gehen von Knoten zu Knoten und schauen uns die Werte an.

Vorwärts: vom Kopf bis zum Ende#

1Knoten* aktuell = kopf;2 3while (aktuell != nullptr) {4    std::cout << aktuell->wert << ' ';5    aktuell = aktuell->naechster;6}

Ausgabe:

110 20 30

So läuft die Schleife ab:

1. aktuell beginnt beim Knoten 10.

2. Wir geben den Wert aus und gehen mit naechster zu 20.

3. Dann geben wir 20 aus und gehen zu 30.

4. Nach 30 kommt nullptr. Die Schleife endet.

Rückwärts: vom Ende bis zum Kopf#

Wir ändern nur den Startpunkt und die Richtung:

1aktuell = ende;2 3while (aktuell != nullptr) {4    std::cout << aktuell->wert << ' ';5    aktuell = aktuell->vorher;6}

Ausgabe:

130 20 10

Genau dafür ist die zweite Verbindung nützlich: Wir kommen ohne erneute Suche zum vorherigen Knoten.

6. Einen Knoten in der Mitte einfügen#

Jetzt soll die 25 zwischen 20 und 30 stehen.

Vorher:

1[10] <--> [20] <--> [30]

Nachher:

1[10] <--> [20] <--> [25] <--> [30]

Dafür ändern wir vier Verbindungen: zwei am neuen Knoten und je eine bei seinen Nachbarn.

1Knoten vier{25};2 3// 1. Der neue Knoten merkt sich seine Nachbarn.4vier.vorher = &zwei;5vier.naechster = &drei;6 7// 2. Die Nachbarn werden mit dem neuen Knoten verbunden.8zwei.naechster = &vier;9drei.vorher = &vier;

7. Einen Knoten aus der Liste entfernen#

Wir wollen 25 wieder aus der Liste aushängen.

1Vorher:  [10] <--> [20] <--> [25] <--> [30]2Nachher: [10] <--> [20] <----------> [30]

Die beiden Nachbarn werden wieder direkt miteinander verbunden:

1zwei.naechster = &drei;2drei.vorher = &zwei;3 4// Optional: Der ausgehängte Knoten zeigt auf niemanden mehr.5vier.vorher = nullptr;6vier.naechster = nullptr;

Das ist alles, was wir zum Aushängen brauchen. Wir haben die Liste verändert, aber die Variable vier existiert weiterhin.

8. Die Sonderfälle: leere Liste, erster und letzter Knoten#

Bisher haben wir in der Mitte gearbeitet. Am Anfang und Ende gibt es etwas zu beachten.

Beispiel: einen Knoten vorne anhängen#

Der folgende Ausschnitt funktioniert auch bei einer leeren Liste:

1Knoten anfang{5};2 3anfang.naechster = kopf;4 5if (kopf != nullptr) {6    kopf->vorher = &anfang;7} else {8    // Die Liste war leer: Der neue Knoten ist auch das Ende.9    ende = &anfang;10}11 12kopf = &anfang;

Wenn vorher 10 <-> 20 <-> 30 in der Liste stand, ergibt sich 5 <-> 10 <-> 20 <-> 30.

1if (kopf != nullptr) {2    Knoten* alt = kopf;3    kopf = alt->naechster;4 5    if (kopf != nullptr) {6        kopf->vorher = nullptr;7    } else {8        ende = nullptr; // Die Liste ist jetzt leer.9    }10 11    alt->naechster = nullptr;12}

1if (ende != nullptr) {2    Knoten* alt = ende;3    ende = alt->vorher;4 5    if (ende != nullptr) {6        ende->naechster = nullptr;7    } else {8        kopf = nullptr; // Die Liste ist jetzt leer.9    }10 11    alt->vorher = nullptr;12}

9. Vollständiges C++-Beispiel zum Ausprobieren#

Hier ist ein komplettes Programm mit allen wichtigen Schritten. Es verwendet absichtlich normale lokale Knoten, damit du dich zuerst auf das Verbinden konzentrieren kannst. Du kannst es mit C++17 kompilieren.

1#include <iostream>2 3struct Knoten {4    int wert;5    Knoten* vorher = nullptr;6    Knoten* naechster = nullptr;7};8 9int main() {10    // 1. Drei Knoten erstellen11    Knoten eins{10};12    Knoten zwei{20};13    Knoten drei{30};14 15    // 2. In beide Richtungen verbinden16    eins.naechster = &zwei;17    zwei.vorher = &eins;18    zwei.naechster = &drei;19    drei.vorher = &zwei;20 21    Knoten* kopf = &eins;22    Knoten* ende = &drei;23 24    // 3. Vorwaerts durchlaufen25    std::cout << "Vorwaerts: ";26    Knoten* aktuell = kopf;27    while (aktuell != nullptr) {28        std::cout << aktuell->wert << ' ';29        aktuell = aktuell->naechster;30    }31    std::cout << '\n';32 33    // 4. Rueckwaerts durchlaufen34    std::cout << "Rueckwaerts: ";35    aktuell = ende;36    while (aktuell != nullptr) {37        std::cout << aktuell->wert << ' ';38        aktuell = aktuell->vorher;39    }40    std::cout << '\n';41 42    // 5. Die 25 zwischen 20 und 30 einfuegen43    Knoten vier{25};44    vier.vorher = &zwei;45    vier.naechster = &drei;46    zwei.naechster = &vier;47    drei.vorher = &vier;48 49    std::cout << "Nach Einfuegen: ";50    aktuell = kopf;51    while (aktuell != nullptr) {52        std::cout << aktuell->wert << ' ';53        aktuell = aktuell->naechster;54    }55    std::cout << '\n';56 57    // 6. Die 25 wieder aushaengen58    zwei.naechster = &drei;59    drei.vorher = &zwei;60    vier.vorher = nullptr;61    vier.naechster = nullptr;62 63    std::cout << "Nach Entfernen: ";64    aktuell = kopf;65    while (aktuell != nullptr) {66        std::cout << aktuell->wert << ' ';67        aktuell = aktuell->naechster;68    }69    std::cout << '\n';70}

1Vorwaerts: 10 20 302Rueckwaerts: 30 20 103Nach Einfuegen: 10 20 25 304Nach Entfernen: 10 20 30

10. Und wenn die Liste beliebig wachsen soll?#

Unser Lernbeispiel verwendet feste Variablen. Eine Liste, deren Größe sich erst während der Programmausführung ergibt, braucht normalerweise dynamisch erzeugte Knoten.

1Knoten* neu = new Knoten{40};

1delete neu;2neu = nullptr;

1#include <list>2 3std::list<int> zahlen{10, 20, 30};4zahlen.push_back(40);  // Hinten anhaengen5zahlen.push_front(5);  // Vorne anhaengen

11. Typische Fehler#

• Nur eine Richtung verbinden: naechster ist korrekt, aber vorher zeigt noch auf den alten Knoten.

• Ersten oder letzten Knoten vergessen: Nach dem Einfügen oder Entfernen am Rand zeigt kopf oder ende noch auf den falschen Knoten.

• Am Ende weiterlaufen: Sobald aktuell == nullptr ist, darfst du nicht mehr auf aktuell->wert zugreifen.

• Einen Knoten einfach auslassen und seine Nachbarn vergessen: Beide Nachbarn müssen bei einer doppelt verketteten Liste wieder zusammenpassen.

• Aushängen und Löschen verwechseln: Eine lokale Variable bleibt bestehen, auch wenn sie nicht mehr Teil der Liste ist. Dynamisch mit new erzeugter Speicher muss passend freigegeben werden.

12. Übungen#

Übung 1: Die Verbindungen lesen#

Gegeben ist:

1nullptr <- [4] <--> [8] <--> [12] -> nullptr

1. Welcher Knoten ist kopf, welcher ende?

2. Welchen Wert hat der Knoten hinter der 8?

3. Was ist vorher beim ersten Knoten?

Übung 2: Den fehlenden Code ergänzen#

Zwischen 10 und 20 soll eine 15 eingefügt werden. Die Knoten links und rechts sind bereits verbunden.

1Knoten mitte{15};2 3mitte.vorher = &links;4mitte.naechster = &rechts;5 6// Welche zwei Zeilen fehlen hier?

1links.naechster = &mitte;2rechts.vorher = &mitte;

Übung 3: Fehler finden#

Eine Liste endet bei 30. Wir möchten 40 hinten anhängen:

1Knoten vierzig{40};2drei.naechster = &vierzig;

Frage: Welche zwei Dinge fehlen für eine korrekte doppelt verkettete Liste mit einem ende-Pointer?

1vierzig.vorher = &drei;2ende = &vierzig;

Das Wichtigste in 30 Sekunden#

• Eine verkettete Liste besteht aus Knoten.

• Ein Knoten einer doppelt verketteten Liste kennt vorher und naechster.

• kopf zeigt auf den ersten Knoten, ende auf den letzten.

• Vorwärts: immer naechster folgen. Rückwärts: immer vorher folgen.

• Beim Einfügen in der Mitte: den neuen Knoten mit beiden Nachbarn verbinden und beide Nachbarn auf ihn umstellen.

• Beim Entfernen in der Mitte: die Nachbarn wieder direkt miteinander verbinden.

• Am Anfang oder Ende: zusätzlich kopf oder ende aktualisieren.

Wenn du nur eine Sache behältst: Bei einer doppelt verketteten Liste muss jede Verbindung in beide Richtungen stimmen.