当前位置：首页 > news >正文

带哨兵位的双向链表

news 2026/8/16 4:05:31

一、简介

上一篇我们实现了顺序表和单链表，但是我们发现了一个问题，链表的增、删、改都需要二级指针来操作，为了解决这个麻烦，今天引入一个叫哨兵位的家伙。
为什么需要哨兵位？
双向链表是数据结构中的基础，但普通双向链表有一个令人头疼的问题：边界条件处理繁琐。
哨兵位（Sentinel Node）：核心思想是引入一个不存储有效数据的“哑结点”作为链表的固定端点，让链表永远不为空。这样一来，所有结点（包括首元结点和尾结点）都拥有前驱和后继，插入删除操作不再需要特判边界。

二、双向循环链表核心特性

1. 结构特点
每个节点包含前驱指针(prve)、后继指针(next)、数据域(data)
带头结点：头结点不存储有效数据，统一空链表和非空链表的操作逻辑，避免特殊判空处理
循环结构：尾节点的next指向头结点，头结点的prve指向尾节点，链表首尾闭环

2. 时间复杂度优势
头插、头删、尾插、尾删：O(1)
查找、遍历：O(N)（链式结构固有特性，无法优化）
指定位置插入/删除：O(1)（已知pos节点时）

三、前置头文件与结构体定义（List.h）

#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* prve; }LTNode; //初始化 LTNode* LTInit(); //尾插双链表 void LTPushBack(LTNode* phead, LTDataType x); //打印双链表 void LTPrint(LTNode* phead); //头插双链表 void LTPushFront(LTNode* phead, LTDataType x); //尾删双链表 void LTPopBack(LTNode* phead); //头删双链表 void LTPopFront(LTNode* phead); //查找 LTNode* LTFind(LTNode* phead, LTDataType x); //在pos之后的位置插入数据 void LTInsertBack(LTNode* pos, LTDataType x); //在pos之前的位置插入数据 void LTInsertFront(LTNode* pos, LTDataType x); //删除pos位置的节点 void LTErase(LTNode* pos); //链表的销毁 void LTDesTroy(LTNode* phead);

设计说明（分离式编程）：使用typedef重命名结构体和数据类型，代码通用性更强，后续如需修改存储数据类型，只需改动一处即可。

四、核心功能接口完整实现与解析

1. 节点空间申请（LTBuyNode）

关键细节：新节点初始化时让自身的前驱、后继都指向自己，适配循环链表特性，避免野指针。

// 申请新节点空间并初始化 LTNode* LTBuyNode(LTDataType x) { // 动态申请节点内存 LTNode* newNode = (LTNode*)malloc(sizeof(LTNode)); // 内存申请失败校验 if (!newNode) { perror("newNode fail!"); // 打印系统错误信息 exit(1); // 终止程序 } // 赋值数据域 newNode->data = x; // 新节点默认自闭环（空节点状态） newNode->prve = newNode->next = newNode; return newNode; }

2. 链表判空（LTEmpty）

操作：基于循环链表特性，空链表的唯一判定条件：头结点的后继指向自身。

// 链表判空：空返回true，非空返回false bool LTEmpty(LTNode* phead) { // 带头结点空链表：phead->next == phead return phead->next == phead; }

3. 链表初始化（LTInit）

操作：创建头结点，完成空链表初始化，所有链表操作均基于头结点展开。

// 初始化双向循环链表，返回头结点地址 LTNode* LTInit() { // 头结点数据域无意义，默认赋值-1 LTNode* pphead = LTBuyNode(-1); return pphead; }

4. 尾插数据（LTPushBack）

操作：利用循环链表特性，phead->prve直接指向尾节点，无需遍历，O(1)效率完成尾插。

// 链表尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); // 断言：头结点不能为空 LTNode* newNode = LTBuyNode(x); // 建立新节点与原尾节点的关系 newNode->prve = phead->prve; phead->prve->next = newNode; // 建立新节点与头结点的关系，完成闭环 newNode->next = phead; phead->prve = newNode; }

