Inverser une liste à double liaison

Question

J'essaye de renverser une liste doublement liée sans succès. Après l'inversion, la liste semble être vide.

Voici mon implémentation:

#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 
} 

Je me attendais

3 
2 
1 
1 
2 
3 

mais seulement obtenir

3 
2 
1 

Le premier printList() fonctionne comme prévu, mais le second ne produit aucune sortie.

En regardant dans le problème, j'ai trouvé que, après avoir inversé la liste, pour une raison quelconque list->head->next pointe vers list->tail, même s'il y a 3 éléments dans la liste.

J'ai cherché en ligne pour des exemples mais tombé sur des implémentations qui n'utilisent pas une structure DLL comme la mienne, mais seulement la structure Node.

Answer 1

Dans votre fonction add, vous devez définir new_item->next->prev-new_item après la mise en 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++; 
} 

problème similaire est dans votre addToTail(). Là, vous devez définir new_item->prev->next à new_item.