扭转双重链接列表问题

I am trying to reverse a Doubly Linked List with no success. After reversing, the list appears to be empty.

我试图扭转双重链接列表但没有成功。反转后,列表显示为空。

Here is my implementation:

这是我的实施:

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

I expected

but get only

但只得到

3
2
1

The first printList() works as expected, but the second produces no output.

第一个printList()按预期工作,但第二个不产生输出。

Looking into the problem I've found that after reversing the list, for some reason list->head->next is pointing to list->tail, even though there are 3 elements in the list.

调查问题我发现在反转列表之后,由于某种原因list-> head-> next指向list-> tail,即使列表中有3个元素。

I've searched online for examples but stumbled upon implementations which don't use a DLL structure such as mine, but only Node structure.

我在网上搜索了一些例子,但偶然发现了不使用DLL结构的实现,例如我的,但只有Node结构。

1 个解决方案

#1

In your add function, you need to set new_item->next->prev to new_item after setting new_item->next = list->head->next;

在你的add函数中,你需要在设置new_item-> next = list-> head-> next之后将new_item-> next-> prev设置为new_item;

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++;
}

Similar issue is in your addToTail(). There you need to set new_item->prev->next to new_item.

类似的问题在你的addToTail()中。你需要在new_item旁边设置new_item-> prev->。

#1