双向链表节点移除异常求助：指定位置移除返回错误值

问题说明 #

我在main函数中对双向链表执行以下操作：

• 调用dll_push_front添加若干元素
• 调用dll_push_back添加若干元素
  随后移除pos=0和pos=1位置的节点，但输出显示移除pos=0返回值为5、移除pos=1返回值为7，与预期的4和2不符，无法定位错误。

完整代码 #

#ifndef MYDLL_H
#define MYDLL_H

#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
    struct node *previous;
} node_t;

typedef struct DLL
{
    int count;     
    node_t *head; 
    node_t *tail; 
} dll_t;

dll_t *create_dll()
{
    dll_t *myDLL = (dll_t*)malloc(sizeof(dll_t));
    if (myDLL == NULL) {
        return NULL;
    }
    myDLL->count = 0;
    myDLL->head = NULL;
    myDLL->tail = NULL;
    return myDLL;
}

int dll_empty(dll_t *l)
{
    if (l == NULL) {
        return -1;
    }
    if (l->count == 0 && l->head == NULL) {
        return 1;
    } else {
        return 0;
    }
}

int dll_push_front(dll_t *l, int item)
{
    if (l == NULL) {
        return -1;
    }
    node_t* new = (node_t*)malloc(sizeof(node_t));
    if (new == NULL) {
        return -1;
    }
    new->data = item;
    new->next = l->head;
    new->previous = NULL;

    if (l->head != NULL) { //set new prev for the previous head before pushing. 
        l->head->previous = new;
    } 
    l->head = new; // reset the new head for l.
    l->count++;
    return 1;
}

int dll_push_back(dll_t *l, int item)
{
    if (l == NULL) {
        return -1;
    }
    node_t* new = (node_t*)malloc(sizeof(node_t));
    if (new == NULL) {
        return -1;
    }
    new->data = item;
    new->previous = l->tail;
    new->next = NULL;

    if(l->tail != NULL) {
        l->tail->next = new;
    } else {
        l->head = new;
    }
    l->tail = new;
    l->count++;
    return 1;
}

int dll_pop_front(dll_t *t)
{
    if (t == NULL || t->head == NULL) {
        return -1;
    }

    node_t* pop_pointer = t->head; 
    int pop_item = pop_pointer->data; 
    t->head = pop_pointer->next; // set new head. 
    if (t->head != NULL) {
        t->head->previous = NULL;
    } else { // t->head = NULL cuz only one item and after popping, the t->head is null. 
        t->tail = NULL; // else if t->head = NULL, then t->tail also should be NULL.
    }
    if (t->head == NULL) {
        t->tail = NULL;
    }
    t->count--;
    free(pop_pointer);
    return pop_item;
}

int dll_pop_back(dll_t *t)
{
    if (t == NULL || t->head == NULL) {
        return -1;
    }
    node_t* pop_pointer = t->tail;
    int pop_item = pop_pointer->data; 
    t->tail = pop_pointer->previous; 
    if (t->tail != NULL) {
        t->tail->next = NULL;
    } else {
        t->head = NULL;
    }
    if (t->head == NULL) {
        t->tail = NULL;
    }
    t->count--;
    free(pop_pointer);
    return pop_item;
}

int dll_insert(dll_t *l, int pos, int item)
{
    if (l == NULL) {
        return -1;
    }
    if (pos >= l->count || pos < 0) {
        return 0;
    }
    node_t* new = (node_t*)malloc(sizeof(node_t));
    if (new == NULL) {
        return 0;
    }
    new->data = item;
    if(pos == 0) {
        return dll_push_front(l, item);
    }

    node_t* pointer = l->head;
    for (int i = 0; i < pos - 1; i++) {
        pointer = pointer->next; 
    }
    //ex: pos = 1, no for loop, pointer still head. 
    new->previous = pointer; 
    new->next = pointer->next; 
    pointer->next->previous = new; 
    pointer->next = new; 
    l->count++;
    return 1;
}

int dll_get(dll_t *l, int pos)
{
   if (l == NULL) {
    return -1;
   } 
   if (pos < 0 || pos >= l->count) {
    return 0;
   }
   node_t* pointer = l->head;
   for (int i = 0; i < pos - 1; i++) {
    pointer = pointer->next;
   }
   return pointer->data;
}

int dll_remove(dll_t *l, int pos)
{
    if (l == NULL) {
        return -1;
    }
    if (pos < 0 || pos >= l->count) {
        return 0;
    }
    node_t* pointer = l->head;
    node_t* prev = NULL; // first node prev is null. 
    for (int i = 0; i < pos; i++) {
        prev = pointer;
        pointer = pointer->next;
    }
    if (prev == NULL) { // first item.
        l->head = pointer->next;
    } else {
        prev->next = pointer->next;
    }
    if (pointer->next != NULL) {
        pointer->next->previous = prev;
    }
    // if we are removing the tail node
    if (pointer == l->tail) {
        l->tail = prev;
    }
    int removed_value = pointer->data;
    free(pointer);
    l->count--;
    return removed_value;
}

int dll_size(dll_t *t) {   
    if (t == NULL) {
        return -1;
    }
    return t->count;
}

void free_dll(dll_t *t)
{
    if (t == NULL) {
        return;
    }
    if (t == NULL) {
        free(t);
        return;
    }
    node_t* pointer = t->head;
    while(pointer != NULL) {
        node_t* pointer2 = pointer; 
        pointer = pointer->next;
        free(pointer2); 
    }
    free(t);
}

#endif

错误定位与修复 #

1. dll_push_front函数未维护tail指针 #

当链表为空时，添加第一个节点后，该节点既是头节点也是尾节点，但当前代码仅更新了head指针，未同步更新tail指针，导致后续push_back操作逻辑错误，破坏链表结构。

修复后的代码：

int dll_push_front(dll_t *l, int item)
{
    if (l == NULL) {
        return -1;
    }
    node_t* new = (node_t*)malloc(sizeof(node_t));
    if (new == NULL) {
        return -1;
    }
    new->data = item;
    new->next = l->head;
    new->previous = NULL;

    if (l->head != NULL) {
        l->head->previous = new;
    } else {
        // 链表为空时，新节点同时作为尾节点
        l->tail = new;
    }
    l->head = new;
    l->count++;
    return 1;
}

2. dll_get函数遍历逻辑错误 #

原代码中循环条件for (int i = 0; i < pos - 1; i++)无法正确定位目标节点，例如pos=1时，循环不会执行，返回的是头节点数据而非第二个节点的数据。

修复后的代码：

int dll_get(dll_t *l, int pos)
{
   if (l == NULL) {
    return -1;
   } 
   if (pos < 0 || pos >= l->count) {
    return 0;
   }
   node_t* pointer = l->head;
   for (int i = 0; i < pos; i++) {
    pointer = pointer->next;
   }
   return pointer->data;
}

辅助调试建议 #

可以添加打印链表所有元素的函数，方便调试过程中验证链表结构：

#include <stdio.h>
void print_dll(dll_t *l) {
    if (l == NULL || l->head == NULL) {
        printf("Empty list\n");
        return;
    }
    node_t* ptr = l->head;
    printf("List elements: ");
    while (ptr != NULL) {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

修复上述问题后，链表的结构维护会恢复正常，移除节点的返回值即可符合预期。

内容的提问来源于stack exchange，提问作者luke