双向链表（带头双向循环链表）超详细实现指南

1. 什么是双向链表？

双向链表是一种链式存储结构，每个结点包含三个部分：存储数据的域、指向下一个结点的指针、指向上一个结点的指针。与单链表相比，双向链表可以双向遍历，在任意位置插入和删除更加灵活。

而我们今天要实现的是 带头双向循环链表，它有三个特点：

• 带头：有一个哨兵位结点（head），它不存储有效数据，只作为“头结点”方便操作。

• 双向：每个结点有 next 和 prev 指针。

• 循环：尾结点的 next 指向头结点，头结点的 prev 指向尾结点，形成一个环。

这种结构的最大优势是：不管在哪个位置插入或删除，都不需要移动元素，只需修改指针。

2. 结点结构定义

typedef int LTDataType; // 方便修改存储的数据类型

typedef struct ListNode {
LTDataType data; // 数据域
struct ListNode* next; // 指向下一个结点
struct ListNode* prev; // 指向上一个结点
} LTNode;

示意图：

+——–+ +——–+ +——–+
| prev |<—->| prev |<—->| prev |
| data | | data | | data |
| next |—->| next |—->| next |
+——–+ +——–+ +——–+
head tail
^ |
+——————————-+

3. 创建新结点

每个新结点被创建时，我们需要手动分配内存，并让它的 next 和 prev 先指向自己（循环初始状态）。

LTNode* LTBuyNode(LTDataType x) {
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode; // 自己指向自己，形成循环
return newnode;
}

⚠️ 坑点1：一定要检查 malloc 是否成功，否则后续对空指针操作会崩溃。

4. 初始化链表

有两种常见的初始化方式，我们对比一下。

方式一：传二级指针

void LTInit(LTNode** pphead) {
assert(pphead);
*pphead = LTBuyNode(-1); // 哨兵位，数据任意
}

调用时：LTInit(&plist);

方式二：返回头结点（推荐，保持接口一致性）

LTNode* LTInit() {
LTNode* phead = LTBuyNode(-1);
return phead;
}

调用时：LTNode* plist = LTInit();

⚠️ 坑点2：为什么推荐方式二？ 因为链表其他操作（增删改查）都只需要传一级指针（头结点地址不会改变）。如果初始化用二级指针，而销毁时可能又用一级指针，导致接口风格不一致，增加学习成本。

5. 打印链表

注意：哨兵位不存储有效数据，所以从 phead->next 开始打印，直到回到 phead 停止。

void LTPrint(LTNode* phead) {
LTNode* pcur = phead->next;
while (pcur != phead) {
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("\\n");
}

图解： 假设链表有 1,2,3 三个结点：

phead -> [哨兵] <-> [1] <-> [2] <-> [3] <-> [哨兵]
^ |
+——————————-+
打印结果：1 -> 2 -> 3 ->

6. 尾插（LTPushBack）

在哨兵位的前一个位置（即最后一个有效结点）后面插入新结点。

步骤：

void LTPushBack(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);

newnode->prev = phead->prev; // 新结点的prev指向原尾结点
newnode->next = phead; // 新结点的next指向头结点

phead->prev->next = newnode; // 原尾结点的next指向新结点
phead->prev = newnode; // 头结点的prev指向新结点
}

示意图（空链表时）：

插入前：
phead -> [哨兵] <-> [哨兵] (自己指向自己)

插入1后：
[哨兵] <-> [1] <-> [哨兵]
^ |
+—————+

⚠️ 坑点3：修改指针的顺序很重要！如果先把 phead->prev 改了，就会丢失原尾结点的地址。正确的顺序是：先让新结点连接旧链表，再断开旧链表的连接。

7. 头插（LTPushFront）

在哨兵位之后（第一个有效结点之前）插入新结点。

步骤：

void LTPushFront(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* newnode = LTBuyNode(x);

newnode->next = phead->next;
newnode->prev = phead;

phead->next->prev = newnode;
phead->next = newnode;
}

8. 判空

链表为空时，只有哨兵位自己循环：phead->next == phead。

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

9. 尾删（LTPopBack）

删除最后一个有效结点。注意：链表不能为空（哨兵位不能删）。

步骤：

