C语言循环双向链表deletefront()函数失效问题排查与修正求助

问题分析 #

你的代码存在两个关键错误，导致delfront()函数无法正常工作：

1. insertfront()函数的循环链表结构不完整
   当链表非空时，你只更新了原头节点的左链接和新节点的右链接，但没有：

   • 设置新节点的左链接指向原链表的尾节点（head->llink）
   • 更新原尾节点的右链接指向新节点
     这会导致链表失去循环特性，结构断裂，后续的删除、遍历操作都会出现异常。

2. delfront()函数未处理链表仅有一个节点的情况
   当链表只有一个节点时，head->rlink和head->llink都指向自身，你的代码会尝试重新链接尾节点（即自身）和第二个节点（也是自身），然后释放节点后将head指向已被释放的内存（野指针），导致遍历的时候仍会输出已释放的节点数据。

修正后的代码 #

下面是修复了上述问题的完整代码：

// circular doubly linked list
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    int data;
    struct node *rlink;
    struct node *llink;
} node;
node *head = NULL;

node *getnode(int ele) {
    node *ptr;
    ptr = (node *)malloc(sizeof(node));
    if (ptr == NULL) {
        printf("memory not alloc");
        exit(0);
    }
    ptr->data = ele;
    ptr->rlink = NULL;
    ptr->llink = NULL;
    return ptr;
}

void insertfront(int ele) {
    node *newnode = getnode(ele);
    if (head == NULL) {
        head = newnode;
        head->rlink = head;
        head->llink = head;
    } else {
        node *last_node = head->llink; // 获取原尾节点
        // 建立新节点与原头节点的双向链接
        newnode->rlink = head;
        head->llink = newnode;
        // 建立新节点与原尾节点的双向链接，维持循环特性
        newnode->llink = last_node;
        last_node->rlink = newnode;
        // 更新头节点为新节点
        head = newnode;
    }
}

void insertend(int ele) {
    node *newnode = getnode(ele);
    if (head == NULL) {
        head = newnode;
        head->rlink = head;
        head->llink = head;
    } else {
        node *last_node = head->llink; // 直接获取尾节点，无需循环
        newnode->rlink = head;
        newnode->llink = last_node;
        last_node->rlink = newnode;
        head->llink = newnode;
    }
}

int lenlist() {
    if (head == NULL) return 0;
    node *temp = head;
    int count = 0;
    do {
        temp = temp->rlink;
        count++;
    } while (temp != head);
    return count;
}

void insertatpos(int ele,int pos) {
    int list_len = lenlist();
    if (pos < 1 || pos > list_len + 1) {
        printf("invalid position\n");
        return;
    }
    if (pos == 1) {
        insertfront(ele);
    } else if (pos == list_len + 1) {
        insertend(ele);
    } else {
        node *prev, *curr;
        node *newnode = getnode(ele);
        int count = 1;
        curr = head;
        do {
            prev = curr;
            curr = curr->rlink;
            count++;
            if (count == pos) {
                prev->rlink = newnode;
                newnode->llink = prev;
                newnode->rlink = curr;
                curr->llink = newnode;
                break; // 找到位置后直接退出循环，无需继续遍历
            }
        } while (curr != head);
    }
}

void delfront() {
    if (head == NULL) {
        printf("empty list\n");
        return;
    }
    // 处理链表仅有一个节点的情况
    if (head->rlink == head) {
        free(head);
        head = NULL;
        return;
    }
    node *aux = head;
    node *last_node = head->llink;
    node *second_node = head->rlink;
    // 重新链接尾节点和第二个节点，维持循环结构
    second_node->llink = last_node;
    last_node->rlink = second_node;
    free(aux);
    // 更新头节点为第二个节点
    head = second_node;
}

void display() {
    if (head == NULL) {
        printf("list is empty\n");
        return;
    }
    node *aux = head;
    do {
        printf("%d->", aux->data);
        aux = aux->rlink;
    } while (aux != head);
    printf("\n");
}

int main() {
    insertfront(100);
    insertend(20);
    printf("List length: %d\n", lenlist());
    insertatpos(45, 2);
    printf("Before deleting front: ");
    display();
    delfront();
    printf("After deleting front: ");
    display();
    return 0;
}

关键修复点说明 #

• insertfront()：补充了新节点与原尾节点的双向链接，确保链表始终保持循环结构。
• delfront()：增加了单个节点的判断逻辑，删除后将head置为NULL，避免野指针问题。
• 额外优化：简化了insertend()的尾节点获取方式（直接用head->llink），给lenlist()增加了空链表判断，insertatpos()增加了提前退出循环的逻辑，提升效率。

测试输出 #

修复后运行main()函数，输出如下：

List length: 2
Before deleting front: 100->45->20->
After deleting front: 45->20->

可以看到，原头节点100已被正确删除，链表显示正常。

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