Doppelt verkettete Liste

Q: Was ist der Unterschied zwischen einer einfach und einer doppelt verketteten Liste?

Eine einfach verkettete Liste hat einen Zeiger pro Knoten (`next`), sodass du dich nur vorwärts bewegen kannst. Eine doppelt verkettete Liste fügt einen `prev`-Zeiger hinzu, was Rückwärtstraversierung und das Löschen eines Knotens, auf den du eine Referenz hältst, in `O(1)` ermöglicht, um den Preis eines zusätzlichen Zeigers pro Knoten und der Aktualisierung zweier Verknüpfungen bei jeder Änderung.

Q: Doppelt verkettete Liste oder Array: was sollte ich verwenden?

Verwende ein Array, wenn du `O(1)`-Zugriff über Index und cachefreundliche Iteration brauchst und Einfügungen meist am Ende erfolgen. Verwende eine doppelt verkettete Liste, wenn du bei vorhandener Knotenreferenz häufig in der Mitte oder an beiden Enden einfügst oder entfernst, da das `O(1)` gegenüber dem `O(n)`-Verschieben eines Arrays ist. Arrays gewinnen bei Speicher und Lokalität; die Liste gewinnt bei strukturellen Änderungen.

Q: Was ist der häufigste Fehler beim Löschen aus einer doppelt verketteten Liste?

Zu vergessen, `head` oder `tail` zu aktualisieren, wenn du den ersten oder letzten Knoten löschst, was einen hängenden Zeiger auf einen freigegebenen Knoten hinterlässt. Prüfe immer, ob `node.prev` gleich `null` ist (`head` aktualisieren) oder ob `node.next` gleich `null` ist (`tail` aktualisieren), bevor du die Nachbarn neu verdrahtest.

Zuletzt aktualisiert 1. Juli 2026

Eine doppelt verkettete Liste ist eine verkettete Liste, bei der jeder Knoten zwei Zeiger hält: next (zum folgenden Knoten) und prev (zum vorhergehenden). Dieser zusätzliche Rückwärtsverweis erlaubt es, in beide Richtungen zu traversieren und einen Knoten in O(1) zu löschen, wenn man bereits eine Referenz auf ihn hat, weil man seinen Vorgänger direkt erreichen kann, statt vom Kopf aus zu laufen. Drücke oben auf Wiedergabe, um zu sehen, wie Knoten in beide Richtungen verknüpft und neu verknüpft werden.

Der Preis ist ein zusätzlicher Zeiger pro Knoten und mehr Verwaltungsaufwand: Jedes Einfügen und Löschen muss sowohl next als auch prev bei den Nachbarn aktualisieren. Es ist die Struktur hinter vielen Deques und LRU-Caches, wo schnelles Entfernen an beiden Enden zählt.

Zeitkomplexität

Operation	Komplexität	Anmerkungen
Einfügen am Kopf/Ende	O(1)	Mit Kopf- und Endzeigern
Bekannten Knoten löschen	O(1)	Erreicht prev direkt, kein Durchlaufen
Suche	O(n)	Weiterhin linearer Scan
Zugriff über Index	O(n)	Kein wahlfreier Zugriff

Einfach vs. doppelt verkettete Liste

Aspekt	Einfach	Doppelt
Zeiger pro Knoten	1 (next)	2 (next + prev)
Rückwärts traversieren	Nein	Ja
Bekannten Knoten löschen	O(n) (prev suchen)	O(1)
Speicheraufwand	Geringer	Höher

Durchgerechnetes Beispiel

Aufbau von [10, 20, 30] durch Anhängen, dann Löschen von Knoten 20:

Schritt	Struktur	Aktion
Start	`null`	Leere Liste: `head` und `tail` sind beide `null`
10 anhängen	`10`	Erster Knoten; `head` und `tail` zeigen darauf, `prev` = `next` = `null`
20 anhängen	`10 <-> 20`	Setze `10.next = 20` und `20.prev = 10`; `tail` = `20`
30 anhängen	`10 <-> 20 <-> 30`	Setze `20.next = 30` und `30.prev = 20`; `tail` = `30`
20 löschen	`10 <-> 30`	Mit `20.prev` und `20.next`: setze `10.next = 30` und `30.prev = 10` in `O(1)`

Wann eine doppelt verkettete Liste verwenden

