Datenstruktur - Doppelt verkettete Liste
Eine doppelt verkettete Liste (Doubly Linked List) ist eine Erweiterung einer einfach verketteten Liste. Zusätzlich zum Zeiger auf den nächsten Knoten speichert jeder Knoten auch einen Zeiger auf den vorherigen Knoten und bildet so eine Kettenstruktur, die in beide Richtungen erreichbar ist.
Aufbau und Eigenschaften der doppelt verketteten Liste
struct Node { int data; struct Node* prev; struct Node* next; };
prev zeigt auf den vorherigen Knoten | data speichert Daten | next zeigt auf den nächsten Knoten
Kernvorteile: Sie können jeden Knoten direkt löschen (der Vorgänger muss nicht gespeichert werden), und es unterstützt bidirektionale Traversierung
Wie in der obigen Abbildung gezeigt, hat jeder Knoten einer doppelt verketteten Listeprevundnextzwei Zeiger.
In der Sprache C lautet die Definition eines Knotens einer doppelt verketteten Liste wie folgt:
Beispiel
int data; /* Datenfeld */
struct Node* prev; /* Vorgängerzeiger: zeigt auf den vorherigen Knoten */
struct Node* next; /* Nachfolgerzeiger: zeigt auf den nächsten Knoten */
};
Im Vergleich zu einer einfach verketteten Liste ist der größte Vorteil einer doppelt verketteten Liste, dass Sie von jedem Knoten aus direkt auf seinen Vorgänger und Nachfolger zugreifen können, was bedeutet, dass beim Löschvorgang keine zusätzliche Referenz auf den Vorgängerknoten gespeichert werden muss.
In einer einfach verketteten Liste müssen Sie, um einen bestimmten Knoten zu löschen, seinen Vorgängerknoten kennen, um die Zeigeranpassung durchzuführen. In einer doppelt verketteten Liste kann der Löschvorgang direkt durchgeführt werden, da jeder Knoten selbst einen prev-Zeiger speichert.
Grundlegende Operationen
Einfügeoperation
Das Einfügen in eine doppelt verkettete Liste erfordert das Anpassen der prev/next-Zeiger des neuen Knotens sowie der Zeiger des vorhergehenden und des nachfolgenden Knotens, wobei insgesamt vier Zeiger angepasst werden.
Beispiel
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
/* Neuen Knoten erstellen */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
/* Einen Knoten am Kopf einfügen Schritte: Der next-Zeiger des neuen Knotens zeigt auf den ursprünglichen Kopfknoten, und der prev-Zeiger des ursprünglichen Kopfknotens zeigt auf den neuen Knoten */
/* Der neue Knoten wird zum neuen Kopfknoten */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head != NULL) {
newNode->next = head;
head->prev = newNode;
}
return newNode; /* Einen neuen Knoten nach einem angegebenen Knoten einfügen Sie müssen 4 Zeiger bearbeiten: 1-2: prev und next des neuen Knotens 3: prev des Nachfolgerknotens (falls vorhanden) 4: next des Vorgängerknotens */
}
/* Der next-Zeiger des neuen Knotens zeigt auf den ursprünglichen Nachfolger */
/* Der prev-Zeiger des neuen Knotens zeigt auf den Vorgänger */
/* Der prev-Zeiger des ursprünglichen Nachfolgers zeigt auf den neuen Knoten */
/* Das next des Vorgängers zeigt auf den neuen Knoten */
Löschoperation
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) return;
struct Node* newNode = createNode(value);
newNode->next = prevNode->next; Beispiel
newNode->prev = prevNode; /* Einen bestimmten Knoten löschen (der Vorgängerknoten muss nicht bekannt sein; das ist der größte Vorteil einer doppelt verketteten Liste) Schritte: die vorherigen und nächsten Knoten miteinander verbinden, den aktuellen Knoten überspringen und dann den aktuellen Knoten freigeben */
if (prevNode->next != NULL) {
prevNode->next->prev = newNode; /* Wenn der Kopfknoten gelöscht wird, aktualisiere den Kopfzeiger */
}
prevNode->next = newNode; /* Den next-Zeiger des Vorgängerknotens auf den Nachfolgerknoten zeigen lassen */
}
Löschoperation
Beispiel
Eine doppelt verkettete Liste unterstützt zwei Traversierungsmethoden: vorwärts und rückwärts.
void deleteNode(struct Node** headRef, struct Node* del) {
if (*headRef == NULL || del == NULL) return;
Beispiel
if (*headRef == del) {
*headRef = del->next;
}
/* Vorwärtsdurchlauf: vom head starten, entlang der next-Richtung gehen */
if (del->prev != NULL) {
del->prev->next = del->next;
}
"Vorwärtsdurchlauf: "
if (del->next != NULL) {
del->next->prev = del->prev;
}
free(del); /* Rückwärtsdurchlauf: vom tail starten, entlang der prev-Richtung gehen Zuerst muss der tail-Knoten gefunden werden */
}
Traversierungsoperation (bidirektional)
/* Vom tail aus entlang der prev-Richtung zum head zurückkehren */
Beispiel
/* Vorwärtsdurchlauf: beim Kopf beginnen, entlang der next-Richtung */
void traverseForward(struct Node* head) {
printf(Vorwärtsdurchlauf:);
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
/* Rückwärtsdurchlauf: vom Ende, entlang der prev-Richtung
Zuerst muss der Endknoten gefunden werden */
void traverseBackward(struct Node* head) {
if (head == NULL) return;
/* Zuerst zum letzten Knoten (d. h. dem Ende) gehen */
struct Node* cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
/* Vom Ende zurück zum Kopf entlang der prev-Richtung */
printf("Rückwärtsdurchlauf: ");
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->prev;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
/* Verkettete Liste erstellen: 10 <-> 20 <-> 30 */
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverseForward(head); /* Ausgabe: Vorwärtsdurchlauf: 10 20 30 */
traverseBackward(head); /* Ausgabe: Rückwärtsdurchlauf: 30 20 10 */
return 0;
}
Doppelt verkettete Liste vs. einfach verkettete Liste
| Vergleichsdimension | Einfach verkettete Liste | Doppelt verkettete Liste |
|---|---|---|
| Knotenstruktur | data + next | data + prev + next |
| Zusätzlicher Speicher pro Knoten | 8 bytes (64-Bit-System) | 16 Bytes (64-Bit-System) |
| Vorwärts-Traversierung | Unterstützt | Unterstützt |
| Rückwärts-Traversierung | Nicht unterstützt | Unterstützt |
| Node löschen | Vorgängerknoten muss bekannt sein | Kein Vorgängerknoten nötig, direktes Löschen möglich |
| Einfügeoperation | 1~2 Zeiger anpassen | 4 Zeiger anpassen |