0Pricing
C Academy · Lektion

Doppelt verkettete Listen

Verknüpfungen in beide Richtungen

Doppelt verkettete Listen ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Zweiwege-Verknüpfungen

Eine doppelt verkettete Liste gibt jedem Knoten zwei Zeiger: einen auf den next-Knoten und einen auf den prev- bzw. vorherigen Knoten.

Dadurch können Sie die Liste in beide Richtungen durchlaufen, und das Löschen wird einfacher.

#include <stdio.h>

struct Node {
    int value;
    struct Node *prev;
    struct Node *next;
};

int main(void) {
    printf("Each node links forward and backward\n");
    return 0;
}

Den Knoten definieren

Die Struktur ergänzt neben next einen prev-Zeiger. An den Enden der Liste sind beide NULL.

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

struct Node { int value; struct Node *prev; struct Node *next; };

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 1; n->prev = NULL; n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Eine Hilfsfunktion zum Erstellen

Wie zuvor zentralisiert eine Hilfsfunktion die Speicherreservierung. Sie setzt sowohl prev als auch next auf NULL.

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

struct Node { int value; struct Node *prev; struct Node *next; };

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v; n->prev = NULL; n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(42);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Knoten in beide Richtungen verknüpfen

Beim Verbinden zweier Knoten müssen Sie beide Richtungen aktualisieren: den next-Zeiger des ersten Knotens und den prev-Zeiger des zweiten Knotens.

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b;
    b->prev = a;
    printf("forward %d, back %d\n", a->next->value, b->prev->value);
    free(a); free(b);
    return 0;
}

Am Anfang einfügen

Beim Einfügen am Anfang zeigt next des neuen Knotens auf den alten Kopf, prev des alten Kopfes auf den neuen Knoten, und anschließend wird der Kopf auf den neuen Knoten gesetzt.

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void push(struct Node **head, int v) {
    struct Node *n = make(v);
    n->next = *head;
    if (*head) (*head)->prev = n;
    *head = n;
}

int main(void) {
    struct Node *head = NULL;
    push(&head, 2); push(&head, 1);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

Vorwärts durchlaufen

Das Vorwärtsdurchlaufen funktioniert genauso wie bei einer einfach verketteten Liste: Folgen Sie next, bis Sie NULL erreichen.

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    for (struct Node *p = a; p; p = p->next) printf("%d ", p->value);
    printf("\n");
    free(a); free(b);
    return 0;
}

Rückwärts durchlaufen

Der große Vorteil: Von jedem Knoten aus können Sie durch Folgen der prev-Zeiger rückwärts laufen, bis Sie den Kopf erreichen.

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    for (struct Node *p = c; p; p = p->prev) printf("%d ", p->value);
    printf("\n");
    free(a); free(b); free(c);
    return 0;
}

Löschen ist einfacher

Da jeder Knoten seinen Vorgänger kennt, können Sie ihn löschen, ohne den vorherigen Knoten suchen zu müssen.

Verbinden Sie einfach node->prev und node->next in beide Richtungen miteinander.

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void del(struct Node **head, struct Node *n) {
    if (n->prev) n->prev->next = n->next; else *head = n->next;
    if (n->next) n->next->prev = n->prev;
    free(n);
}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next=b; b->prev=a; b->next=c; c->prev=b;
    struct Node *head = a;
    del(&head, b);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

Beide Nachbarn aktualisieren

Beim Entfernen eines Knotens müssen Sie immer den next-Zeiger des vorherigen Knotens und den prev-Zeiger des folgenden Knotens korrigieren.

Prüfen Sie an beiden Enden auf NULL, damit Sie nicht auf einen fehlenden Nachbarn zugreifen.

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    a->next = NULL;
    free(b);
    printf("now only %d remains\n", a->value);
    free(a);
    return 0;
}

Einen Endzeiger speichern

Viele doppelt verkettete Listen speichern zusätzlich einen tail-Zeiger auf den letzten Knoten. Dadurch werden Anhängen und rückwärts gerichtetes Durchlaufen vom Ende aus mit O(1) möglich.

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

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1), *tail = head;
    struct Node *n = make(2);
    tail->next = n; n->prev = tail; tail = n;
    printf("tail = %d\n", tail->value);
    free(head); free(n);
    return 0;
}

Abwägungen

Doppelt verkettete Listen benötigen zusätzlichen Speicher (einen weiteren Zeiger pro Knoten) und erfordern bei jeder Änderung die Aktualisierung von zwei Verknüpfungen.

Dafür erhalten Sie ein Durchlaufen in beide Richtungen sowie das Löschen eines bekannten Knotens in O(1). Wählen Sie die passende Variante entsprechend Ihren Anforderungen.

#include <stdio.h>

int main(void) {
    printf("Singly: less memory, one-way\n");
    printf("Doubly: more memory, two-way + easy delete\n");
    return 0;
}

Kurztest

Testen Sie Ihr Verständnis doppelt verketteter Listen.

Zusammenfassung

Sie haben doppelt verkettete Listen gelernt:

  • Jeder Knoten besitzt sowohl prev- als auch next-Zeiger.
  • Beim Verknüpfen müssen beide Richtungen aktualisiert werden.
  • Sie können vorwärts und rückwärts durchlaufen sowie einen bekannten Knoten in O(1) löschen.
  • Der Preis dafür sind zusätzlicher Speicher und mehr Zeigeraktualisierungen; ein tail-Zeiger ermöglicht Anhängen in O(1).

Häufig gestellte Fragen

Ist die Lektion „Doppelt verkettete Listen“ kostenlos?

Ja — der vollständige Text von „Doppelt verkettete Listen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Doppelt verkettete Listen“?

Verknüpfungen in beide Richtungen Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C Academy zu starten?

Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.

Wie lange dauert die Lektion „Doppelt verkettete Listen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?

Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Einfach verkettete Listen
  2. Einfügen und Löschen
  3. Durchlaufen und Suchen
  4. Doppelt verkettete Listen
← Zurück zu C Academy