📌 前言

在前面两篇文章中，我们分别学习了顺序表和单链表。

• 顺序表：支持随机访问，但头部和中间插入删除效率低（O(n)）。

• 单链表：头插头删效率高，但只能单向遍历，且尾插尾删仍需O(n)，另外删除结点时必须知道前驱结点。

那么有没有一种链表，既能双向遍历，又能高效地在任意位置插入删除呢？
双向链表（Doubly Linked List） 就是答案！如果再给它加上带头结点和循环的特性，就变成了我们今天要实现的 “带头循环双向链表” —— 这是链表中最完美的结构之一。

本文将带你手撕一个带头循环双向链表，包含：

• ✅ 结点的定义（data + prev + next）

• ✅ 初始化、打印

• ✅ 头插、头删、尾插、尾删（全部 O(1)！）

• ✅ 任意位置插入/删除（配合查找）

• ✅ 查找、判空、销毁

• ✅ 完整测试代码与运行结果

学完你将掌握：
👉 带头结点链表的优势
👉 双向循环链表的指针操作技巧
👉 为什么尾插尾删能成为 O(1)
👉 两种销毁方式的区别与选择

一、双向链表的基本概念

1.1 什么是带头循环双向链表

这个名字很长，我们拆解一下：

术语	含义	带来的好处
双向	每个结点既有 next 指针（指向后一个结点），也有 prev 指针（指向前一个结点）	可以双向遍历，删除任意结点不再需要查找前驱
循环	最后一个结点的 next 指向头结点，头结点的 prev 指向最后一个结点	形成闭环，遍历更方便，且没有空指针
带头	有一个哨兵位头结点，它的数据域不存放有效数据（通常存-1或任意值）	统一空表和非空表的操作逻辑，不需要二级指针

结构示意图：

text

       head (哨兵位)
          ↓
     ┌─────┴─────┐
     │ data = -1 │
     │ prev ───┐ │
     │ next ─┐ │ │
     └───────┴─┴─┘
           │   │
           ↓   ↓
     ┌───────────┐      ┌───────────┐
     │ data = 1  │  →→  │ data = 2  │
     │ prev ←─── │ ←──  │ prev      │
     │ next ───→ │  ←→  │ next ───→ │ ... → 回到head
     └───────────┘      └───────────┘

特点：

• 空链表时：只有头结点，它的 prev 和 next 都指向自己。

• 非空链表：头结点的 prev 指向最后一个结点，最后一个结点的 next 指向头结点。

1.2 为什么带头结点可以不用二级指针？

因为头结点本身是固定的，即使链表为空，头结点也存在。所有插入删除操作都不会改变 phead 这个指针变量本身（它始终指向那个哨兵位），所以我们只需要传递一级指针即可。
这一点对比单链表（没有头结点时头指针可能为 NULL）是一大进步！

二、代码实现（逐模块讲解）

2.1 头文件 List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// 定义数据类型
typedef int LTDataType;

// 定义双向链表结点结构
typedef struct ListNode {
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
} LTNode;

// 接口声明
void LTPrint(LTNode* phead);              // 打印
LTNode* LTInit();                         // 初始化（返回头结点）
void LTPushBack(LTNode* phead, LTDataType x);   // 尾插
void LTPushFront(LTNode* phead, LTDataType x);  // 头插
bool LTEmpty(LTNode* phead);              // 判空
void LTPopBack(LTNode* phead);            // 尾删
void LTPopFront(LTNode* phead);           // 头删
LTNode* LTFind(LTNode* phead, LTDataType x);   // 查找
void LTInsert(LTNode* pos, LTDataType x);       // 在pos之后插入
void LTErase(LTNode* pos);                // 删除pos结点
void LTDesTroy1(LTNode** pphead);         // 销毁方式1（二级指针）
void LTDesTroy2(LTNode* phead);           // 销毁方式2（一级指针，需手动置NULL）

📌 注意：这里所有操作都传 LTNode* 一级指针，因为头结点不变。只有销毁时，如果希望函数内把外部指针置NULL，才需要二级指针。

三、核心函数实现（List.c）

3.1 创建新结点（辅助函数）

LTNode* LTBuyNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = newnode;  // 新结点自己指向自己（循环初始状态）
    newnode->prev = newnode;
    return newnode;
}

3.2 初始化（创建头结点）

LTNode* LTInit() {
    LTNode* phead = LTBuyNode(-1);  // 头结点数据域可以随便放，一般放-1
    return phead;
}