5. 链表打印（LTPrint）

操作：从第一个有效节点开始遍历，遍历至头结点终止，打印所有有效数据。

// 遍历打印链表所有有效数据 void LTPrint(LTNode* phead) { assert(phead); // 从第一个有效节点开始遍历 LTNode* pv = phead->next; // 遍历终止条件：回到头结点 while (pv != phead) { printf("%d ->", pv->data); pv = pv->next; } printf("\n"); }

6. 头插数据（LTPushFront）

操作：在头结点和第一个有效节点之间插入新节点，完成头插操作。

// 链表头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newNode = LTBuyNode(x); // 连接新节点与原第一个有效节点 newNode->next = phead->next; phead->next->prve = newNode; // 连接新节点与头结点 newNode->prve = phead; phead->next = newNode; }

7. 尾删数据（LTPopBack）

操作：直接定位尾节点，修改头尾指针关联，释放尾节点内存，删除后仍保持链表闭环。

// 链表尾删 void LTPopBack(LTNode* phead) { // 断言：链表不能为空，空链表禁止删除 assert(!LTEmpty(phead)); // 定位尾节点 LTNode* del = phead->prve; // 断开尾节点连接，重新建立闭环 phead->prve = del->prve; del->prve->next = phead; // 释放内存，避免内存泄漏 free(del); del = NULL; }

8. 头删数据（LTPopFront）

操作：删除第一个有效节点，修正头结点与新首节点的指针关系。

// 链表头删 void LTPopFront(LTNode* phead) { assert(!LTEmpty(phead)); // 定位第一个有效节点 LTNode* del = phead->next; // 断开原首节点连接，建立新链接 phead->next = del->next; del->next->prve = phead; free(del); del = NULL; }

9. 数据查找（LTFind）

操作：遍历链表，匹配目标数据，返回对应节点地址，无匹配则返回NULL，为后续插入、删除提供pos位置。

// 查找值为x的节点，返回节点地址 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; // 未找到目标节点 }

10. 指定位置后插入（LTInsertBack）

操作：在pos节点后方插入新节点，无需移动节点，仅修改指针指向。

// 在pos节点之后插入数据 void LTInsertBack(LTNode* pos, LTDataType x) { assert(pos); LTNode* newNode = LTBuyNode(x); // 先连接新节点的前后指针 newNode->next = pos->next; newNode->prve = pos; // 再修改原后续节点和pos节点的指针 pos->next->prve = newNode; pos->next = newNode; }

11. 指定位置前插入（LTInsertFront）

操作：在pos节点前方插入新节点，适配更多自定义插入场景。

// 在pos节点之前插入数据 void LTInsertFront(LTNode* pos, LTDataType x) { assert(pos); LTNode* newNode = LTBuyNode(x); // 绑定新节点与pos、pos前驱节点的关系 newNode->next = pos; newNode->prve = pos->prve; // 修正原节点指针指向 pos->prve->next = newNode; pos->prve = newNode; }

12. 指定节点删除（LTErase）

操作：删除任意已知pos节点，通用性极强，可配合LTFind实现按值删除。

// 删除pos位置的节点 void LTErase(LTNode* pos) { assert(pos); // 跳过pos节点，直接关联前后节点 pos->prve->next = pos->next; pos->next->prve = pos->prve; // 释放节点内存 free(pos); pos = NULL; }

13. 链表销毁（LTDesTroy）

操作：遍历释放所有有效节点+头结点，彻底回收内存，杜绝内存泄漏。

// 销毁整个链表，释放所有内存 void LTDesTroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; // 遍历释放所有有效节点 while (pcur != phead) { pcur = pcur->next; free(pcur->prve); } // 释放头结点 free(phead); }

五、核心易错点总结

