Implementierung einer doppelt verketteten Liste in C

Einführung

In diesem Projekt lernst du, wie du eine doppelt verkettete Liste als Datenstruktur in C implementierst. Eine doppelt verkettete Liste ist eine Art von verketteter Liste, bei der jeder Knoten Zeiger auf seinen Vorgänger- und Nachfolgerknoten enthält, was eine effiziente Durch traversierung in beiden Richtungen ermöglicht.

👀 Vorschau

$ gcc test_list.c list.c -o test
$./test
willkommen
zu
labex
online

🎯 Aufgaben

In diesem Projekt wirst du lernen:

• Wie du eine doppelt verkettete Liste initialisierst
• Wie du die doppelt verkettete Liste traversierst und für jeden Knoten eine Callback-Funktion ausführst
• Wie du einen neuen Knoten hinter einem angegebenen Knoten in der doppelt verketteten Liste einfügst
• Wie du einen neuen Knoten vor einem angegebenen Knoten in der doppelt verketteten Liste einfügst
• Wie du einen Knoten aus der doppelt verketteten Liste löschst

🏆 Errungenschaften

Nach Abschluss dieses Projekts wirst du in der Lage sein:

• Das grundlegende Struktur und die Operationen einer doppelt verketteten Liste zu verstehen
• Die Kernfunktionen für das Verwalten einer doppelt verketteten Liste zu implementieren
• Die Fähigkeit zu demonstrieren, mit Zeigern und dynamischer Arbeitsspeicherzuweisung in C umzugehen
• Dein Wissen anzuwenden, um die bereitgestellte Implementierung der doppelt verketteten Liste zu beheben und zu verbessern

Skills Graph

Fehler bei der Adressierung von Speicherbereichen (Segmentation Faults) beheben

In diesem Schritt aktualisiert die Funktion free_list den Zeiger current nicht, nachdem ein Knoten freigegeben wurde. Dies führt zu einem Fehler bei der Adressierung von Speicherbereichen (Segmentation Fault). Der Fehler muss nun behoben werden.

1. Locate the free_list() function in the list.c file.
2. Hier ist die aktualisierte Funktion free_list():

void free_list(struct List* list) {
    struct Node* current = list->head;
    struct Node* next = NULL;

    while (current) {
        next = current->next;
        free(current);
        current = next; // Aktualisiert
    }
    free(list);
}

Füge einen Knoten hinter einem angegebenen Knoten ein

In diesem Schritt wirst du lernen, wie du einen neuen Knoten hinter einem angegebenen Knoten in der doppelt verketteten Liste einfügst.

1. Locate the insert_after() function in the list.c file.
2. Diese Funktion nimmt einen Zeiger struct List*, einen Zeiger struct Node* (der Knoten, hinter dem der neue Knoten eingefügt werden soll), und die data für den neuen Knoten entgegen.
3. Die Funktion sollte einen neuen struct Node erstellen und sein data-Feld mit der bereitgestellten data initialisieren.
4. Die Funktion sollte dann die next- und prev-Zeiger des neuen Knotens und des prev-Knotens aktualisieren, um den neuen Knoten korrekt einzufügen.
5. Schließlich sollte die Funktion den tail-Zeiger aktualisieren, wenn der neue Knoten am Ende der Liste eingefügt wird.

Hier ist die aktualisierte insert_after()-Funktion:

void insert_after(struct List* list, struct Node* prev, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (prev) { // Aktualisiert
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // Aktualisiert
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // Aktualisiert
        list->head = newnode;
    }
}

6. Locate insert_after (list, NULL, data); und ändere es in den folgenden Code:

insert_after (list, list->tail, data);

Füge einen Knoten vor einem angegebenen Knoten ein

In diesem Schritt wirst du lernen, wie du einen neuen Knoten vor einem angegebenen Knoten in der doppelt verketteten Liste einfügst.

1. Locate the insert_before() function in the list.c file.
2. Diese Funktion nimmt einen Zeiger struct List*, einen Zeiger struct Node* (der Knoten, vor dem der neue Knoten eingefügt werden soll), und die data für den neuen Knoten entgegen.
3. Die Funktion sollte einen neuen struct Node erstellen und sein data-Feld mit der bereitgestellten data initialisieren.
4. Die Funktion sollte dann die next- und prev-Zeiger des neuen Knotens und des next-Knotens aktualisieren, um den neuen Knoten korrekt einzufügen.
5. Schließlich sollte die Funktion den head-Zeiger aktualisieren, wenn der neue Knoten am Anfang der Liste eingefügt wird.

Hier ist die aktualisierte insert_before()-Funktion:

void insert_before(struct List* list, struct Node* next, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (next) { // Aktualisiert
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // Aktualisiert
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // Aktualisiert
        list->tail = newnode;
    }
}

6. Locate insert_before (list, NULL, data); und ändere es in den folgenden Code:

insert_before (list, list->head, data);

Entferne einen Knoten aus der doppelt verketteten Liste

In diesem Schritt wirst du lernen, wie du einen Knoten aus der doppelt verketteten Liste entfernest.

1. Locate the delete_from() function in the list.c file.
2. Diese Funktion nimmt einen Zeiger struct List* und einen Zeiger struct Node* (den Knoten, der entfernt werden soll).
3. Die Funktion sollte die next- und prev-Zeiger der benachbarten Knoten aktualisieren, um den angegebenen Knoten aus der Liste zu entfernen.
4. Die Funktion sollte auch die head- und tail-Zeiger aktualisieren, wenn der gelöschte Knoten der head oder tail der Liste war.
5. Schließlich sollte die Funktion den von dem gelöschten Knoten belegten Speicher freigeben.

Hier ist die aktualisierte delete_from()-Funktion:

void delete_from(struct List* list, struct Node* node) {
    if (node->prev) node->prev->next = node->next;
    else list->head = node->next; // Aktualisiert

    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev; // Aktualisiert

    free(node);
}

Jetzt sollte die Implementierung der doppelt verketteten Liste in der Datei list.c korrekt funktionieren. Du kannst die bereitgestellte Datei test_list.c verwenden, um die Funktionalität der doppelt verketteten Liste zu testen. Die Testergebnisse lauten wie folgt:

$ gcc test_list.c list.c -o test
$./test
willkommen
zu
labex
online

Zusammenfassung

Herzlichen Glückwunsch! Du hast dieses Projekt abgeschlossen. Du kannst in LabEx weitere Übungen absolvieren, um deine Fähigkeiten zu verbessern.