空链表状态：只有一个头结点，它的 next 和 prev 都指向自己。

3.3 打印链表

void LTPrint(LTNode* phead) {
    assert(phead);
    LTNode* pcur = phead->next;   // 跳过头结点
    while (pcur != phead) {       // 循环结束条件：回到头结点
        printf("%d -> ", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

⚠️ 因为是循环链表，遍历的终止条件是 pcur != phead。

3.4 尾插（O(1) ）

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    
    // 原尾结点是 phead->prev
    LTNode* tail = phead->prev;
    
    // 修改四个指针
    newnode->prev = tail;
    newnode->next = phead;
    tail->next = newnode;
    phead->prev = newnode;
}

图解：

插入前：head <-> ... <-> tail
插入后：head <-> ... <-> tail <-> newnode

复杂度：O(1)，因为头结点直接记录尾结点地址（phead->prev）。

3.5 头插（O(1) ）

void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    LTNode* first = phead->next;   // 原来的第一个有效结点
    
    newnode->prev = phead;
    newnode->next = first;
    phead->next = newnode;
    first->prev = newnode;
}

3.6 判空

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

3.7 尾删（O(1) ）

void LTPopBack(LTNode* phead) {
    assert(!LTEmpty(phead));   // 不能删头结点
    LTNode* del = phead->prev;   // 要删除的尾结点
    LTNode* newTail = del->prev; // 新的尾结点
    
    newTail->next = phead;
    phead->prev = newTail;
    
    free(del);
    del = NULL;
}

3.8 头删（O(1) ）

void LTPopFront(LTNode* phead) {
    assert(!LTEmpty(phead));
    LTNode* del = phead->next;
    LTNode* newFirst = del->next;
    
    phead->next = newFirst;
    newFirst->prev = phead;
    
    free(del);
    del = NULL;
}

3.9 查找

LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;   // 没找到
}

3.10 在 pos 之后插入（O(1) ）

void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = LTBuyNode(x);
    LTNode* after = pos->next;
    
    newnode->prev = pos;
    newnode->next = after;
    pos->next = newnode;
    after->prev = newnode;
}

因为双向循环链表，不需要知道头结点，只要给一个位置结点，就可以完成插入。

3.11 删除 pos 结点（O(1) ）

void LTErase(LTNode* pos) {
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}

神奇之处：删除任意结点都只要 O(1)！因为可以直接通过 pos->prev 拿到前驱，不用遍历。

3.12 销毁链表（两种方式）

方式一：二级指针（函数内部置空外部指针）

void LTDesTroy1(LTNode** pphead) {
    assert(pphead);
    LTNode* pcur = (*pphead)->next;
    while (pcur != *pphead) {
        LTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    free(*pphead);
    *pphead = NULL;   // 外部指针也被置NULL
}

方式二：一级指针（需调用者手动置NULL）

void LTDesTroy2(LTNode* phead) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        LTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    free(phead);
    // 注意：phead 是形参，置NULL不影响外部实参
}

// 调用后需手动：
// LTDesTroy2(plist);
// plist = NULL;

💡 推荐：方式一更安全，不会忘记置空；方式二保持了接口一致性（都是一级指针），但需要调用者小心。

四、完整测试代码及运行结果

4.1 测试程序（test.c）

#include "List.h"

void test1() {
    printf("=== 尾插测试 ===\n");
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);   // 1 -> 2 -> 3 -> 4
}

void test2() {
    printf("=== 头插测试 ===\n");
    LTNode* plist = LTInit();
    LTPushFront(plist, 1);
    LTPushFront(plist, 2);
    LTPushFront(plist, 3);
    LTPushFront(plist, 4);
    LTPrint(plist);   // 4 -> 3 -> 2 -> 1
}

void test3() {
    printf("=== 尾删测试 ===\n");
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);
    LTPopBack(plist); LTPrint(plist);
    LTPopBack(plist); LTPrint(plist);
    LTPopBack(plist); LTPrint(plist);
    LTPopBack(plist); LTPrint(plist);
}

void test4() {
    printf("=== 头删测试 ===\n");
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);
    LTPopFront(plist); LTPrint(plist);
    LTPopFront(plist); LTPrint(plist);
    LTPopFront(plist); LTPrint(plist);
    LTPopFront(plist); LTPrint(plist);
}

