Linked list in C

Question

Wie erstelle ich eine einfache Linked List in C?

Answer 1

Im Gegensatz zu Arrays, bei denen die Elemente direkt im Speicher hintereinander liegen, werden die Elemente einer verketteten Liste durch sogenannte "Knoten" repräsentiert, die miteinander verknüpft sind. Jeder Knoten enthält zwei Hauptkomponenten:      

• Daten: Dies ist der Wert oder das Element, das in diesem Knoten gespeichert wird.     
• Zeiger (Pointer): Dies ist ein Zeiger auf den nächsten Knoten in der Liste.  

Die Verknüpfung der Knoten durch Zeiger ermöglicht es, dass die Elemente nicht kontinuierlich im Speicher liegen müssen sondern irgendwo dynamisch verstreut. Dadurch können die Elemente auch dynamisch hinzugefügt oder entfernt werden, ohne dass der gesamte Speicher neu organisiert werden muss. Es gibt verschiedene Arten von verketteten Listen, wie zum Beispiel:      

• Einfach verkettete Liste: Jeder Knoten hat einen Zeiger auf den nächsten Knoten.     
• Doppelt verkettete Liste: Jeder Knoten hat Zeiger auf den nächsten und den vorherigen Knoten.
• Kreisförmige verkettete Liste: Die letzte Kante ist mit der ersten verknüpft, so dass die Liste einen Kreis bildet.  

Hier ist ein einfaches Beispiel für die Definition eines Knotens und den Aufbau einer einfach verketteten Liste in C

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

// Definition des Knotens
struct Node {
    int data;
    struct Node* next;
};

int main() {
    // Erstellung des Head-Knotens
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->next = NULL; // Die verkettete Liste beginnt mit einem leeren Head-Knoten

    // Hinzufügen von Knoten zur verketteten Liste
    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    first->next = NULL;
    head->next = first;

    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    second->data = 2;
    second->next = NULL;
    first->next = second;

    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    third->data = 3;
    third->next = NULL;
    second->next = third;

    // Durchlaufen und Ausgeben der verketteten Liste
    struct Node* current = head->next;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    // Speicher freigeben
    current = head->next;
    while (current != NULL) {
        struct Node* temp = current;
        current = current->next;
        free(temp);
    }
    free(head);

    return 0;
}