数据结构(三) 带头双向循环链表 (附完整代码实现)

数据结构(三) 带头双向循环链表 (附完整代码实现)在链表家族中带头双向循环链表是综合效率最高、实际工程中最常用的链表结构。它完美解决了单链表查找前驱、尾插尾删效率低、边界判断复杂等问题是链表学习的核心重点。本文从结构原理、接口设计、完整代码、性能对比四个维度带你彻底掌握双向链表。文章目录数据结构(三) 带头双向循环链表 (附完整代码实现)一、双向链表核心结构1. 结构定义2. 哨兵位的作用3. 节点结构体二、双向链表接口设计三、完整代码实现1. 工具函数创建新节点2. 链表初始化3. 链表销毁4. 打印链表5. 判断链表是否为空6. 尾插 / 尾删7. 头插 / 头删8. 查找节点9. 指定位置插入 / 删除核心接口10. 测试主函数四、顺序表 vs 双向链表 全面对比五、总结一、双向链表核心结构1. 结构定义本文实现的是带头双向循环链表这是标准双向链表的最优形态带头存在哨兵位头节点不存储有效数据仅用于简化边界处理双向每个节点包含prev前驱指针和next后继指针循环尾节点的next指向头节点头节点的prev指向尾节点2. 哨兵位的作用很多同学疑惑为什么要多一个不存数据的节点统一插入/删除逻辑无需处理头节点为空的边界情况循环结构避免遍历死循环尾节点查找直接用head-prev时间复杂度O(1)3. 节点结构体// 链表存储的数据类型可改为char、double等typedefintLTDataType;// 双向链表节点结构体typedefstructListNode{// 指向后一个节点structListNode*next;// 指向前一个节点structListNode*prev;// 节点存储的数据LTDataType data;}LTNode;二、双向链表接口设计我们将实现工业级标准的双向链表接口覆盖初始化、增删查改、销毁全流程链表初始化链表销毁打印链表判断链表是否为空尾插、尾删头插、头删查找节点指定位置插入、指定位置删除三、完整代码实现1. 工具函数创建新节点所有插入操作都需要先创建节点封装为独立函数// 创建新节点LTNode*BuyLTNode(LTDataType x){LTNode*newnode(LTNode*)malloc(sizeof(LTNode));if(newnodeNULL){perror(malloc fail);returnNULL;}newnode-datax;newnode-prevNULL;newnode-nextNULL;returnnewnode;}2. 链表初始化返回哨兵位头节点初始状态自己指向自己// 初始化返回哨兵位头节点LTNode*LTInit(){LTNode*pheadBuyLTNode(-1);if(pheadNULL){returnNULL;}// 双向循环phead-nextphead;phead-prevphead;returnphead;}3. 链表销毁遍历释放所有节点最后释放哨兵位// 销毁链表voidLTDestroy(LTNode*phead){assert(phead);LTNode*curphead-next;while(cur!phead){LTNode*nextcur-next;free(cur);curnext;}free(phead);}4. 打印链表// 打印链表voidLTPrint(LTNode*phead){assert(phead);printf(哨兵位-);LTNode*curphead-next;while(cur!phead){printf(%d-,cur-data);curcur-next;}printf(哨兵位\n);}5. 判断链表是否为空// 判断链表是否为空boolLTEmpty(LTNode*phead){assert(phead);returnphead-nextphead;}6. 尾插 / 尾删尾插直接在哨兵位前驱节点后插入// 尾插voidLTPushBack(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeBuyLTNode(x);LTNode*tailphead-prev;// 建立双向连接tail-nextnewnode;newnode-prevtail;newnode-nextphead;phead-prevnewnode;}尾删直接删除尾节点无需遍历// 尾删voidLTPopBack(LTNode*phead){assert(phead);// 空链表不能删assert(!LTEmpty(phead));LTNode*tailphead-prev;LTNode*tailPrevtail-prev;tailPrev-nextphead;phead-prevtailPrev;free(tail);}7. 头插 / 头删头插在哨兵位后插入// 头插voidLTPushFront(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeBuyLTNode(x);LTNode*firstphead-next;phead-nextnewnode;newnode-prevphead;newnode-nextfirst;first-prevnewnode;}头删删除哨兵位后第一个节点// 头删voidLTPopFront(LTNode*phead){assert(phead);assert(!LTEmpty(phead));LTNode*firstphead-next;LTNode*secondfirst-next;phead-nextsecond;second-prevphead;free(first);}8. 查找节点// 查找值为x的节点找到返回节点地址找不到返回NULLLTNode*LTFind(LTNode*phead,LTDataType x){assert(phead);LTNode*curphead-next;while(cur!phead){if(cur-datax){returncur;}curcur-next;}returnNULL;}9. 指定位置插入 / 删除核心接口这是双向链表最强大的接口头插、尾插都可复用此函数// 在pos位置之前插入voidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newnodeBuyLTNode(x);LTNode*posPrevpos-prev;posPrev-nextnewnode;newnode-prevposPrev;newnode-nextpos;pos-prevnewnode;}// 删除pos位置节点voidLTErase(LTNode*pos){assert(pos);LTNode*posPrevpos-prev;LTNode*posNextpos-next;posPrev-nextposNext;posNext-prevposPrev;free(pos);}10. 测试主函数intmain(){// 初始化LTNode*plistLTInit();// 尾插LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPrint(plist);// 头插LTPushFront(plist,0);LTPrint(plist);// 尾删LTPopBack(plist);LTPrint(plist);// 头删LTPopFront(plist);LTPrint(plist);// 查找插入LTNode*posLTFind(plist,2);if(pos){LTInsert(pos,99);}LTPrint(plist);// 删除LTErase(pos);LTPrint(plist);// 销毁LTDestroy(plist);plistNULL;return0;}四、顺序表 vs 双向链表 全面对比对比维度顺序表双向链表物理存储物理空间连续逻辑连续物理不连续随机访问支持O(1)不支持O(N)插入/删除需搬移元素O(N)只需改指针O(1)缓存利用率高空间连续低节点分散扩容问题需扩容存在空间浪费按需申请无浪费适用场景大量查询、少插入删除频繁任意位置增删五、总结带头双向循环链表是链表最优结构哨兵位极大简化边界处理尾插、尾删、头插、头删时间复杂度均为O(1)LTInsert/LTErase是核心接口可复用实现所有增删操作链表与顺序表互补根据业务场景选择查多用顺序表增删多用链表