Deutsche Lernausgabe

Doppelt verkettete Liste in C

Erhalten Sie Vorwärts- und Rückwärtsverbindungen beim Einfügen und Entfernen.

Ein Knoten besitzt next und prev und lässt sich dadurch in beide Richtungen durchlaufen. Dafür sind ein zusätzlicher Zeiger und mehr konsistente Aktualisierungen nötig.

Verbinden Sie beim Einfügen zwischen zwei Nachbarn beide Seiten und korrigieren Sie die Rückverweise. Verbinden Sie beim Löschen zuerst die Nachbarn und geben Sie dann den Knoten frei. Der erste hat keinen Vorgänger, der letzte keinen Nachfolger.

Prüfen Sie die Konsistenz durch Durchläufe in beide Richtungen. Testen Sie das Entfernen von Kopf, Ende und einzigem Knoten. Geben Sie abschließend alle Reservierungen frei.

Quellcode

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

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

DNode* insertHead(DNode *head, int val) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = val;
    newNode->prev = NULL;
    newNode->next = head;
    if (head != NULL) head->prev = newNode;
    return newNode;
}

void printForward(DNode *head) {
    DNode *curr = head;
    while (curr != NULL) {
        printf("%d <-> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

void freeDList(DNode *head) {
    DNode *curr = head;
    while (curr != NULL) {
        DNode *temp = curr;
        curr = curr->next;
        free(temp);
    }
}

int main() {
    DNode *head = NULL;
    head = insertHead(head, 300);
    head = insertHead(head, 200);
    head = insertHead(head, 100);

    printf("Doubly Linked List: ");
    printForward(head);

    freeDList(head);
    return 0;
}

Im Compiler öffnen

Erwartetes Ergebnis

Doubly Linked List: 100 <-> 200 <-> 300 <-> NULL

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.