Verwenden, wenn	Vermeiden, wenn
Du in beide Richtungen traversieren oder einfügen musst	Du dich nur vorwärts bewegst: eine einfache Liste ist leichter
Du beliebige Knoten löschst, auf die du bereits eine Referenz hältst (`O(1)`)	Du meist über Position indizierst: nutze ein Array für `O(1)`-Zugriff
Du einen Deque, LRU-Cache oder Rückgängig-Verlauf implementierst	Der Speicher knapp ist: der zusätzliche `prev`-Zeiger verdoppelt den Verknüpfungsaufwand
Einfügungen und Entfernungen häufig an beiden Enden geschehen	Die Daten klein sind und sich selten ändern: Array-Kopien sind günstiger

Doubly Linked List-Code

Eine saubere, lauffähige Doubly Linked List-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.

Doubly Linked List-Code in PythonPython
1class Node:2    def __init__(self, value):3        self.value = value4        self.prev = None5        self.next = None6
7
8class DoublyLinkedList:9    def __init__(self):10        self.head = None11        self.tail = None12
13    def append(self, value):14        node = Node(value)15        if self.tail is None:16            self.head = self.tail = node17            return18        # Wire both directions: old tail <-> new node19        node.prev = self.tail20        self.tail.next = node21        self.tail = node22
23    def prepend(self, value):24        node = Node(value)25        if self.head is None:26            self.head = self.tail = node27            return28        node.next = self.head29        self.head.prev = node30        self.head = node31
32    def forward(self):33        values, current = [], self.head34        while current:35            values.append(current.value)36            current = current.next37        return values38
39    def backward(self):40        values, current = [], self.tail41        while current:42            values.append(current.value)43            current = current.prev44        return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49    lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())
Führe diesen Code im Python-Playground aus

Doubly Linked List-Code in JavaScriptJavaScript
1class Node {2    constructor(value) {3        this.value = value;4        this.prev = null;5        this.next = null;6    }7}8
9class DoublyLinkedList {10    constructor() {11        this.head = null;12        this.tail = null;13    }14
15    // Tail pointer makes append O(1)16    append(value) {17        const node = new Node(value);18        if (!this.tail) {19            this.head = node;20            this.tail = node;21            return;22        }23        node.prev = this.tail;24        this.tail.next = node;25        this.tail = node;26    }27
28    forward() {29        const out = [];30        for (let n = this.head; n; n = n.next) out.push(n.value);31        return out;32    }33
34    backward() {35        const out = [];36        for (let n = this.tail; n; n = n.prev) out.push(n.value);37        return out;38    }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));
Führe diesen Code im JavaScript-Playground aus

Doubly Linked List-Code in JavaJava
1public class Main {2    static class Node {3        int value;4        Node prev, next;5        Node(int value) { this.value = value; }6    }7
  static Node head, tail;9
  static void append(int value) {11        Node node = new Node(value);12        if (head == null) { head = tail = node; return; }13        node.prev = tail;14        tail.next = node;15        tail = node;16    }17
  // Unlink in O(1) once found: fix both neighbor pointers19    static void delete(int value) {20        for (Node cur = head; cur != null; cur = cur.next) {21            if (cur.value != value) continue;22            if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23            if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24            return;25        }26    }27
  public static void main(String[] args) {29        append(1);30        append(2);31        append(3);32        append(4);33
      StringBuilder forward = new StringBuilder("Forward:");35        for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36        System.out.println(forward);37
      StringBuilder backward = new StringBuilder("Backward:");39        for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40        System.out.println(backward);41
      delete(3);43        StringBuilder after = new StringBuilder("After delete 3:");44        for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45        System.out.println(after);46    }47}
Führe diesen Code im Java-Playground aus

Doubly Linked List-Code in C++C++
1#include <iostream>2
3struct Node {4    int value;5    Node* prev = nullptr;6    Node* next = nullptr;7    explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11    Node* head = nullptr;12    Node* tail = nullptr;13
14    void append(int value) {15        Node* node = new Node(value);16        if (tail == nullptr) {17            head = tail = node;18            return;19        }20        node->prev = tail;  // link both directions21        tail->next = node;22        tail = node;23    }24
25    void prepend(int value) {26        Node* node = new Node(value);27        if (head == nullptr) {28            head = tail = node;29            return;30        }31        node->next = head;32        head->prev = node;33        head = node;34    }35
36    void printForward() const {37        for (Node* cur = head; cur != nullptr; cur = cur->next) {38            std::cout << cur->value << " <-> ";39        }40        std::cout << "null\n";41    }42
43    void printBackward() const {44        for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45            std::cout << cur->value << " <-> ";46        }47        std::cout << "null\n";48    }49};50
51int main() {52    DoublyLinkedList list;53    for (int value : {10, 20, 30}) list.append(value);54    list.prepend(5);55    std::cout << "Forward:  ";56    list.printForward();57    std::cout << "Backward: ";58    list.printBackward();59    return 0;60}
Führe diesen Code im C++-Playground aus

