Double linked List in C

Question

Ich habe einen Node

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

und erstelle damit eine Linked List.

struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->next = NULL;

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;

Wie kann ich eine doppelte linked list machen so das jeder Knoten Zeiger auf den nächsten und den vorherigen Knoten hat.

Answer 1

Du musst die Struktur des Node anpassen, um einen Zeiger auf den vorherigen Knoten hinzuzufügen.

struct Node {
    int data;
    struct Node* next;
    struct Node* prev; // Zeiger auf den vorherigen Knoten hinzugefügt
};

Der Struktur jedes neuen Node wird ein Zeiger "prev" auf den vorherigen Node hinzugefügt. Bei der Initialisierung des ersten (Head) Node wird prev auf NULL gesetzt, da der Head keinen vorherigen Node hat.

struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->next = NULL;
head->prev = NULL;

struct Node* first = (struct Node*)malloc(sizeof(struct Node));
first->data = 1;
first->next = NULL;
first->prev = head; // Der vorherige Knoten von "first" ist der Head-Knoten
head->next = first;

struct Node* second = (struct Node*)malloc(sizeof(struct Node));
second->data = 2;
second->next = NULL;
second->prev = first; // Der vorherige Knoten von "second" ist "first"
first->next = second;

struct Node* third = (struct Node*)malloc(sizeof(struct Node));
third->data = 3;
third->next = NULL;
third->prev = second; // Der vorherige Knoten von "third" ist "second"
second->next = third;