Technologie

Wie implementiere ich eine verkettete Liste in C?

Melden
  1. Definition des Knotens
  2. Initialisierung der Liste
  3. Einfügen eines Knotens am Anfang
  4. Einfügen eines Knotens am Ende
  5. Löschen eines Knotens
  6. Ausgabe der Liste
  7. Beispiel für die Nutzung der verketteten Liste
  8. Speicherfreigabe

Eine verkettete Liste ist eine grundlegende Datenstruktur, bei der jeder Knoten auf den nächsten Knoten verweist. Im Gegensatz zu Arrays ist die Größe einer verketteten Liste dynamisch und kann während der Laufzeit angepasst werden. Im Folgenden wird eine einfache einfach verkettete Liste mit Einfügungs- und Löschoperationen in C beschrieben und implementiert.

Definition des Knotens

In C definiert man einen Knoten der verketteten Liste mittels eines struct. Jeder Knoten enthält mindestens zwei Elemente: die Daten (z. B. eine Ganzzahl) und einen Zeiger auf den nächsten Knoten.

typedef struct Node { int data; // gespeicherte Daten struct Node* next; // Zeiger auf den nächsten Knoten} Node;

Initialisierung der Liste

Eine verkettete Liste wird üblicherweise durch einen Zeiger auf den ersten Knoten, den sogenannten Kopf (head), referenziert. Ist die Liste leer, zeigt dieser Zeiger auf NULL.

Node* head = NULL; // Anfangs ist die Liste leer

Einfügen eines Knotens am Anfang

Um einen neuen Knoten am Anfang der Liste einzufügen, muss Speicher für den Knoten alloziert werden. Danach wird der neue Knoten so verbunden, dass er zum neuen Kopf der Liste wird.

void insertAtBeginning(Node** head, int value) { Node* newNode = malloc(sizeof(Node)); if (newNode == NULL) { printf("Speicherreservierung fehlgeschlagen\n"); return; } newNode->data = value; newNode->next = *head; // Der neue Knoten zeigt auf das bisherige erste Element *head = newNode; // Kopf zeigt jetzt auf den neuen Knoten}

Einfügen eines Knotens am Ende

Das Einfügen am Ende erfordert das Durchlaufen der Liste, bis der letzte Knoten erreicht ist (dessen next auf NULL zeigt), und anschließend das Anhängen des neuen Knotens.

void insertAtEnd(Node** head, int value) { Node* newNode = malloc(sizeof(Node)); if (newNode == NULL) { printf("Speicherreservierung fehlgeschlagen\n"); return; } newNode->data = value; newNode->next = NULL; if (*head == NULL) { *head = newNode; // Liste war leer, neuer Knoten ist Kopf return; } Node* current = *head; while (current->next != NULL) { current = current->next; } current->next = newNode; // Am Ende anfügen}

Löschen eines Knotens

Zum Löschen eines Knotens mit einem gegebenen Wert muss man die Liste durchsuchen und den Knoten aus der Verkettung entfernen. Dabei muss man auf spezielle Fälle achten, z. B. wenn der zu löschende Knoten der Kopf ist.

void deleteNode(Node** head, int value) { Node* current = *head; Node* prev = NULL; while (current != NULL && current->data != value) { prev = current; current = current->next; } if (current == NULL) { printf("Wert %d nicht gefunden.\n", value); return; } if (prev == NULL) { *head = current->next; // Kopf wird geändert } else { prev->next = current->next; } free(current); // Speicher freigeben}

Ausgabe der Liste

Um die Elemente der Liste anzuzeigen, kann man eine Funktion schreiben, die die Knoten der Reihe nach durchläuft und ihre Daten ausgibt.

void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n");}

Beispiel für die Nutzung der verketteten Liste

Das folgende Beispiel zeigt, wie man die beschriebenen Funktionen zusammen verwendet:

int main() { Node* head = NULL; // Liste initial leer insertAtBeginning(&head, 3); insertAtBeginning(&head, 1); insertAtEnd(&head, 5); insertAtEnd(&head, 7); printf("Liste nach Einfügungen: "); printList(head); deleteNode(&head, 5); printf("Liste nach Löschen von 5: "); printList(head); deleteNode(&head, 10); // Versuch, ein nicht vorhandenes Element zu löschen // Speicher freigeben (nicht gezeigt) return 0;}

Speicherfreigabe

Zum Schluss ist es wichtig, den gesamten dynamisch reservierten Speicher zu befreien, um Speicherlecks zu vermeiden. Dies kann man durch eine Hilfsfunktion erledigen, die alle Knoten der Liste löscht.

void freeList(Node* head) { Node* current = head; while (current != NULL) { Node* temp = current; current = current->next; free(temp); }}

Diese Grundlagen bilden die Basis für die Verwendung und Erweiterung verketteter Listen in C. Sie können auf einfache Weise angepasst werden, um komplexere Daten und weitere Operationen wie Einfügen in der Mitte oder Suchen zu unterstützen.

0

Kommentare