双向链表专题：结构、实现与对比分析

双向链表专题结构、实现与对比分析双向链表是链表中结构最复杂但使用最广泛的一种。本文将深入讲解带头双向循环链表的结构特点带您从零实现双向链表的核心接口增删改查并与顺序表进行全方位对比分析各自的适用场景。目录一、双向链表的结构1. 带头双向循环链表的定义2. 哨兵位的作用二、实现双向链表1. 节点结构与接口声明2. 核心接口实现三、顺序表和双向链表的对比分析一、双向链表的结构1. 带头双向循环链表的定义带头双向循环链表是链表中最复杂也最常用的一种结构。它具备三个特征带头存在一个哨兵位节点不存储有效数据双向每个节点既有指向下一个节点的指针next也有指向上一个节点的指针prev循环尾节点的next指向哨兵位哨兵位的prev指向尾节点typedefstructListNode{structListNode*next;// 指向下一个节点structListNode*prev;// 指向上一个节点intdata;// 数据域}LTNode;2. 哨兵位的作用哨兵位节点不保存有效数据只作为链表头尾的标志。它的存在使得空链表不再是NULL而是仅有一个哨兵位节点其next和prev都指向自己遍历链表时不会死循环因为遇到哨兵位即表示遍历结束插入删除操作无需考虑头尾特殊处理逻辑统一二、实现双向链表1. 节点结构与接口声明typedefintLTDataType;typedefstructListNode{structListNode*next;structListNode*prev;LTDataType data;}LTNode;// 创建哨兵位初始化链表LTNode*LTInit();// 销毁链表voidLTDestroy(LTNode*phead);// 打印链表voidLTPrint(LTNode*phead);// 判断链表是否为空仅含哨兵位boolLTEmpty(LTNode*phead);// 尾插 / 尾删voidLTPushBack(LTNode*phead,LTDataType x);voidLTPopBack(LTNode*phead);// 头插 / 头删voidLTPushFront(LTNode*phead,LTDataType x);voidLTPopFront(LTNode*phead);// 在 pos 位置之后插入voidLTInsert(LTNode*pos,LTDataType x);// 删除 pos 位置节点voidLTErase(LTNode*pos);// 查找值为 x 的节点LTNode*LTFind(LTNode*phead,LTDataType x);注意所有接口参数均为哨兵位指针phead无需二级指针因为哨兵位永远固定不变。2. 核心接口实现创建哨兵位初始化LTNode*LTInit(){LTNode*phead(LTNode*)malloc(sizeof(LTNode));if(pheadNULL)exit(-1);phead-nextphead;phead-prevphead;returnphead;}创建新节点LTNode*BuyLTNode(LTDataType x){LTNode*node(LTNode*)malloc(sizeof(LTNode));if(nodeNULL)exit(-1);node-datax;node-nextNULL;node-prevNULL;returnnode;}尾插voidLTPushBack(LTNode*phead,LTDataType x){LTNode*newNodeBuyLTNode(x);LTNode*tailphead-prev;// 哨兵位的 prev 即尾节点tail-nextnewNode;newNode-prevtail;newNode-nextphead;phead-prevnewNode;}头插voidLTPushFront(LTNode*phead,LTDataType x){LTNode*newNodeBuyLTNode(x);LTNode*firstphead-next;phead-nextnewNode;newNode-prevphead;newNode-nextfirst;first-prevnewNode;}尾删voidLTPopBack(LTNode*phead){assert(!LTEmpty(phead));// 不能删除哨兵位LTNode*tailphead-prev;LTNode*prevtail-prev;prev-nextphead;phead-prevprev;free(tail);}头删voidLTPopFront(LTNode*phead){assert(!LTEmpty(phead));LTNode*firstphead-next;LTNode*secondfirst-next;phead-nextsecond;second-prevphead;free(first);}在 pos 之后插入voidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newNodeBuyLTNode(x);LTNode*nextpos-next;pos-nextnewNode;newNode-prevpos;newNode-nextnext;next-prevnewNode;}删除 pos 节点voidLTErase(LTNode*pos){assert(pos);LTNode*prevpos-prev;LTNode*nextpos-next;prev-nextnext;next-prevprev;free(pos);}打印链表voidLTPrint(LTNode*phead){LTNode*curphead-next;printf(哨兵位 - );while(cur!phead){printf(%d - ,cur-data);curcur-next;}printf(哨兵位\n);}判断空链表boolLTEmpty(LTNode*phead){returnphead-nextphead;}销毁链表voidLTDestroy(LTNode*phead){LTNode*curphead-next;while(cur!phead){LTNode*nextcur-next;free(cur);curnext;}free(phead);}三、顺序表和双向链表的对比分析不同点顺序表双向链表单链表类似存储空间物理上一定连续逻辑上连续物理上不一定连续随机访问支持 O(1)不支持O(N)任意位置插入删除需要搬移元素效率低 O(N)只需修改指针指向 O(1)容量管理需要扩容可能浪费空间或扩容耗时无容量概念按需分配节点缓存友好性好空间局部性强差节点分散缓存命中率低适用场景元素高效存储 频繁随机访问任意位置频繁插入删除总结没有绝对优劣只有是否适合场景。顺序表适合静态数据、频繁查找双向链表适合动态数据、频繁增删。实际开发中两者常配合使用。总结双向链表通过哨兵位和双向指针实现了优雅的循环结构和统一的操作逻辑解决了单链表在删除、反向遍历上的不便。与顺序表相比双向链表在任意位置插入删除上具有天然优势但牺牲了随机访问和缓存性能。掌握双向链表是理解更复杂数据结构如LRU缓存、双向队列的基础建议读者动手实现所有接口并与单链表、顺序表进行对比测试。