C语言数据结构：双链表详解

1. 引言链表是 C 语言中非常基础且重要的数据结构。与数组不同链表通过指针将一系列节点串联起来不需要连续的内存空间。而双链表Doubly Linked List在单链表的基础上每个节点额外增加了一个指向前驱节点的指针使得我们可以从两个方向遍历链表。链表分为8种主要由三个维度构成带头/不带头单向/双向循环/不循环由这三个维度组成了8种类型的链表其中最常用的是两种链表单链表不带头单向不循环链表双链表带头双向循环链表带头即为拥有一个头节点头节点又被称为哨兵位头节点不存储实际数据仅作为哨兵这样可以简化插入和删除的边界处理。本文将带你从零开始用 C 语言实现一个完整的双链表涵盖初始化、插入、删除、查找、遍历等核心操作并配有可运行的完整代码示例。2. 双链表的结构定义双链表的每个节点包含三部分数据域、指向前驱节点的指针prev和指向后继节点的指针next。// 双向链表结构:前驱指针 数据 后驱指针typedefintLTDataType;typedefstructListNode{LTDataType data;// 数据域structListNode*prev;// 指向前驱节点structListNode*next;// 指向后继节点}LTNode;与之前同样方便我们修改存储的数据类型直接在最开始时定义好双链表中存储的数据类型将其重命名3. 初始化与销毁在使用链表时我们在外部新建一个链表节点指针指向双链表的头节点3.1 申请节点和初始化链表创建一个空的双链表头节点和尾节点都指向哨兵节点本身// 初始化// 给双链表创建一个哨兵位voidLTInit(LTNode**pphead){*ppheadLTApplyNode(-1);}为了方便后续新建节点在此将申请节点的函数单独拎出来避免代码冗余因为哨兵位需要自己指向自己形成循环链表它的前后指针不能初始化为NULL// 申请节点LTNode*LTApplyNode(LTDataType x){LTNode*newnode(LTNode*)malloc(sizeof(LTNode));if(newnodeNULL){perror(malloc fail!);exit(1);}newnode-datax;newnode-prevnewnode;newnode-nextnewnode;returnnewnode;}3.2 销毁链表释放所有节点和链表结构体的内存避免内存泄漏需要注意的是因为这里函数传值给的是一级指针因此调用销毁链表后需要手动将指针置为NULL函数内部将指针置为NULL并不会影响实参如果不手动置为NULL在销毁链表后再使用链表指针将会造成越界访问的问题但只要不使用该指针就不会有影响后续删除指定位置节点时也是同理为什么不传二级指针保持接口的一致性降低使用成本// 销毁链表// 全部删除 包括头节点// 使用后需要手动将phead置为NULLvoidLTDestroy(LTNode*phead){assert(phead);LTNode*pcurphead-next;while(pcur!phead){LTNode*pnextpcur-next;free(pcur);pcurpnext;}// 现在只剩头节点没有删除free(phead);pcurpheadNULL;}4. 基本操作4.1 尾插法在链表尾部插入新节点需要改变头结点和尾节点的prev和next指针指向注意在插入数据之前链表必须初始化到只有一个头节点的情况因为双链表是双向带头循环链表我们在插入和删除时都不改变哨兵位的位置所以只需要传一级即可// 尾插voidLTPushBack(LTNode*phead,LTDataType x){// 头节点不能为空assert(phead);LTNode*newnodeLTApplyNode(x);// 修改节点的前驱指针和后驱指针// phead phead-prev newnodenewnode-prevphead-prev;newnode-nextphead;phead-prev-nextnewnode;phead-prevnewnode;}4.2 头插法在链表头部插入新节点// 头插voidLTPushFront(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeLTApplyNode(x);// 修改指针指向// phead phead-next newnodenewnode-prevphead;newnode-nextphead-next;phead-next-prevnewnode;phead-nextnewnode;}4.3 尾删删除链表尾节点// 尾删voidLTPopBack(LTNode*phead){// 链表必须有效 且 链表不能为空(只有一个哨兵位)assert(phead);assert(phead-next!phead);LTNode*delphead-prev;// phead del del-prevphead-prevdel-prev;del-prev-nextphead;// 销毁del节点free(del);delNULL;}4.4 头删删除链表第一个节点注意头删不是删除头节点链表中最少还有头节点存在不能改变头节点// 头删voidLTPopFront(LTNode*phead){assert(pheadphead-next!phead);LTNode*delphead-next;phead-nextdel-next;del-next-prevphead;free(del);delNULL;}4.5 指定位置之后插入在第 pos 个位置之后插入节点pos是链表中某个节点的具体位置配合查找功能一起使用// 在pos位置之后插入数据voidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newnodeLTApplyNode(x);newnode-prevpos;newnode-nextpos-next;pos-next-prevnewnode;pos-nextnewnode;}4.6 查找节点按值查找返回第一个匹配节点的位置找不到返回 NULL// 查找LTNode*LTFind(LTNode*phead,LTDataType x){assert(phead);LTNode*pcurphead-next;while(pcur!phead){if(pcur-datax){// 找到了returnpcur;}pcurpcur-next;}// 没找到returnNULL;}4.7 删除节点删除指定位置的节点// 删除pos节点voidLTErase(LTNode*pos){assert(pos);// 修改节点指针指向pos-prev-nextpos-next;pos-next-prevpos-prev;// 销毁pos节点free(pos);posNULL;}4.8 打印链表正向打印链表// 打印链表voidLTPrint(LTNode*phead){assert(phead);LTNode*pcurphead-next;while(pcur!phead){printf(%d-,pcur-data);pcurpcur-next;}printf(NULL\n);}5. 完整示例代码下面是完整的程序双链表函数声明// List.h头文件#pragmaonce#includestdio.h#includeassert.h#includestdlib.h// 双向链表结构:前驱指针 数据 后驱指针typedefintLTDataType;typedefstructListNode{LTDataType data;structListNode*prev;structListNode*next;}LTNode;// 双链表初始化voidLTInit(LTNode**pphead);// 打印voidLTPrint(LTNode*phead);// 尾插voidLTPushBack(LTNode*phead,LTDataType x);// 头插voidLTPushFront(LTNode*phead,LTDataType x);// 尾删voidLTPopBack(LTNode*phead);// 头删voidLTPopFront(LTNode*phead);// 在pos位置之后插入数据voidLTInsert(LTNode*pos,LTDataType x);// 查找LTNode*LTFind(LTNode*phead,LTDataType x);// 删除pos节点voidLTErase(LTNode*pos);// 销毁链表voidLTDestroy(LTNode*phead);双链表函数实现// List.c实现文件#define_CRT_SECURE_NO_WARNINGS#includeList.h// 申请节点LTNode*LTApplyNode(LTDataType x){LTNode*newnode(LTNode*)malloc(sizeof(LTNode));if(newnodeNULL){perror(malloc fail!);exit(1);}newnode-datax;newnode-prevnewnode;newnode-nextnewnode;returnnewnode;}// 初始化// 给双链表创建一个哨兵位voidLTInit(LTNode**pphead){*ppheadLTApplyNode(-1);}// 打印链表voidLTPrint(LTNode*phead){assert(phead);LTNode*pcurphead-next;while(pcur!phead){printf(%d-,pcur-data);pcurpcur-next;}printf(NULL\n);}// 尾插voidLTPushBack(LTNode*phead,LTDataType x){// 头节点不能为空assert(phead);LTNode*newnodeLTApplyNode(x);// 修改节点的前驱指针和后驱指针// phead phead-prev newnodenewnode-prevphead-prev;newnode-nextphead;phead-prev-nextnewnode;phead-prevnewnode;}// 头插voidLTPushFront(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeLTApplyNode(x);// 修改指针指向// phead phead-next newnodenewnode-prevphead;newnode-nextphead-next;phead-next-prevnewnode;phead-nextnewnode;}// 尾删voidLTPopBack(LTNode*phead){// 链表必须有效 且 链表不能为空(只有一个哨兵位)assert(phead);assert(phead-next!phead);LTNode*delphead-prev;// phead del del-prevphead-prevdel-prev;del-prev-nextphead;// 销毁del节点free(del);delNULL;}// 头删voidLTPopFront(LTNode*phead){assert(pheadphead-next!phead);LTNode*delphead-next;phead-nextdel-next;del-next-prevphead;free(del);delNULL;}// 在pos位置之后插入数据voidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newnodeLTApplyNode(x);newnode-prevpos;newnode-nextpos-next;pos-next-prevnewnode;pos-nextnewnode;}// 查找LTNode*LTFind(LTNode*phead,LTDataType x){assert(phead);LTNode*pcurphead-next;while(pcur!phead){if(pcur-datax){// 找到了returnpcur;}pcurpcur-next;}// 没找到returnNULL;}// 删除pos节点voidLTErase(LTNode*pos){assert(pos);// 修改节点指针指向pos-prev-nextpos-next;pos-next-prevpos-prev;// 销毁pos节点free(pos);posNULL;}// 销毁链表// 全部删除 包括头节点// 使用后需要手动将phead置为NULLvoidLTDestroy(LTNode*phead){assert(phead);LTNode*pcurphead-next;while(pcur!phead){LTNode*pnextpcur-next;free(pcur);pcurpnext;}// 现在只剩头节点没有删除free(phead);pcurpheadNULL;}双链表测试// test.c测试文件#define_CRT_SECURE_NO_WARNINGS#includeList.hvoidListTest01(){// 测试初始化LTNode*plistNULL;LTInit(plist);// 测试打印LTPrint(plist);// 测试尾插LTPushBack(plist,1);LTPrint(plist);LTPushBack(plist,2);LTPrint(plist);LTPushBack(plist,3);LTPrint(plist);LTPushBack(plist,4);LTPrint(plist);LTPushBack(plist,5);LTPrint(plist);// 测试头插//LTPushFront(plist, 88);//LTPrint(plist);//LTPushFront(plist, 77);//LTPrint(plist);//LTPushFront(plist, 66);//LTPrint(plist);//LTPushFront(plist, 55);//LTPrint(plist);//LTPushFront(plist, 44);//LTPrint(plist);// 测试尾删//LTPopBack(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);// 测试头删//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);// 在pos位置之后插入数据//LTInsert(plist, 88);//LTPrint(plist);// 测试查找LTNode*findLTFind(plist,3);//if (find)// printf(找到了\n);//else// printf(没找到\n);//LTInsert(find, 88);//LTPrint(plist);// 测试删除pos节点LTErase(find);findNULL;LTPrint(plist);//LTErase(find);//LTPrint(plist);// 测试销毁链表LTDestroy(plist);// 需要手动置为空plistNULL;//LTPrint(plist);}intmain(){ListTest01();return0;}6. 双链表 vs 单链表特性单链表双链表节点结构data nextdata prev next内存占用较小较大多一个指针反向遍历不支持需重新遍历支持O(1) 定位前驱删除指定节点需找到前驱节点直接通过 prev 指针完成插入/删除时间复杂度O(1)已知位置O(1)已知位置双链表的核心优势在于已知某个节点时可以在 O(1) 时间内删除它或访问它的前驱这在 LRU 缓存淘汰算法等场景中非常实用。7. 总结本文详细介绍了 C 语言中双链表的结构定义、初始化、插入、删除、查找、遍历等核心操作并给出了完整的可运行代码。双链表通过增加一个前驱指针换取了双向遍历和 O(1) 删除前驱的能力是很多高级数据结构和算法如 LRU 缓存、双向队列的基础。建议读者动手运行上面的代码并尝试自己实现「按值删除」「链表反转」等扩展功能加深对指针操作的理解。