Verkettete Listen in C

Eine verkettete Liste ist eine dynamische Datenstruktur, in der Elemente (Knoten) mithilfe von Zeigern miteinander verbunden sind.

In dieser Lektion lernen Sie:

• Wie verkettete Listen funktionieren.
• Wie Sie Knoten in eine verkettete Liste einfügen und daraus löschen.
• Welche Vorteile verkettete Listen gegenüber Arrays haben.

Beispiel: Einen Knoten für eine verkettete Liste definieren

In C wird ein Knoten einer verketteten Liste mithilfe eines struct definiert, das ein Datenfeld und einen Zeiger auf den nächsten Knoten enthält.

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

struct Node {
    int data;
    struct Node *next;
};

int main() {
    struct Node *head = NULL;
    return 0;
}

Einen Knoten am Anfang einfügen

So fügen Sie am Anfang einer verketteten Liste einen neuen Knoten ein:

• Erstellen Sie einen neuen Knoten.
• Setzen Sie seinen next-Zeiger auf den aktuellen Kopf.
• Aktualisieren Sie den Kopfzeiger.

Beispiel: Einen Knoten am Anfang einfügen

Dieses Programm fügt am Anfang einer verketteten Liste einen neuen Knoten ein.

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

struct Node {
    int data;
    struct Node *next;
};

void insertAtBeginning(struct Node **head, int newData) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

int main() {
    struct Node *head = NULL;
    insertAtBeginning(&head, 10);
    printf("Inserted: %d\n", head->data);
    return 0;
}

Einen Knoten löschen

So löschen Sie einen Knoten aus einer verketteten Liste:

• Finden Sie den zu löschenden Knoten.
• Aktualisieren Sie den next-Zeiger des vorherigen Knotens.
• Geben Sie den Speicher des gelöschten Knotens frei.

Beispiel: Einen Knoten löschen

Dieses Programm löscht einen Knoten aus einer verketteten Liste.

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

struct Node {
    int data;
    struct Node *next;
};

void deleteNode(struct Node **head, int key) {
    struct Node *temp = *head, *prev;
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

int main() {
    struct Node *head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 10;
    head->next = NULL;
    deleteNode(&head, 10);
    return 0;
}

Vorteile verketteter Listen

Verkettete Listen haben gegenüber Arrays mehrere Vorteile:

• Dynamische Größe (die Größe muss nicht im Voraus festgelegt werden).
• Effizientes Einfügen und Löschen.
• Keine Speicherverschwendung durch feste Größen.

Zusammenfassung

In dieser Lektion haben Sie Folgendes gelernt:

• Was verkettete Listen sind und wie sie funktionieren.
• Wie Sie Knoten einfügen und löschen.
• Welche Vorteile verkettete Listen gegenüber Arrays haben.

Als Nächstes sehen wir uns Stacks und Queues in C an.