void test5() {
    printf("=== 查找测试 ===\n");
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTNode* ret = LTFind(plist, 3);
    if (ret) printf("找到了3！\n");
    else printf("未找到\n");
    
    ret = LTFind(plist, 99);
    if (ret) printf("找到了99！\n");
    else printf("未找到99\n");
}

void test6() {
    printf("=== 在pos之后插入 ===\n");
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);
    LTNode* pos = LTFind(plist, 2);
    LTInsert(pos, 100);
    LTPrint(plist);   // 1 -> 2 -> 100 -> 3 -> 4
}

void test7() {
    printf("=== 删除pos结点 ===\n");
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);
    LTNode* pos = LTFind(plist, 2);
    LTErase(pos);
    LTPrint(plist);   // 1 -> 3 -> 4
}

int main() {
    test1();
    test2();
    test3();
    test4();
    test5();
    test6();
    test7();
    return 0;
}

4.2 运行结果

=== 尾插测试 ===
1 -> 2 -> 3 -> 4

=== 头插测试 ===
4 -> 3 -> 2 -> 1

=== 尾删测试 ===
1 -> 2 -> 3 -> 4
1 -> 2 -> 3
1 -> 2
1


=== 头删测试 ===
1 -> 2 -> 3 -> 4
2 -> 3 -> 4
3 -> 4
4


=== 查找测试 ===
找到了3！
未找到99

=== 在pos之后插入 ===
1 -> 2 -> 3 -> 4
1 -> 2 -> 100 -> 3 -> 4

=== 删除pos结点 ===
1 -> 2 -> 3 -> 4
1 -> 3 -> 4

五、复杂度分析汇总

操作	时间复杂度	说明
头插	O(1) ✅	直接修改头指针和原首结点
头删	O(1) ✅	直接修改头指针和第二个结点
尾插	O(1) ✅	通过 phead->prev 直接拿到尾结点
尾删	O(1) ✅	通过 phead->prev 拿到尾结点，再拿到新的尾结点
任意位置插入（已知pos）	O(1) ✅	双向链表只需修改四个指针
任意位置删除（已知pos）	O(1) ✅	通过 pos->prev 和 pos->next 直接操作
查找	O(n)	最坏情况遍历整个链表
打印	O(n)	遍历输出

这是目前效率最高的链表结构！ 除了查找是 O(n)，其他所有增删操作都是 O(1)。

---

六、带头循环双向链表 vs 单链表

对比维度	单链表（无头）	带头循环双向链表
结构	单向，尾结点next=NULL	双向循环，哨兵位
头插/头删	O(1)	O(1)
尾插/尾删	O(n)	O(1) ✅
已知pos删除	需要前驱（O(n)）	O(1) ✅
已知pos插入	O(1)（后插）或 O(n)（前插）	O(1) ✅（后插）
逆序遍历	不支持	支持（通过prev）
是否带头	通常不带头	带头
二级指针	需要（因为头指针会变）	不需要 ✅
空间开销	每个结点1个指针	每个结点2个指针

结论：带头循环双向链表是用空间换时间的典型，虽然多了一个 prev 指针和哨兵位，但换来了极致的操作效率和代码的简洁性。

---

七、常见问题与注意事项

7.1 为什么初始化时新结点要 next = prev = 自己？

因为双向链表是循环的，单个结点（头结点）也要满足循环条件：prev 和 next 都指向自己。

7.2 判空条件为什么是 phead->next == phead？

空链表只有头结点，头结点的 next 指向自己（循环），所以相等即为空。

7.3 删除最后一个有效结点后，链表会自动变空吗？

会的。例如删完最后一个有效结点后，phead->next 和 phead->prev 都会指向 phead 自己，满足判空条件。

7.4 为什么要两种销毁方式？

• 方式一（二级指针）：方便，自动把外部指针置NULL，防止野指针。

• 方式二（一级指针）：保持接口统一（所有其他函数都是一级指针），但需要调用者自己置NULL。

在实际工程中，建议使用方式一，更安全。

八、总结

我们一步一步实现了带头循环双向链表，它具备以下优点：

1. 双向遍历：既有 next 又有 prev，灵活度高。

2. 循环结构：没有空指针，遍历和操作统一。

3. 哨兵头结点：统一空表和非空表操作，不需要二级指针。

4. 所有增删操作 O(1)：这是链表中最优的性能表现。

如果你有任何疑问或改进想法，欢迎在评论区留言讨论！

最后！如果这篇博客对你有帮助，欢迎 点赞、收藏、评论 三连！后续会持续更新 栈、队列、树 等数据结构教程，敬请关注～