# Doubly Linked Lists Quelle: https://dev.inf.zone/exercises/09/doublylinkedlist/ ## Aufgabe **Auf einen Blick** - **Was:** Ein Programm, das eine doppelt verkettete Liste (engl. *doubly linked list*) aus ganzen Zahlen verwaltet. Der Benutzer wählt die Operationen über ein Menü. - **Datei:** `doublylinkedlist.c` in einem Ordner `doublylinkedlist`. Ausgangspunkt ist das Codegerüst unten: Es enthält nur das Menü. - **Eingabe:** eine Menünummer (`> `), bei Einfügen, Suchen und Löschen danach eine Zahl. - **Ausgabe:** je nach Menüpunkt die Liste vorwärts oder rückwärts, das Ergebnis einer Suche oder Löschung. - **Ihre Arbeit:** die Struktur `node`, die Pointer `head` und `tail`, die sechs Funktionen `insert_end`, `search`, `delete_value`, `print_forward`, `print_backward` und `clear_list` sowie ihre Aufrufe in `main`. **Wozu das Ganze?** Sie üben Pointer, dynamische Speicherverwaltung mit `malloc` und `free` und den Entwurf einer Datenstruktur. In der nächsten Aufgabe, [Stack mit Doubly Linked List](https://dev.inf.zone/exercises/09/stack/), bauen Sie mit denselben Bausteinen einen Stack. ### So funktioniert eine doppelt verkettete Liste 1. **Knoten:** Die Liste besteht aus Knoten. Jeder Knoten speichert einen Wert (`value`), einen Pointer auf den nächsten Knoten (`next`) und einen auf den vorherigen (`prev`). 2. **Enden:** `head` zeigt auf den ersten Knoten, `tail` auf den letzten. Beim ersten Knoten ist `prev` `NULL`, beim letzten ist `next` `NULL`. In einer leeren Liste sind `head` und `tail` `NULL`. 3. **Durchlaufen:** Vorwärts geht es von `head` über `next` bis `NULL`, rückwärts von `tail` über `prev` bis `NULL`. 4. **Einfügen am Ende:** Der neue Knoten bekommt `prev = tail` und `next = NULL`. War die Liste leer, wird er zu `head`, sonst zeigt der bisher letzte Knoten mit `next` auf ihn. Danach zeigt `tail` auf den neuen Knoten. 5. **Löschen:** Vorgänger und Nachfolger des Knotens werden direkt verbunden: `next` des Vorgängers zeigt auf den Nachfolger, `prev` des Nachfolgers auf den Vorgänger. Fehlt der Vorgänger (erster Knoten), wird der Nachfolger zu `head`; fehlt der Nachfolger (letzter Knoten), wird der Vorgänger zu `tail`. Danach geben Sie den Knoten mit `free` frei. 6. **Speicher:** Jeder Knoten, der mit `malloc` angelegt wurde, wird genau einmal mit `free` freigegeben. **Beispiel:** Nach dem Einfügen von 4, 7 und 10 sieht die Liste so aus (`head` → 4, `tail` → 10): | Knoten | `prev` | `next` | | ------ | ------ | ------ | | 4 | `NULL` | 7 | | 7 | 4 | 10 | | 10 | 7 | `NULL` | Löschen von 7 (Knoten in der Mitte): `next` von 4 zeigt jetzt auf 10, `prev` von 10 auf 4; Knoten 7 wird freigegeben. `head` und `tail` bleiben, wie sie sind. | Knoten | `prev` | `next` | | ------ | ------ | ------ | | 4 | `NULL` | 10 | | 10 | 4 | `NULL` | Vorwärts ausgegeben ergibt das `4 10`, rückwärts `10 4`. Würde man anschließend 4 löschen (den ersten Knoten), wäre 10 der einzige Knoten: `head` und `tail` zeigen beide auf 10, dessen `prev` und `next` sind `NULL`. ## Demo So sieht ein Lauf des fertigen Programms aus (hinter `> ` und den Fragen stehen die Eingaben): ```text $ ./doublylinkedlist (1) Zahl einfügen (2) Liste vorwärts ausgeben (3) Liste rückwärts ausgeben (4) Wert suchen (5) Wert löschen (6) gesamte Liste löschen (0) Programm beenden > 1 Zahl: 5 > 1 Zahl: 9 > 2 Vorwärts: 5 9 > 3 Rückwärts: 9 5 > 4 Wert suchen: 9 9 wurde gefunden. > 5 Wert löschen: 5 5 gelöscht. > 2 Vorwärts: 9 > 0 Programm beendet. ``` ## Aufgabenmaterial Für diese Aufgabe werden Sie ein von uns zur Verfügung gestelltes Codegerüst vervollständigen. Legen Sie einen Ordner `doublylinkedlist` an und darin die Datei `doublylinkedlist.c` mit diesem Inhalt: **Codegerüst** ```c #include #include #include #include int main(void) { // Menü nur einmal ausgeben printf( "(1) Zahl einfügen\n" "(2) Liste vorwärts ausgeben\n" "(3) Liste rückwärts ausgeben\n" "(4) Wert suchen\n" "(5) Wert löschen\n" "(6) gesamte Liste löschen\n" "(0) Programm beenden\n" ); while (true) { // Benutzerauswahl abfragen int choice = get_int("> "); // Operationen auswerten switch (choice) { case 1: // Zahl einfügen break; case 2: // Liste vorwärts ausgeben break; case 3: // Liste rückwärts ausgeben break; case 4: // Wert suchen break; case 5: // Wert löschen break; case 6: // gesamte Liste löschen break; case 0: // gesamte Liste löschen printf("Programm beendet.\n"); return 0; default: printf("Ungültige Auswahl. Bitte erneut versuchen.\n"); } } } ``` ## Spezifikation **Datenstruktur.** Definieren Sie die Struktur `node` und zwei globale Pointer auf den ersten und den letzten Knoten: ```c typedef struct node { int value; struct node *next; struct node *prev; } node; node *head = NULL; // zeigt auf den ersten Knoten node *tail = NULL; // zeigt auf den letzten Knoten ``` **Funktionen.** Die Funktionen geben selbst nur dort etwas aus, wo es in der Tabelle steht; alle anderen Meldungen gibt `main` aus. | Funktion | Aufgabe | | -------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | `void insert_end(int value)` | Legt mit `malloc` einen neuen Knoten an und hängt ihn ans Ende der Liste (Regel 4), auch wenn die Liste leer ist. | | `bool search(int value)` | Durchläuft die Liste ab `head` und gibt `true` zurück, wenn `value` darin vorkommt, sonst `false`. Gibt nichts aus. | | `bool delete_value(int value)` | Löscht den ersten Knoten (von `head` aus) mit diesem Wert (Regel 5) und gibt `true` zurück. Kommt der Wert nicht vor, bleibt die Liste unverändert, Rückgabe `false`. | | `void print_forward(void)` | Gibt `Vorwärts: ` aus, dann die Werte von `head` bis `tail`, durch Leerzeichen getrennt, dann einen Zeilenumbruch. | | `void print_backward(void)` | Wie `print_forward`, aber mit `Rückwärts: ` und von `tail` bis `head`. | | `void clear_list(void)` | Gibt alle Knoten mit `free` frei und setzt `head` und `tail` auf `NULL`. | Beim Löschen müssen diese Fälle stimmen: Der Knoten ist der einzige, der erste, der letzte oder einer in der Mitte der Liste – oder der Wert kommt gar nicht vor. **Menü.** `main` gibt das Menü einmal aus und fragt dann immer wieder mit `> ` nach einer Auswahl: | Auswahl | Eingabe | Ausgabe | | ------- | ------------------ | ----------------------------------------------------------- | | `1` | `Zahl: ` | – | | `2` | – | `Vorwärts: 5 9` | | `3` | – | `Rückwärts: 9 5` | | `4` | `Wert suchen: ` | `9 wurde gefunden.` oder `9 nicht in der Liste.` | | `5` | `Wert löschen: ` | `5 gelöscht.` oder `5 nicht gefunden.` | | `6` | – | `Liste geleert.` | | `0` | – | `Programm beendet.` – vorher wird die Liste freigegeben | | sonst | – | `Ungültige Auswahl. Bitte erneut versuchen.` | Die Zahlen in der Ausgabe sind Beispiele; eingesetzt wird jeweils der eingegebene Wert. ## Hilfestellung Klicken Sie auf die folgenden Tipps, um einige Ratschläge zu erhalten. Versuchen Sie aber zunächst, selbst so weit wie möglich zu kommen. **Wo stehen `node`, `head`, `tail` und die Prototypen?** Schreiben Sie die Struktur `node`, die globalen Pointer `head` und `tail` und die Prototypen der sechs Funktionen über `main`. Die Funktionen selbst können dann unter `main` stehen: ```c void insert_end(int value); bool search(int value); bool delete_value(int value); void print_forward(void); void print_backward(void); void clear_list(void); ``` Wenn Sie in einem `case` eine Variable anlegen (etwa `int value = get_int("Zahl: ");`), setzen Sie den Inhalt des `case` in geschweifte Klammern `{ … }`. Sonst meldet der Compiler einen Fehler. **Die Liste durchlaufen** `search`, `delete_value` und die beiden Ausgabefunktionen folgen demselben Muster: Ein Hilfs-Pointer startet an einem Ende und springt so lange weiter, bis er `NULL` ist. ```c for (node *current = head; current != NULL; current = current->next) { // current->value verarbeiten } ``` Rückwärts starten Sie bei `tail` und springen über `current->prev`. Wie das mit einfach verketteten Listen aussieht, zeigt das Short [Verkettete Listen](https://dev.inf.zone/lectures/5-datenstrukturen/short-5-2-verkettete-listen/). **Implementierung von `delete_value`** Suchen Sie den Knoten wie in `search`. Haben Sie ihn gefunden (`current`), prüfen Sie beide Seiten getrennt: - Hat `current` einen Vorgänger (`current->prev != NULL`), dann bekommt dieser als `next` den Nachfolger von `current`. Sonst ist `current` der erste Knoten, und `head` wird zum Nachfolger. - Hat `current` einen Nachfolger, dann bekommt dieser als `prev` den Vorgänger von `current`. Sonst ist `current` der letzte Knoten, und `tail` wird zum Vorgänger. Diese zwei Prüfungen decken alle vier Fälle ab: Beim einzigen Knoten greifen beide „sonst“-Zweige, und `head` und `tail` werden `NULL`. Geben Sie `current` erst **danach** mit `free` frei und beenden Sie die Funktion mit `return true`. **Implementierung von `clear_list`** Nach `free(current)` dürfen Sie `current->next` nicht mehr lesen. Merken Sie sich den Nachfolger deshalb vorher: ```c node *current = head; while (current != NULL) { node *next = current->next; free(current); current = next; } ``` Vergessen Sie nicht, `head` und `tail` danach auf `NULL` zu setzen – sonst zeigen sie auf freigegebenen Speicher. ## Testen Stellen Sie beim Testen Ihres Codes sicher, dass dieser mit folgenden Szenarien umgehen kann: - Ausgabe einer leeren Liste (vorwärts und rückwärts: nur `Vorwärts: ` bzw. `Rückwärts: `) - Einfügen mehrerer Zahlen; vorwärts und rückwärts stehen dieselben Zahlen in umgekehrter Reihenfolge - Suchen eines vorhandenen und eines nicht vorhandenen Werts - Löschen des ersten, des letzten, eines mittleren und des einzigen Knotens; danach jeweils vorwärts **und** rückwärts ausgeben – so fallen falsch gesetzte `prev`-Pointer auf - Löschen eines Werts, der nicht in der Liste steht - Löschen der gesamten Liste (`6`) und danach erneutes Einfügen - eine ungültige Menünummer ### Korrektheit Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen: ```bash check50 -l inf-zone/exercises/2026/doublylinkedlist ``` ### Speicher Ob Ihr Programm allen Speicher freigibt, zeigt `valgrind` (siehe [Vorlesung 4](https://dev.inf.zone/lectures/4-memory/notes4/)). Fügen Sie ein paar Zahlen ein, löschen Sie einige und beenden Sie das Programm mit `0`: ```bash valgrind ./doublylinkedlist ``` ### Style Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit `style50` zu analysieren: ```bash style50 doublylinkedlist.c ``` ## Abgeben Geben Sie im Ordner `doublylinkedlist` ab: ```bash inf upload doublylinkedlist ``` Danach sehen Sie, welche Tests Ihr Programm besteht und ob die Übung für die Bonuspunkte zählt. Wie Sie `inf` installieren und sich anmelden, steht unter [Abgeben mit `inf`](https://dev.inf.zone/faq/uebung-solutions/#inf-installieren).