Doubly Linked Lists

Aufgabe

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):

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.

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):

$ ./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:

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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:

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.

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:

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.

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);

for (node *current = head; current != NULL; current = current->next)
{
    // current->value verarbeiten
}

node *current = head;
while (current != NULL)
{
    node *next = current->next;
    free(current);
    current = next;
}

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:

check50 -l inf-zone/exercises/2026/doublylinkedlist

Speicher

Ob Ihr Programm allen Speicher freigibt, zeigt valgrind (siehe Vorlesung 4). Fügen Sie ein paar Zahlen ein, löschen Sie einige und beenden Sie das Programm mit 0:

valgrind ./doublylinkedlist

Style

Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit style50Prüfprogramm von CS50, das zeigt, wo Ihr Code von den Formatierungsregeln abweicht. In Grün zeigt es, was Sie ergänzen sollten, in Rot, was wegfallen soll. Glossar → zu analysieren:

style50 doublylinkedlist.c

Abgeben

Geben Sie im Ordner doublylinkedlist ab:

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.