Datenstruktur - Verkettete Liste
Eine verkettete Liste (Linked List) ist eine lineare Datenstruktur, die aus mehreren Knoten besteht, die sequenziell durch Zeiger verbunden sind.
Im Gegensatz zu Arrays müssen die Elemente in einer verketteten Liste nicht zusammenhängend im Speicher abgelegt werden.
Grundlegende Konzepte der verketteten Liste und Knotenstruktur
Jeder Knoten einer verketteten Liste enthält zwei Teile:Datenfeld (data)Speichert die tatsächlichen Daten;Zeigerfeld (next)Zeigt auf den nächsten Knoten.
Die obige Abbildung zeigt das tatsächliche Erscheinungsbild einer verketteten Liste im Speicher. Jeder Knoten wirdmallocunabhängig auf dem Heap zugewiesen, sodass sie im Speicher nicht zusammenhängend sein können. Knoten werden durchnextZeiger verbunden, und der next-Zeiger des letzten Knotens zeigt auf NULL, um das Ende der verketteten Liste anzuzeigen.
In C werden Knoten einer verketteten Liste mithilfe einer Struktur definiert:
Beispiel
#include <stdlib.h> /* malloc, free */
/* Knotenstruktur einer verketteten Liste
data: Datenfeld, speichert ganzzahlige Daten
next: Zeigerfeld, zeigt auf den nächsten Knoten desselben Typs */
struct Node {
int data;
struct Node* next;
};
/* Einen neuen Knoten erstellen
Parameterwert: der Datenwert des Knotens
Rückgabewert: Zeiger auf den neuen Knoten, gibt NULL zurück, wenn die Allokation fehlschlägt */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Speicherallokation fehlgeschlagen\n");
return NULL;
}
newNode->data = value; /* Daten setzen */
newNode->next = NULL; /* next des neuen Knotens auf NULL initialisieren */
return newNode;
}
struct Node* nextist eine selbstreferenzielle Struktur, d. h., das struct enthält einen Zeiger auf ein struct desselben Typs. Dies ist die Kerntechnik zum Aufbau aller verketteten Datenstrukturen (verkettete Listen, Bäume, Graphen).
Grundlegende Operationen einer einfach verketteten Liste
Erstellen einer verketteten Liste und Traversierung
Beispiel
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Alle Knoten der verketteten Liste durchlaufen und ausgeben
Beim Kopfknoten beginnen und jeden Knoten entlang der next-Zeiger bis NULL besuchen */
void traverse(struct Node* head) {
struct Node* current = head; /* Vom Kopf aus starten */
printf("Inhalt der verketteten Liste: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next; /* Zum nächsten Knoten wechseln */
}
printf("NULL\n");
}
/* Eine verkettete Liste mit n Knoten erstellen (1, 2, 3, ..., n) */
struct Node* createList(int n) {
if (n <= 0) return NULL;
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = NULL;
struct Node* tail = head; /* tail zeigt immer auf den letzten Knoten */
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = NULL;
tail->next = newNode; /* Den neuen Knoten mit dem Ende der verketteten Liste verbinden */
tail = newNode; /* tail-Zeiger aktualisieren */
}
return head;
}
int main() {
struct Node* head = createList(5);
traverse(head);
/* Ausgabe: Inhalt der verketteten Liste: 1 -> 2 -> 3 -> 4 -> 5 -> NULL */
return 0;
}
Einfügeoperation
Die obige Abbildung zeigt den vollständigen Prozess der Zeigeränderungen beim Einfügen und Löschen in einer verketteten Liste. Das Verständnis der Reihenfolge der Zeigeranpassungen ist entscheidend: Wenn die Reihenfolge falsch ist, kann dies dazu führen, dass die verkettete Liste bricht oder Speicherlecks entstehen.
Beispiel
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Einen neuen Knoten am Kopf der verketteten Liste einfügen (head-Einfügung)
Zeitkomplexität: O(1)
Rückgabewert: Zeiger auf den neuen head-Knoten */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = head; /* Der neue Knoten zeigt auf den ursprünglichen head-Knoten */
return newNode; /* Der neue Knoten wird der neue Kopfknoten */
}
/* Einen neuen Knoten am Ende der verketteten Liste einfügen (tail-Einfügung)
Zeitkomplexität: O(n), erfordert das Durchlaufen bis zum Ende */
struct Node* insertAtTail(struct Node* head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
return newNode; /* Leere verkettete Liste, der neue Knoten wird zum Kopfknoten */
}
struct Node* current = head;
while (current->next != NULL) {
current = current->next; /* Bis zum letzten Knoten durchlaufen */
}
current->next = newNode; /* Der Endknoten zeigt auf den neuen Knoten */
return head;
}
/* Einen neuen Knoten nach der angegebenen Position einfügen
Zeitkomplexität: O(n), erfordert, zuerst prevNode zu finden */
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) {
printf("Vorgängerknoten darf nicht null sein\n");
return;
}
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
/* Wichtig: Zuerst muss der neue Knoten auf seinen Nachfolger zeigen, dann muss der Vorgänger auf den neuen Knoten zeigen */
newNode->next = prevNode->next;
prevNode->next = newNode;
}
void printList(struct Node* head) {
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
head = insertAtHead(head, 30); /* Verkettete Liste: 30 */
head = insertAtHead(head, 20); /* Verkettete Liste: 20 -> 30 */
head = insertAtHead(head, 10); /* Verkettete Liste: 10 -> 20 -> 30 */
printf("Nach dem Einfügen am Kopf: "); printList(head); /* Ausgabe: 10 20 30 */
head = insertAtTail(head, 40); /* Verkettete Liste: 10 -> 20 -> 30 -> 40 */
printf("Nach dem Einfügen am Ende: "); printList(head); /* Ausgabe: 10 20 30 40 */
insertAfter(head->next, 25); /* 25 nach 20 einfügen */
printf("Nach dem Einfügen in der Mitte: "); printList(head);
/* Ausgabe: 10 20 25 30 40 */
return 0;
}
Löschoperation
Beispiel
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Kopfknoten der verketteten Liste löschen
Zeitkomplexität: O(1)
Rückgabewert: Zeiger auf den neuen head-Knoten */
struct Node* deleteHead(struct Node* head) {
if (head == NULL) return NULL;
struct Node* temp = head; /* Alten Kopfknoten speichern */
head = head->next; /* Kopfzeiger auf den nächsten Knoten verschieben */
free(temp); /* Speicher des alten Kopfknotens freigeben */
return head;
}
/* Ersten Knoten in der verketteten Liste mit Wert target löschen
Zeitkomplexität: O(n), erfordert Durchlaufen, um den Zielknoten zu finden */
struct Node* deleteByValue(struct Node* head, int target) {
if (head == NULL) return NULL;
/* Sonderfall: Der Zielwert befindet sich am Kopfknoten */
if (head->data == target) {
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}
/* Durchlaufen, um den Vorgängerknoten des Zielknotens zu finden */
struct Node* current = head;
while (current->next != NULL && current->next->data != target) {
current = current->next;
}
/* Zielknoten finden und löschen */
if (current->next != NULL) {
struct Node* temp = current->next;
current->next = current->next->next; /* Den Zielknoten überspringen */
free(temp); /* Speicher des Zielknotens freigeben */
}
return head;
}
void printList(struct Node* head) {
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main() {
/* Verkettete Liste aufbauen: 10 -> 20 -> 30 -> 40 */
struct Node* head = NULL;
int vals[] = {10, 20, 30, 40};
for (int i = 3; i >= 0; i--) {
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->data = vals[i];
n->next = head;
head = n;
}
printf("Ursprüngliche verkettete Liste: "); printList(head); /* Ausgabe: 10 20 30 40 */
head = deleteHead(head);
printf("Nach dem Löschen des Kopfes: "); printList(head); /* Ausgabe: 20 30 40 */
head = deleteByValue(head, 30);
printf("Nach dem Löschen von 30: "); printList(head); /* Ausgabe: 20 40 */
return 0;
}
Bei der Löschoperation einer verketteten Liste,
free()ist entscheidend. Wenn Sie nur Zeiger anpassen, ohne den Speicher des gelöschten Knotens freizugeben, führt dies zu einem Speicherleck. In der Sprache C muss jedermallocein entsprechendes habenfree。
Vergleich: verkettete Liste vs. Array
| Vergleichsdimension | Array | Verkettete Liste |
|---|---|---|
| Speicherlayout | Zusammenhängender Speicher | Verstreuter Speicher, verbunden über Zeiger |
| Wahlfreier Zugriff | O(1) | O(n) |
| Einfügen/Löschen am Kopf | O(n) | O(1) |
| Einfügen/Löschen am Ende | O(1) | O(1) (mit Endzeiger) / O(n) (ohne Endzeiger) |
| Einfügen/Löschen in der Mitte | O(n) | O(1)(bekannte Position) |
| Speicher-Overhead | Nur Daten | Daten + Zeiger (8 zusätzliche Bytes pro Knoten (64-Bit)) |
| Cache-Freundlichkeit | Hoch(räumliche Lokalität) | Niedrig(Knoten verstreut) |
| Kapazität | Fest (statisches Array) | Dynamisches Wachstum |
Das Verständnis dieses Trade-offs ist eine der Kernfähigkeiten bei der Auswahl von Datenstrukturen.
Wenn die Datengröße vor der Laufzeit bekannt ist und sich nicht häufig ändert und häufiger wahlfreier Zugriff erforderlich ist, ist ein Array die bessere Wahl.
Wenn sich die Datengröße häufig ändert und ihr Umfang unsicher ist, sind dynamische Strukturen wie verkettete Listen flexibler.
Weitere Erweiterungen