一文搞懂双向链表！从结构到实操，附完整代码

双向链表哨兵位与基本结构哨兵位 带头双向循环链表里的头节点也叫哨兵位一定要和单链表的头节点区分开单链表没有哨兵位,ta的头节点一般指的是第一个有效结点,里面存储着有效数据哨兵位不存储任何有效业务数据仅作为辅助节点(一般都是给哨兵位赋一个没有意义的值)整个链表形成闭环最后一个节点的next指向哨兵位哨兵位的prev指向最后一个节点核心作用遍历循环链表时避免死循环同时大幅简化空表、头部、尾部的增删逻辑不用频繁判断边界条件简单理解哨兵位就像一个 “门卫”帮我们统一链表的操作规则基本结构 双向链表的每一个节点除了存储有效数据还包含两个指针next指向下一个节点后继prev指向上一个节点前驱这也是 “双向” 名字的由来我们可以从任意节点向前、向后遍历整个链表// 定义双向链表结点的结构typedefintLTDataType;// 方便数据类型的更换structListNode{LTDataType data;structListNode*next;structListNode*prev;};typedefstructListNodeLTNode; 单链表和双向链表为空时的差异单链表为空------此时指向第一个有效结点的指针为空双向链表为空------此时链表中只剩下一个自循环的头节点核心接口的实现 申请结点动态开辟新节点,这里需要注意的是双向链表是循环链表,所以一开始ta的前驱和后继指针都应该指向ta自己(这个结点是自循环的)代码展示:// 申请结点LTNode*LTBuyNode(LTDataType x){LTNode*node(LTNode*)malloc(sizeof(LTNode));if(nodeNULL){perror(malloc fail);exit(1);}node-datax;node-nextnode-prevnode;// 使其自循环returnnode;} 初始化双向链表的初始化其实就是申请一个结点来充当哨兵位.由于哨兵位并不存储有效的值,所以一般来讲会给ta赋一个没有用的值(这里用-1)双向链表插入数据之前,链表必须初始化到只有一个头结点的情况代码展示:// 初始化voidLTInit(LTNode**pphead){// 给双向链表创建一个哨兵位*ppheadLTBuyNode(-1);} 关于操作中传参到底传一级指针还是二级指针的问题关键是判断只是动哨兵结点里面的数据,还是要增删哨兵结点一级指针:传的是哨兵结点的地址,只能改变哨兵结点内部的数据/指针二级指针传的是哨兵结点地址的地址,可以直接修改哨兵结点的地址(申请哨兵结点的空间 or 释放哨兵结点的空间)在实战中 : 用 一级指针 Node* 的函数打印链表查找节点尾插 / 头插尾删 / 头删修改节点数据原因不需要动哨兵本身只动哨兵内部和后面节点 用 二级指针 Node** 的函数初始化链表创建哨兵销毁链表释放哨兵原因必须修改哨兵变量本身的地址一句话 , 在双向链表中初始化 / 销毁用二级指针其他操作用一级指针 尾插先创建一个自循环的结点,修改该结点的前驱和后继,然后再修改尾结点的后继以及头结点的前驱注意,尾插操作一定是先动尾结点再动头结点先 phead -- prev -- next 后 phead -- prev 将新节点插入到头结点的前面,也叫做尾插代码展示 :// 尾插voidLTPushBack(LTNode*phead,LTDataType x){assert(phead);// 创建一个自循环的结点LTNode*newnodeLTBuyNode(x);// 修改新结点前驱和后继newnode-prevphead-prev;newnode-nextphead;// 修改尾结点的后继phead-prev-nextnewnode;// 修改头结点的前驱phead-prevnewnode;} 遍历双向链表用一个 结构体指针pcur 从第一个有效结点开始,让pcur不断等于ta的后继,直到指向头结点为止代码展示:// 遍历链表voidLTPrint(LTNode*phead){LTNode*pcurphead-next;while(pcur!phead){printf(%d-,pcur-data);pcurpcur-next;}// 跳出循环时,pcur指向头结点printf(\n);} 头插在第一个有效结点之前插入 (在哨兵位之后插入) 叫做头插在哨兵位之前插入 (在尾结点之后插入) 叫尾插创建一个自循环结点,修改结点的前驱和后继(无顺序要求),然后先改变第一个有效结点的前驱,再改变头结点的后继先 phead -- next -- prev 后 phead -- next 代码展示:// 头插voidLTPushFront(LTNode*phead,LTDataType x){// 创建新的自循环结点LTNode*newnodeLTBuyNode(x);// 修改新节点的前驱和后继newnode-prevphead;newnode-nextphead-next;// 修改第一个有效结点的前驱phead-next-prevnewnode;// 修改头结点的后继phead-nextnewnode;} 尾删 我发现-------如果是通过头结点来找到其他结点,那么所有的操作都应该是最后动头结点先动倒数第二个结点的后继,再动头结点的前驱,最后free掉尾结点代码展示:// 尾删voidLTPopBack(LTNode*phead){// 链表必须有效(判断内存里是否真的有头结点) 且 链表不能为空(头结点不能自循环)assert(pheadphead-next!phead);// 为简化代码,先存下尾结点的地址LTNode*delphead-prev;// 先动倒数第二个结点的后继del-prev-nextphead;// 再修改头结点的前驱phead-prevdel-prev;// 最后释放掉尾结点的空间free(del);delNULL;} 头删先动第二个有效结点的前驱,再改头结点的后继,最后free掉第一个有效结点代码展示:// 头删voidLTPopFront(LTNode*phead){// 链表必须有效(判断内存里是否真的有头结点) 且 链表不能为空(头结点不能自循环)assert(pheadphead-next!phead);// 保存第一个有效结点的地址LTNode*delphead-next;// 先动第二个结点的前驱del-next-prevphead;// 再改头结点的后继phead-nextdel-next;// 最后free掉第一个有效结点free(del);delNULL;} 查找查找的过程其实就是遍历链表的过程用一个 结构体指针pcur 从第一个有效结点开始,让pcur不断等于ta的后继,直到指向头结点为止代码展示:// 查找LTNode*LTFind(LTNode*phead,LTDataType x){LTNode*pcurphead-next;while(pcur!phead){if(pcur-datax){returnpcur;}pcurpcur-next;}// 跳出循环就代表没找到returnNULL;} 在指定位置pos之后插入新节点如果是通过pos位置来找到其他结点,那么所有的操作都应该最后动pos创建自循环的新节点,修改新节点的前驱后继,先动pos位置之后的结点,再动pos位置结点这个方法包含了头插,头插是这个方法中的一种情况代码展示://在pos位置之后插⼊数据voidLTInsert(LTNode*pos,LTDataType x){// pos地址不能为空assert(pos);// 创建自循环的新节点LTNode*newnodeLTBuyNode(x);// 修改新节点的前驱后继newnode-prevpos;newnode-nextpos-next;// 先动pos位置之后的结点pos-next-prevnewnode;// 再动pos位置的结点pos-nextnewnode;} 删除指定位置pos的结点这里并没有顺序上的要求,毕竟这些结点都是通过pos找来的,只要保证最后动pos就行需要改变pos位置前一个结点的后继,后一个结点的前驱,最后再释放掉pos位置结点所申请的空间代码展示:// 删除pos结点voidLTErase(LTNode*pos){// pos理论上来说不能为phead// 但是没有传相应的参数,无法校验assert(pos);// 修改pos前一个结点的后继 以及 后一个结点的前驱// 这里就没有顺序要求了,毕竟都是通过pos来找的// 只要保证最后改pos就行pos-prev-nextpos-next;pos-next-prevpos-prev;// 释放pos指向结点的空间free(pos);posNULL;} 销毁双向链表的销毁其实就是遍历链表的过程.只不过每一次遍历都要用一个 指针next 先保存下一个结点的地址,然后释放当前结点的空间,再将新地址赋给进行遍历的指针pcur代码展示:// 销毁// 传的是哨兵位地址的地址// 解引用得到哨兵位地址 ( *pphead )// 目的是free(*pphead) 之后能通过 *pphead NULL 避免野指针voidLTDestroy(LTNode**pphead){// 保证二级指针不为空 且 链表不为空assert(pphead*pphead);// 遍历链表LTNode*pcur(*pphead)-next;while(pcur!(*pphead)){LTNode*nextpcur-next;free(pcur);pcurnext;}// 跳出循环时,pcur指向哨兵位free(*pphead);*ppheadNULL;} 顺序表与链表适用场景对比顺序表连续内存内存连续整块存储随机访问极快 O(1)尾部增删快中间 / 头部插入删除很慢需要批量平移元素 O(n)有容量概念扩容会复制整个数组存在空间冗余缓存友好局部性好遍历速度远快于链表 什么时候适合用顺序表 ?大量随机下标访问需要频繁根据索引取值、修改元素比如取第 50 个元素顺序表一步到位链表要从头遍历例矩阵、表格数据、按序号存取的数据集。以尾部增删为主很少中间插入删除只在末尾添加 / 删除几乎无性能损耗日常绝大多数业务场景例存储日志、临时缓存、普通列表容器频繁遍历、循环读取数据连续内存命中 CPU 缓存遍历速度比链表快几倍到几十倍数据总量可控不需要频繁扩容迁移元素数量稳定提前预估容量可避免数组复制开销 不适合 :频繁在表头、中间位置插入删除海量数据链表分散节点 指针内存零散靠指针相连不支持随机访问查找指定下标必须遍历 O(n)已知节点位置时插入、删除只改指针O(1)无扩容开销但每个节点多存指针内存开销更大缓存不友好节点分散遍历效率低 什么时候适合用链表 ?大量在头部 / 中间插入、删除元素只要拿到目标节点仅修改指针不用移动大量元素例LRU 缓存、任务队列、消息插队、撤销操作栈数据量波动极大无法预估容量不需要提前分配连续大块内存按需分配节点无扩容复制例动态数据流、频繁增删的临时节点集合不需要随机访问只从头到尾遍历只做顺序迭代不会根据下标取值实现特殊数据结构栈、队列、双向队列、哈希表拉链、跳表等底层常用链表 不适合需要频繁按下标访问、大量循环遍历、二分查找