指针修改顺序：插入节点时，必须先绑定新节点的指针，再修改原节点指针，否则会丢失链表地址
空链表保护：删除操作必须判空，空链表执行删操作会导致指针越界崩溃
循环终止条件：遍历终止条件必须是pcur != phead，不能用NULL，否则会死循环
内存释放：所有malloc申请的节点必须手动free，链表使用完毕必须调用销毁函数
断言校验：所有接口入参指针必须断言判空，避免野指针操作

六、整体总结

双向循环链表是线性表中综合效率最高的链式结构，对比单链表：首尾操作从O(N)优化为O(1)，支持双向遍历、任意位置快速插入删除。本文实现的代码封装完整、逻辑严谨，包含工业级基础校验，可直接用于课程设计、项目开发和算法刷题。
核心优势概括：结构闭环、操作统一、效率高效、通用性强。

七、有哨兵位双链表对比无哨兵位单链表

前文完整实现了带头哨兵位的双向循环链表，也是工程开发中的最优写法。为了让大家彻底理解该结构的设计价值，本节将它和无哨兵位普通单链表做全方位对比，从结构本质、代码逻辑、边界处理、时间效率、适用场景五个维度深度剖析，厘清两种链表的优劣与适用场景。

7.1 基础结构对比

无哨兵位单链表：无额外头结点，第一个节点即为有效数据节点，链表首尾不闭环，尾节点next指针置为NULL，仅支持单向遍历。
有哨兵位双向循环链表：单独开辟一个哨兵头结点，不存储有效数据，链表首尾闭环，每个节点均包含前驱、后继双指针，支持双向遍历。

7.2 核心操作边界逻辑对比

这是两种结构最大的差异，也是哨兵位结构的核心优势所在。
无哨兵位单链表痛点
所有首尾操作、空链表操作都需要特殊分支判断，代码冗余且容易出错：
头插、头删：需要单独更新链表头指针，需区分空链表、单节点链表、多节点链表三种场景
尾插、尾删：必须遍历整个链表找到尾节点，无法直接定位，且需要判空防止空指针崩溃
空链表与非空链表操作逻辑完全不同，分支代码多，维护成本高
有哨兵位双链表优势
无任何特殊边界判断：无论链表为空、只有一个节点、还是多个节点，增删操作逻辑完全统一
头尾节点可通过phead->next、phead->prve直接O(1)定位，无需遍历
闭环结构杜绝野指针，所有节点指针均有合法指向，不存在NULL指针访问问题

7.3 时间复杂度对比

操作场景	无哨兵位单链表	有哨兵位双向循环链表
头部插入/删除	O(1)	O(1)
尾部插入/删除	O(N)（需遍历找尾）	O(1)（直接通过头结点定位尾节点）
正向遍历	O(N)	O(N)
逆向遍历	不支持	O(N)
指定位置插入/删除	O(N)（需遍历找前驱）	O(1)（已知pos节点可直接操作）

7.4 代码复杂度与稳定性对比

无哨兵位单链表
代码逻辑碎片化，大量if-else分支处理边界情况，新手极易遗漏空链表、单节点边界，导致野指针、内存泄漏、程序崩溃等问题。代码复用性差，每一个增删接口都需要重复编写边界判断逻辑。
有哨兵位双链表
接口逻辑高度统一，无冗余分支代码，所有场景复用一套指针操作逻辑。仅初始化时多开辟一个哨兵节点，极小的内存开销，换来极高的代码稳定性和可读性，非常适合工程级开发。

7.5 两种结构优缺点总结

无哨兵位单向单链表
优点：结构极简、内存开销最小，无需额外开辟哨兵节点，逻辑轻量化。
缺点：边界处理繁琐、尾部操作效率极低、不支持逆向遍历、代码容错率低、维护成本高。
有哨兵位双向循环链表
优点：操作逻辑统一无边界、首尾操作O(1)高效、支持双向遍历、代码健壮性强、几乎无野指针问题。
缺点：多占用一个哨兵节点内存（可忽略）、节点结构稍复杂（双指针）。