C语言带头双向循环链表核心操作实现详解

一、 链表结构设计与优势

带头双向循环链表由一个不存储有效数据的“哑元”头结点和若干存储数据的节点组成。其显著特征在于：

1. 双向连接：每个节点包含 prev 和 next 两个指针，分别指向前驱和后继。
2. 循环闭合：尾节点的 next 指向头结点，头结点的 prev 指向尾节点，形成闭环。
3. 统一接口：由于存在固定的头结点，无需特殊处理头插或首节点删除的情况，所有插入和删除操作的逻辑保持一致。

二、 核心模块定义

在编写具体操作前，需明确节点的结构体定义及辅助类型别名。这决定了后续内存管理的粒度与接口参数。

typedef int ListDataType;
typedef struct ListNode {
    ListDataType val;       // 有效数据
    struct ListNode* prev;  // 前驱指针
    struct ListNode* next;  // 后继指针
}LTNode;

三、 逐步实现关键操作

第1步：创建单个节点

封装 BuyListNode 函数用于向堆区申请内存并初始化。此步骤是所有涉及新节点操作的基础，确保新节点的指针不会成为野指针。

LTNode* BuyListNode(ListDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc");
        exit(-1);
    }
    newnode->val = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

第2步：链表初始化

初始化需要创建一个不存数据的头结点，并让其 prev 和 next 都指向自身，构成初始的空环。这里采用二级指针传参，以便在主调函数中直接修改头指针变量。

void ListInit(LTNode** pphead) {
    *pphead = (LTNode*)malloc(sizeof(LTNode));
    *pphead = BuyListNode(-1); 
    (*pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}

第3步：打印链表信息

遍历是从头结点的 next 开始，直到再次遇到头结点时停止。使用 assert 确保传入的头指针合法，防止空指针解引用。

void ListPrint(LTNode* phead) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

第4步：尾部插入（尾插）

利用循环特性，找到当前尾节点（即 phead->prev）。将新节点插在尾节点之后，同时修正新节点与前驱后援的连接关系。

void ListPushBack(LTNode* phead, ListDataType x) {
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev; // 当前尾节点
    
    // 1. 新节点链接原尾节点与原头节点
    newnode->next = tail->next;
    tail->next = newnode;
    
    // 2. 新节点链接原头节点
    phead->prev = newnode;
    newnode->prev = tail;
}

第5步：尾部删除（尾删）

删除需校验链表不为空（判断 phead->next != phead）。找到尾节点后，断开其与前驱的连接，释放尾节点内存，并将新的尾节点与头结点重新衔接。

void ListPopBack(LTNode* phead) {
    assert(phead);
    assert(phead->next != phead); // 非空判断
    
    LTNode* prevnode = phead->prev; // 准备删除的尾节点
    prevnode->prev->next = phead;   // 尾节点的前驱 -> 头结点
    phead->prev = prevnode->prev;   // 头结点 <- 尾节点的前驱
    free(prevnode);
}

第6步：头部插入（头插）

头插实际上是插在头结点与第一个有效节点之间。获取第二个节点（tail），将其前驱改为新节点，新节点再连入头结点即可。

void ListPushFront(LTNode* phead, ListDataType x) {
    assert(phead);
    LTNode* second = phead->next;   // 原来的第一个有效节点
    LTNode* newnode = BuyListNode(x);
    
    second->prev = newnode;
    newnode->next = second;
    newnode->prev = phead;
    phead->next = newnode;
}

第7步：头部删除（头删）

同样需要先进行非空断言。删除逻辑是将头结点的 next 指向第三个节点，并将第三个节点的前驱重新指向头结点。

void ListPopFront(LTNode* phead) {
    assert(phead);
    assert(phead->next != phead);
    
    LTNode* second = phead->next;   // 第一个有效节点
    phead->next = second->next;     // 头结点 -> 第三个节点
    second->next->prev = phead;     // 第三个节点 -> 头结点
    free(second);                   // 释放第一个节点
}

第8步：查找指定元素

从头结点开始往后遍历，若找到值相等的节点则返回其指针，否则返回 NULL。这是其他位置插入和删除的前置依赖。

LTNode* ListFind(LTNode* phead, ListDataType x) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        if (cur->val == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

第9步：按位置插入

给定目标节点 pos，在其前驱与 pos 之间插入新节点。逻辑与头插类似，只是参照点不同。

void ListInsert(LTNode* pos, ListDataType x) {
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    LTNode* before = pos->prev; // pos的直接前驱
    
    before->next = newnode;
    newnode->prev = before;
    newnode->next = pos;
    pos->prev = newnode;
}

第10步：按位置删除

找到待删节点 pos 的上下相邻节点，绕过 pos 进行连接，然后安全释放内存。

void ListErase(LTNode* pos) {
    assert(pos);
    LTNode* prevnode = pos->prev;
    LTNode* nextnode = pos->next;
    
    prevnode->next = nextnode;
    nextnode->prev = prevnode;
    free(pos);
}

第11步：状态查询（判空与大小）

当 phead->next == phead 时链表为空。计算大小时只需统计有效节点个数，注意不要累加头结点。

bool ListEmpty(LTNode* phead) {
    assert(phead);
    return phead->next == phead;
}

size_t ListSize(LTNode* phead) {
    assert(phead);
    size_t size = 0;
    LTNode* cur = phead->next;
    while (cur != phead) {
        size++;
        cur = cur->next;
    }
    return size;
}

第12步：彻底销毁链表

内存泄漏的主要隐患区。需先遍历销毁所有有效节点，最后销毁哑元头结点本身。

void ListDestroy(LTNode* phead) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        LTNode* nextnode = cur->next;
        free(cur);
        cur = nextnode;
    }
    free(phead); // 别忘了销毁头结点
}

四、 验证与调试测试

完整的 TestList 逻辑涵盖了全生命周期验证：

1. 顺序插入测试：尾插 5 个元素验证循环连接的正确性。
2. 反向删除测试：依次尾删 3 个元素，观察剩余元素是否为预期的中间段。
3. 前端操作测试：执行两次头插和一次头删，检验前向连接的完整性。
4. 精准定位测试：使用 ListFind 锁定特定数值，调用 ListInsert 插入测试节点后紧接 ListErase 删除该节点，模拟实际业务中的原地更新场景。
5. 最终输出：打印剩余数据长度与具体内容，确认无内存错乱或数据丢失。