前言在单链表中删除一个节点必须先找到它的前驱时间复杂度为 O(n)而双向链表通过prev指针让每个节点都认识自己的前驱使得插入和删除操作可以在 O(1) 内完成。如果再让链表首尾相接形成循环结构并引入一个不存储有效数据的哨兵头节点那么头插、尾插、头删、尾删将不再需要任何特殊分支判断——所有位置的操作逻辑完全统一。本文基于带头节点的双向循环链表用 C 语言实现初始化、插入、删除、打印与销毁等核心操作并重点剖析指针重连的顺序与边界处理。一、数据结构定义// DuList.h #pragma once #include stdio.h #include stdlib.h #include stdbool.h #include assert.h typedef int ElemType; // 双向链表节点 typedef struct DuListNode { ElemType data; struct DuListNode* prev; struct DuListNode* next; } DuListNode; // 双向链表管理结构 typedef struct DuLinkList { DuListNode* head; // 哨兵头节点 size_t cursize; // 有效元素个数 } DuLinkList; 这里head指向一个哨兵节点它不存储有效数据仅作为链表的锚点。空表时哨兵节点的prev和next都指向自己形成自环。二、核心操作实现1. 创建节点DuListNode* BuyNode(ElemType val) { DuListNode* p (DuListNode*)malloc(sizeof(DuListNode)); if (p NULL) return NULL; p-data val; p-prev NULL; p-next NULL; return p; } malloc后必须判空这是 C 语言内存操作的基本规范。2. 初始化void InitDuList(DuLinkList* dps) { assert(dps ! NULL); DuListNode* p BuyNode(0); // 哨兵节点data 无实际意义 if (p NULL) return; p-next p; p-prev p; // 自环空表状态 dps-head p; dps-cursize 0; } 初始化后链表形态如下3. 在指定节点前插入bool InsertElemType(DuLinkList* dps, DuListNode* ptr, ElemType val) { assert(dps ! NULL); DuListNode* p BuyNode(val); if (p NULL) return false; p-next ptr; // 新节点后继指向 ptr p-prev ptr-prev; // 新节点前驱指向 ptr 的前驱 p-next-prev p; // ptr 的前驱指针指向新节点 p-prev-next p; // ptr 前驱的后继指针指向新节点 dps-cursize; return true; } 这是整个链表最核心的函数。四行指针赋值完成插入且无需区分头插、尾插或中间插入——因为哨兵节点的存在所有位置都是在某个节点前插入。插入过程图解假设在节点ptr前插入新节点p插入前p1 ←→ ptr插入前 p1 ptr 插入后 p1 p ptr四步指针重连的顺序至关重要必须先让新节点p的两条线指出去再让邻居节点指回来。如果先改ptr-prev就会丢失原前驱的地址。记忆口诀新节点先认亲指出去邻居再认亲指回来。4. 删除指定节点bool EraseNode(DuLinkList* dps, DuListNode* ptr) { assert(dps ! NULL); if (dps-cursize 0) return false; ptr-next-prev ptr-prev; // 后继的前驱指向 ptr 的前驱 ptr-prev-next ptr-next; // 前驱的后继指向 ptr 的后继 dps-cursize--; free(ptr); // 释放被删除节点 return true; } 删除操作同样无需任何分支判断两行指针赋值即可将节点从环中摘除。删除过程图解删除前 p1 ptr p2 删除后 p1 p25. 打印链表void PrintDuList(DuLinkList* dps) { assert(dps ! NULL); printf(双向循环链表中的所有元素为); DuListNode* p dps-head-next; for (; p ! dps-head; p p-next) { printf(%d , p-data); } printf(\n); }从哨兵节点的下一个节点开始遍历遇到哨兵节点时停止这样就不会打印哨兵节点的无效数据也不会陷入死循环。原文代码中先单独打印第一个节点再用for遍历剩余节点逻辑上可行但不够简洁。统一用for循环即可代码更清晰。6. 常用头插、尾插、头删、尾删// 头插在哨兵节点的下一个节点前插入 bool Push_Front(DuLinkList* dps, ElemType val) { return InsertElemType(dps, dps-head-next, val); } // 尾插在哨兵节点前插入等价于在最后一个节点后插入 bool Push_Back(DuLinkList* dps, ElemType val) { return InsertElemType(dps, dps-head, val); } // 头删删除哨兵节点的下一个节点 bool Pop_Front(DuLinkList* dps) { if (dps-cursize 0) return false; return EraseNode(dps, dps-head-next); } // 尾删删除哨兵节点的前一个节点 bool Pop_Back(DuLinkList* dps) { if (dps-cursize 0) return false; return EraseNode(dps, dps-head-prev); } 这就是带头节点双向循环链表的魅力头尾操作与中间操作完全统一没有特殊分支。7. 销毁链表void DestroyDuList(DuLinkList* dps) { assert(dps ! NULL); DuListNode* p dps-head-next; while (p ! dps-head) { DuListNode* next p-next; free(p); p next; } free(dps-head); // 释放哨兵节点 dps-head NULL; dps-cursize 0; } 必须逐个释放所有节点包括哨兵节点否则会造成内存泄漏。三、三种链表对比对比项不带头单链表带头单链表带头双向循环链表头插/头删需特殊判断无需判断无需判断尾插/尾删需遍历 特殊判断需遍历O(1)无需遍历删除已知节点需 O(n) 找前驱需 O(n) 找前驱O(1)代码复杂度分支最多中等最简洁内存开销无额外开销多 1 个节点多 1 个节点 每个节点多 1 个指针结论带头节点双向循环链表是工程中综合表现最优的选择——插入删除操作统一、时间复杂度低、代码简洁。唯一的代价是每个节点多一个prev指针但在现代计算机内存充裕的背景下这点开销完全可以接受。 
长河君 · 2026/10/19 4:48:39 · 阅读 1.2k 数据结构：带头节点双向循环链表
前言在单链表中删除一个节点必须先找到它的前驱时间复杂度为 O(n)而双向链表通过prev指针让每个节点都认识自己的前驱使得插入和删除操作可以在 O(1) 内完成。如果再让链表首尾相接形成循环结构并引入一个不存储有效数据的哨兵头节点那么头插、尾插、头删、尾删将不再需要任何特殊分支判断——所有位置的操作逻辑完全统一。本文基于带头节点的双向循环链表用 C 语言实现初始化、插入、删除、打印与销毁等核心操作并重点剖析指针重连的顺序与边界处理。一、数据结构定义// DuList.h #pragma once #include stdio.h #include stdlib.h #include stdbool.h #include assert.h typedef int ElemType; // 双向链表节点 typedef struct DuListNode { ElemType data; struct DuListNode* prev; struct DuListNode* next; } DuListNode; // 双向链表管理结构 typedef struct DuLinkList { DuListNode* head; // 哨兵头节点 size_t cursize; // 有效元素个数 } DuLinkList; 这里head指向一个哨兵节点它不存储有效数据仅作为链表的锚点。空表时哨兵节点的prev和next都指向自己形成自环。二、核心操作实现1. 创建节点DuListNode* BuyNode(ElemType val) { DuListNode* p (DuListNode*)malloc(sizeof(DuListNode)); if (p NULL) return NULL; p-data val; p-prev NULL; p-next NULL; return p; } malloc后必须判空这是 C 语言内存操作的基本规范。2. 初始化void InitDuList(DuLinkList* dps) { assert(dps ! NULL); DuListNode* p BuyNode(0); // 哨兵节点data 无实际意义 if (p NULL) return; p-next p; p-prev p; // 自环空表状态 dps-head p; dps-cursize 0; } 初始化后链表形态如下3. 在指定节点前插入bool InsertElemType(DuLinkList* dps, DuListNode* ptr, ElemType val) { assert(dps ! NULL); DuListNode* p BuyNode(val); if (p NULL) return false; p-next ptr; // 新节点后继指向 ptr p-prev ptr-prev; // 新节点前驱指向 ptr 的前驱 p-next-prev p; // ptr 的前驱指针指向新节点 p-prev-next p; // ptr 前驱的后继指针指向新节点 dps-cursize; return true; } 这是整个链表最核心的函数。四行指针赋值完成插入且无需区分头插、尾插或中间插入——因为哨兵节点的存在所有位置都是在某个节点前插入。插入过程图解假设在节点ptr前插入新节点p插入前p1 ←→ ptr插入前 p1 ptr 插入后 p1 p ptr四步指针重连的顺序至关重要必须先让新节点p的两条线指出去再让邻居节点指回来。如果先改ptr-prev就会丢失原前驱的地址。记忆口诀新节点先认亲指出去邻居再认亲指回来。4. 删除指定节点bool EraseNode(DuLinkList* dps, DuListNode* ptr) { assert(dps ! NULL); if (dps-cursize 0) return false; ptr-next-prev ptr-prev; // 后继的前驱指向 ptr 的前驱 ptr-prev-next ptr-next; // 前驱的后继指向 ptr 的后继 dps-cursize--; free(ptr); // 释放被删除节点 return true; } 删除操作同样无需任何分支判断两行指针赋值即可将节点从环中摘除。删除过程图解删除前 p1 ptr p2 删除后 p1 p25. 打印链表void PrintDuList(DuLinkList* dps) { assert(dps ! NULL); printf(双向循环链表中的所有元素为); DuListNode* p dps-head-next; for (; p ! dps-head; p p-next) { printf(%d , p-data); } printf(\n); }从哨兵节点的下一个节点开始遍历遇到哨兵节点时停止这样就不会打印哨兵节点的无效数据也不会陷入死循环。原文代码中先单独打印第一个节点再用for遍历剩余节点逻辑上可行但不够简洁。统一用for循环即可代码更清晰。6. 常用头插、尾插、头删、尾删// 头插在哨兵节点的下一个节点前插入 bool Push_Front(DuLinkList* dps, ElemType val) { return InsertElemType(dps, dps-head-next, val); } // 尾插在哨兵节点前插入等价于在最后一个节点后插入 bool Push_Back(DuLinkList* dps, ElemType val) { return InsertElemType(dps, dps-head, val); } // 头删删除哨兵节点的下一个节点 bool Pop_Front(DuLinkList* dps) { if (dps-cursize 0) return false; return EraseNode(dps, dps-head-next); } // 尾删删除哨兵节点的前一个节点 bool Pop_Back(DuLinkList* dps) { if (dps-cursize 0) return false; return EraseNode(dps, dps-head-prev); } 这就是带头节点双向循环链表的魅力头尾操作与中间操作完全统一没有特殊分支。7. 销毁链表void DestroyDuList(DuLinkList* dps) { assert(dps ! NULL); DuListNode* p dps-head-next; while (p ! dps-head) { DuListNode* next p-next; free(p); p next; } free(dps-head); // 释放哨兵节点 dps-head NULL; dps-cursize 0; } 必须逐个释放所有节点包括哨兵节点否则会造成内存泄漏。三、三种链表对比对比项不带头单链表带头单链表带头双向循环链表头插/头删需特殊判断无需判断无需判断尾插/尾删需遍历 特殊判断需遍历O(1)无需遍历删除已知节点需 O(n) 找前驱需 O(n) 找前驱O(1)代码复杂度分支最多中等最简洁内存开销无额外开销多 1 个节点多 1 个节点 每个节点多 1 个指针结论带头节点双向循环链表是工程中综合表现最优的选择——插入删除操作统一、时间复杂度低、代码简洁。唯一的代价是每个节点多一个prev指针但在现代计算机内存充裕的背景下这点开销完全可以接受。