void LTPopBack(LTNode* phead) {
assert(!LTEmpty(phead)); // 空链表不能删
LTNode* del = phead->prev;

del->prev->next = phead;
phead->prev = del->prev;

free(del);
del = NULL;
}

⚠️ 坑点4：释放结点后一定要将局部指针置 NULL，虽然函数结束后指针会销毁，但良好的习惯能避免误用。

10. 头删（LTPopFront）

删除第一个有效结点。

void LTPopFront(LTNode* phead) {
assert(!LTEmpty(phead));
LTNode* del = phead->next;

del->next->prev = phead;
phead->next = del->next;

free(del);
del = NULL;
}

11. 查找

遍历链表，返回第一个匹配数据的结点地址，找不到返回 NULL。

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;
}

12. 在指定位置之后插入（LTInsert）

这是最通用的插入函数，可以替代头插和尾插。

步骤（在 pos 之后插入）：

void LTInsert(LTNode* pos, LTDataType x) {
assert(pos);
LTNode* newnode = LTBuyNode(x);

newnode->next = pos->next;
newnode->prev = pos;

pos->next->prev = newnode;
pos->next = newnode;
}

如何使用：

• 尾插：LTInsert(phead->prev, x); // 在尾结点之后插入（实际上是在头结点之前？注意循环）

• 头插：LTInsert(phead, x); // 在哨兵位之后插入

⚠️ 坑点5：pos 不能为 NULL。另外，如果要在指定位置 之前 插入，可以用 LTInsert(pos->prev, x) 实现，但一般不单独提供函数。

13. 删除指定位置结点（LTErase）

删除 pos 位置的结点，pos 不能是哨兵位。

步骤：

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

14. 销毁链表

销毁所有结点（包括哨兵位）。这里有两种接口设计。

方式一：传二级指针（销毁后自动置NULL）

void LTDesTroy(LTNode** pphead) {
LTNode* pcur = (*pphead)->next;
while (pcur != *pphead) {
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(*pphead);
*pphead = NULL;
}

方式二：传一级指针（需要调用者手动置NULL）—— 推荐

void LTDesTroy(LTNode* phead) {
LTNode* pcur = phead->next;
while (pcur != phead) {
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
// 注意：这里无法将外部 plist 置为 NULL，需要调用者手动做
}

调用方式：

LTNode* plist = LTInit();
// … 各种操作
LTDesTroy(plist);
plist = NULL; // 必须手动置NULL，否则变成野指针

⚠️ 坑点6：为什么推荐传一级指针？ 因为链表的其他所有操作都只需要一级指针（头结点地址不变），如果销毁突然要求二级指针，接口不统一，容易混淆。传一级指针，让调用者负责置 NULL，是一种更清晰的约定。

15. 常见坑点总结

16. 顺序表 vs 双向链表 对比

17. 完整代码示例

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;

// 初始化
LTNode* LTInit();
// 销毁
void LTDesTroy(LTNode* phead);
// 打印
void LTPrint(LTNode* phead);
// 判空
bool LTEmpty(LTNode* phead);
// 尾插 / 头插
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
// 尾删 / 头删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
// 查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 在 pos 之后插入 / 删除 pos
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);

List.c（前面已给出，略）

test.c（示例）

#include "List.h"

int main() {
LTNode* plist = LTInit();

LTPushBack(plist, 10);
LTPushBack(plist, 20);
LTPushFront(plist, 5);
LTPrint(plist); // 5 -> 10 -> 20 ->

LTNode* pos = LTFind(plist, 10);
if (pos) LTInsert(pos, 15);
LTPrint(plist); // 5 -> 10 -> 15 -> 20 ->

LTErase(pos);
LTPrint(plist); // 5 -> 15 -> 20 ->

LTPopBack(plist);
LTPopFront(plist);
LTPrint(plist); // 15 ->

LTDesTroy(plist);
plist = NULL;
return 0;
}

18.最后

带头双向循环链表是数据结构中“最复杂也最简单”的结构：结构定义复杂，但一旦写好插入删除的核心逻辑，其他操作都是对它的简单包装。理解指针的指向变化和循环特性是关键。

如果你能手动画出每一步的指针连接图，调试时就能轻松定位问题。希望这篇文章能帮你彻底搞懂双向链表！

更多链表刷题推荐：

• LeetCode 链表专题

• 牛客网 链表专项