Eine doppelt verknüpfte Liste stornieren Probleme

Question

Ich versuche, eine Doubly Linked List ohne Erfolg umzukehren. Nach dem Umkehren scheint die Liste leer zu sein.

Hier ist meine Implementierung:

#include <stdio.h> 
#include <malloc.h> 
#include <stdlib.h> 
typedef struct Item Item; 
typedef struct DLL DLL; 

struct Item { 
    int value; 
    Item* next; 
    Item* prev; 
}; 

struct DLL { 
    Item* head; 
    Item* tail; 
    int size; 
    void(*add)(DLL*, int); 
    void(*addToTail)(DLL*, int); 
}; 

void add(DLL* list, int val) { 
    Item* new_item = (Item*) malloc(sizeof(Item)); 
    if (new_item == NULL) { 
     exit(-1); 
    } 
    new_item->value = val; 
    new_item->next = list->head->next; 
    list->head->next = new_item; 
    new_item->prev = list->head; 
    list->size++; 
} 

void addToTail(DLL* list, int val) { 
    Item* new_item = (Item*) malloc(sizeof(Item)); 
    if (new_item == NULL) { 
     exit(-1); 
    } 
    new_item->value = val; 
    new_item->prev = list->tail->prev; 
    list->tail->prev = new_item; 
    new_item->next = list->tail; 
    list->size++; 
} 

Item* find(DLL* list, int val) { 
    Item* iter = list->head->next; 
    while (iter != list->tail) { 
     if (iter->value == val) { 
      return iter; 
     } 
     iter = iter->next; 
    } 
    return NULL; 
} 

void reverse(DLL* list) { 
    Item* current = list->head; 
    Item* temp = NULL; 
    while (current != NULL) { 
     temp = current->next; 
     current->next = current->prev; 
     current->prev = temp; 
     current = current->prev; 
    } 

    temp = list->head; 
    list->head = list->tail; 
    list->tail = temp; 
} 

void printList(DLL* list) { 
    Item* iter = list->head->next; 
    while (iter != list->tail) { 
     printf("%d\n", iter->value); 
     iter = iter->next; 
    } 
} 

DLL* initDLL() { 
    DLL* list = (DLL*) malloc(sizeof(DLL)); 
    if (list == NULL) { 
     exit(-1); 
    } 

    // Creating head & tail 
    list->head = (Item*) malloc(sizeof(Item)); 
    list->tail = (Item*) malloc(sizeof(Item)); 
    if (list->head == NULL || list->tail == NULL) { 
     free(list); 
     exit(-1); 
    } 

    // Initializing head & tail values just for testing 
    list->head->value = 100; 
    list->tail->value = 200; 

    list->head->prev = NULL; 
    list->head->next = list->tail; 
    list->tail->prev = list->head; 
    list->tail->next = NULL; 

    list->size = 0; 
    list->add = add; 
    list->addToTail = addToTail; 

    return list; 
} 

int main() { 
    DLL* my_list = initDLL(); 
    my_list->add(my_list, 1); 
    my_list->add(my_list, 2); 
    my_list->add(my_list, 3); 

    printList(my_list); 
    // Outputs: 
    // 3 
    // 2 
    // 1 

    reverse(my_list); 

    printList(my_list); 
    // Prints nothing since list->head->next == list->tail 
} 

Ich erwartete

3 
2 
1 
1 
2 
3 

aber nur

3 
2 
1 

erhalten

Die erste printList() funktioniert wie erwartet, aber die zweite erzeugt keine Ausgabe.

Blick in das Problem Ich habe festgestellt, dass nach dem Umkehren der Liste, aus irgendeinem Grund list->head->next zeigt auf list->tail, obwohl es 3 Elemente in der Liste sind.

Ich habe online nach Beispielen gesucht, stolperte jedoch über Implementierungen, die keine DLL Struktur wie meine, sondern nur Node Struktur verwenden.

Answer 1

In Ihrer Add-Funktion, müssen Sie new_item->next->prev-new_item einstellen, nach new_item->next = list->head->next;

void add(DLL* list, int val) { 
    Item* new_item = malloc(sizeof *new_item); 
    if (new_item == NULL) { 
     exit(EXIT_FAILURE); 
    } 
    new_item->value = val; 
    new_item->next = list->head->next; 
    new_item->next->prev = new_item; // <--- This is missing in your code 
    list->head->next = new_item; 
    new_item->prev = list->head; 
    list->size++; 
} 

ähnlicher Ausgabe Einstellung in Ihrem addToTail() sind. Dort müssen Sie new_item->prev->next auf new_item setzen.