双向循环链表deleteB头删操作后末尾出现尾随0的问题排查

问题表现 #

实现双向循环链表的头删函数deleteB后，删除头节点遍历链表时，末尾出现多余的0值，异常运行截图如下：

附原始实现代码：

#include <stdio.h>
#include <stdlib.h>

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

void deleteB(Node **head)
{
    if (*head != NULL)
    {
        if ((*head)->next == *head)
        {
            *head = NULL;
            return;
        }
        Node *temp = *head;
        (*head)->prev->next = (*head)->next;
        (*head)->next->prev = (*head)->prev;
        *head = (*head)->next;
        free(temp);
        // Node *curr = *head;
        // while (curr->next != *head)
        // {
        //  curr = curr->next;
        // }
        // curr->next = (*head)->next;
        // (*head)->next->prev = curr;
        // *head = (*head)->next;
        // free(temp);
    }
}

void prepend(Node **head, int value)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->data = value;
    if (*head == NULL)
    {
        *head = newNode;
        (*head)->next = *head;
        (*head)->prev = *head;
        return;
    }
    Node *temp = *head;
    while (temp->next != *head)
    {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
    newNode->next = *head;
    *head = newNode;
}

void append(Node **head, int value)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->data = value;
    if (*head == NULL)
    {
        *head = newNode;
        (*head)->next = *head;
        (*head)->prev = *head;
        return;
    }
    Node *temp = *head;
    while (temp->next != *head)
    {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
    newNode->next = *head;
}

void display(Node *head)
{
    printf("\nPrinting the list: ");
    Node *temp = head;
    do
    {
        printf("-->%d", temp->data);
        temp = temp->next;
    } while (temp != head);
}

int main()
{
    Node *head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    append(&head, 4);
    // insertAtN(&head, 9, 1);
    deleteB(&head);
    display(head);
    printf("\n");
    return 0;
}

问题根因 #

deleteB的头删逻辑本身没有问题，bug出在append和prepend两个插入函数没有正确维护双向循环链表的指针：

• append函数在尾部插入新节点后，没有将原头节点的prev指针指向新的尾节点，导致头节点的prev指针始终指向第一次初始化时的节点，无法正确定位到链表尾部
• 调用deleteB时，代码尝试通过(*head)->prev拿到尾节点修改其next指针，但实际拿到的是不符合预期的节点地址，真正的尾节点next指针仍然指向被释放的原头节点
• 遍历链表时，走到尾节点后会访问到已释放的内存空间，该空间被系统覆写为0，因此输出了多余的尾随0，后续从已释放内存中读到原头节点存储的next指针才回到新头节点，终止遍历
• 额外问题：prepend函数同样存在遗漏，头插新节点后没有将原头节点的prev指针指向新头节点，后续调用头插也会出现指针错误

修复方案 #

1. 修复append函数，在设置完新节点的next指针后，补充头节点prev指针的赋值：

void append(Node **head, int value)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->data = value;
    if (*head == NULL)
    {
        *head = newNode;
        (*head)->next = *head;
        (*head)->prev = *head;
        return;
    }
    Node *temp = *head;
    while (temp->next != *head)
    {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
    newNode->next = *head;
    (*head)->prev = newNode; // 补充该行，维护头节点的前驱指针
}

2. 修复prepend函数，在更新头指针前，补充原头节点prev指针的赋值：

void prepend(Node **head, int value)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->data = value;
    if (*head == NULL)
    {
        *head = newNode;
        (*head)->next = *head;
        (*head)->prev = *head;
        return;
    }
    Node *temp = *head;
    while (temp->next != *head)
    {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
    newNode->next = *head;
    (*head)->prev = newNode; // 补充该行，维护原头节点的前驱指针
    *head = newNode;
}

修复后运行代码，输出结果为-->2-->3-->4，无多余尾随0，逻辑正常。

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