Doubly Linked List-Code in CC
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value;6    struct Node* prev;7    struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14    Node* n = calloc(1, sizeof(Node));15    n->value = value;16    return n;17}18
19void append(int value) {20    Node* node = newNode(value);21    if (tail == NULL) {22        head = tail = node;23        return;24    }25    node->prev = tail;  // link both directions26    tail->next = node;27    tail = node;28}29
30void prepend(int value) {31    Node* node = newNode(value);32    if (head == NULL) {33        head = tail = node;34        return;35    }36    node->next = head;37    head->prev = node;38    head = node;39}40
41void printForward(void) {42    for (Node* cur = head; cur != NULL; cur = cur->next) {43        printf("%d <-> ", cur->value);44    }45    printf("NULL\n");46}47
48void printBackward(void) {49    for (Node* cur = tail; cur != NULL; cur = cur->prev) {50        printf("%d <-> ", cur->value);51    }52    printf("NULL\n");53}54
55int main(void) {56    int values[] = {10, 20, 30};57    for (int i = 0; i < 3; i++) append(values[i]);58    prepend(5);59    printf("Forward:  ");60    printForward();61    printf("Backward: ");62    printBackward();63    return 0;64}
Führe diesen Code im C-Playground aus

FAQ zu doppelt verketteten Listen

Was ist der Unterschied zwischen einer einfach und einer doppelt verketteten Liste?

Eine einfach verkettete Liste hat einen Zeiger pro Knoten (next), sodass du dich nur vorwärts bewegen kannst. Eine doppelt verkettete Liste fügt einen prev-Zeiger hinzu, was Rückwärtstraversierung und das Löschen eines Knotens, auf den du eine Referenz hältst, in O(1) ermöglicht, um den Preis eines zusätzlichen Zeigers pro Knoten und der Aktualisierung zweier Verknüpfungen bei jeder Änderung.

Wann lohnt sich der zusätzliche Speicher einer doppelt verketteten Liste?

Wenn du Rückwärtstraversierung oder das Löschen beliebiger, bereits referenzierter Knoten in O(1) brauchst - klassische Fälle sind Deques (doppelendige Warteschlangen) und LRU-Caches, in denen Einträge häufig an beiden Enden verschoben und verdrängt werden.

Warum kann eine doppelt verkettete Liste einen Knoten in O(1) löschen?

Um einen Knoten zu entfernen, musst du seinen Vorgänger mit seinem Nachfolger verbinden. In einer einfach verketteten Liste müsstest du vom Kopf aus laufen, um den Vorgänger zu finden (O(n)); in einer doppelt verketteten Liste liefert der prev-Zeiger des Knotens den Vorgänger direkt, sodass das Neuverknüpfen O(1) ist.

Doppelt verkettete Liste oder Array: was sollte ich verwenden?

Verwende ein Array, wenn du O(1)-Zugriff über Index und cachefreundliche Iteration brauchst und Einfügungen meist am Ende erfolgen. Verwende eine doppelt verkettete Liste, wenn du bei vorhandener Knotenreferenz häufig in der Mitte oder an beiden Enden einfügst oder entfernst, da das O(1) gegenüber dem O(n)-Verschieben eines Arrays ist. Arrays gewinnen bei Speicher und Lokalität; die Liste gewinnt bei strukturellen Änderungen.

Was ist ein Wächterknoten (Sentinel) in einer doppelt verketteten Liste?

Ein Wächter- oder Dummy-Knoten ist ein Platzhalter vor dem Kopf und/oder nach dem Ende, sodass die Liste nie wirklich leer ist. Er beseitigt die null-Prüfungen für head, tail und Rand-Einfügungen/-Löschungen und lässt jede Operation demselben Neuverknüpfungspfad folgen. Viele produktive LRU-Cache-Implementierungen nutzen zwei Wächter, um die Enden nicht als Sonderfälle behandeln zu müssen.

Was ist der häufigste Fehler beim Löschen aus einer doppelt verketteten Liste?

Zu vergessen, head oder tail zu aktualisieren, wenn du den ersten oder letzten Knoten löschst, was einen hängenden Zeiger auf einen freigegebenen Knoten hinterlässt. Prüfe immer, ob node.prev gleich null ist (head aktualisieren) oder ob node.next gleich null ist (tail aktualisieren), bevor du die Nachbarn neu verdrahtest.