【数据结构入坑指南（四.2）】--《从单链到双链的进阶，读懂“双向奔赴”的算法之美与效率权衡》
🔥@晨非辰Tong：个人主页
👀专栏：《C语言》、《数据结构与算法》、《数据结构与算法刷题集》
💪学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”
引言：征服了单链表，却总感束缚？无法回溯的遍历、繁琐的节点删除...是时候解锁双向链表，体验指针自由穿梭的真正力量。
目录
一、链表的分类、说明
--根据表格知道：链表的组合共有8种。那么具体是什么？
1.1 带头、不带头
--“头节点”：一般是指不存储任何有效数据的节点。
--在前面的学习中，也说过“头节点”或者“首节点”，但所谓的节点是存储着有效数据的节点，是为了好说明。
--这里的头指的是前面刷题提到过的“哨兵位”——>不存储任何有效数据，只是用来指向的第一个节点（存储有效数据）。
1.2 单向、双向
--对比可以看到，双向链表比单向链表多一个指针（称为前驱指针）——>存储上一个节点地址，都有的指针在双链表称为后继指针。
--对于这样三个指针的节点结构：1指针-->前驱指针，2指针-->存储数据值，3指针-->后继指针。
1.3 循环、不循环
--对于前面所学单链表，到了尾节点就会指向NULL——>这就是不循环。
--但是对于循环的链表——>尾节点的后继指针（next）会指向第一个节点。（这样循环往复）
虽然说了有8种链表，但是常用的组合为：不带头单向不循环链表 和 带头双向循环链表。
--下面见识一下双向链表。
二、双向链表
2.1 基本信息介绍
2.1 定义、结构
所谓双向链表：就如上面图示一样——>首先有头节点，然后存在着前驱指针指向前一个节点-->这就是双向，最后尾节点的后继指针指向头节点形成循环。
DList.h文件 #include <stdio.h> #include <stdlib.h> //定义双链表基本结构（节点） typedef int DLTDataType; typedef struct DListNode { DLTDataType data; struct DListNode* next;//指向下一个节点 struct DListNode* prev;//指向前一个节点 }DLTNode;2.2 “哨兵位”的初始化（准备工作）
--在实现链表的功能时，首先实现空链表：先将“哨兵位”的结构整出来。
双链表最开始为空，意味着“哨兵节点”始终指向自己（不是连“哨兵节点”都没有）——>前驱指针、后继指针都指向头节点本身。
DList.c文件 #include "DList.h" //定义_初始化 void DLTInit(DLTNode** pphead)//二级指针接收“哨兵位”地址-->改变结构（test.c传的头节点） { //申请空间 *pphead = (DLTNode*)malloc(sizeof(DLTNode));//*pphead 是 phead //判断非空 if (*pphead == NULL) { perror("malloc"); exit(1);//申请失败 } (*pphead)->data = -1;//随便一个值，后续不用 (*pphead)->next = (*pphead)->prev = *pphead;//指向自己 }--“哨兵节点”初始化时的数据指针存储什么数据？
：随便放什么值，以后也不会用到 head->data。
test.c文件 #include "DList.h" //测试 void test01() { DLTNode* plist = NULL;//不是双向链表，初始化 //初始化 DLTInit(&plist);//传址 } int main() { test01(); return 0; }
--可以看到：因为是传址调用，实参（plist）与形参（*pphead）节点结构一致，初始化成功。
2.2 链表基本功能实现
2.2.1 双链表尾插
--要尾插新节点，就要改变多处指针的指向。
--进行改变，先对newnode部分进行（若先变head、d3，导致指向变化，newnode无从下手），两图对照写。
--先将创建新节点定义出来：封装函数
DList.c文件 #include "DList.h" //定义_由数值创建新节点 DLTNode* DLTBuyNode(DLTDataType x) { //申请空间 DLTNode* newnode = (DLTNode*)malloc(sizeof(DLTNode)); //判断非空 if (newnode == NULL) { perror("malloc"); exit(1);//申请失败 } newnode->data = x; newnode->next = newnode->prev = newnode;//新节点先指向自己 return newnode; } --新申请的节点，刚开始前驱指针、后继指针都要指向自己，在后续的指向改变中完成变化。
DList.c文件 #include "DList.h" //定义_尾插 void DLTPushBack(DLTNode* phead, DLTDataType x)//一级指针，只需要知道是哪个链表 { //断言 assert(phead); //创建新节点 DLTNode* newnode = DLTBuyNode(x); //先对newnode进行改变，防止phead、尾节点指向改变 newnode->prev = phead->prev; newnode->next = phead; phead->prev->next = newnode;//->prev->next代表尾节点next phead->prev = newnode; } test.c文件 #include "DList.h" void test01() { DLTNode* plist = NULL;//不是双向链表，初始化 //初始化 DLTInit(&plist);//传址 //尾插 DLTPushBack(plist, 1); DLTPushBack(plist, 2); DLTPushBack(plist, 3); DLTPushBack(plist, 4); } int main() { test01(); return 0; }
2.2.2 双链表头插
--在头节点后，第一个节点前进行插入。
对于关于d1节点相关指针的改变，通过 head 头节点的相关指针进行改变。
DList.c文件 #include "DList.h" //定义_头插 void DLTPushFront(DLTNode* phead, DLTDataType x) { //断言 assert(phead); //申请新节点 DLTNode* newnode = DLTBuyNode(x); newnode->next = phead->next; newnode->prev = phead; phead->next->prev = newnode; phead->next = newnode; }test.c文件 #include "DList.h" void test01() { DLTNode* plist = NULL;//不是双向链表，初始化 //初始化 DLTInit(&plist);//传址 //头插 DLTPushFront(plist, 1); DLTPushFront(plist, 2); DLTPushFront(plist, 3); DLTPushFront(plist, 4); } int main() { test01(); return 0; }
2.2.3 双链表尾删
--在实现尾删操作前，先来定义判空的函数
//定义-判空 bool DLTEmpty(DLTNode* phead) { assert(phead); return phead->next == phead; }--对于打印链表：为了体现尾删、头删的效果，将链表进行打印
//定义_打印 void DLTPrint(DLTNode* phead) { DLTNode* pcur = phead->next;//指向第一个节点 //循环遍历 while (pcur != phead) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); }--对于尾删：
尾删操作：将头节点及尾节点的上一个节点的前驱指针、后继指针改变指向，都不再指向尾节点。
DList.c文件 #include "DList.h" //定义_尾删 void DLTPopBack(DLTNode* phead) { assert(!DLTEmpty(phead)); //首先定义指针指向尾节点 DLTNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; //对del节点空间进行释放 free(del); del = NULL; }test.c文件 #include "DList.h" void test01() { DLTNode* plist = NULL;//不是双向链表，初始化 //初始化 DLTInit(&plist);//传址 //尾插 DLTPushBack(plist, 1); DLTPushBack(plist, 2); DLTPushBack(plist, 3); DLTPushBack(plist, 4); DLTPrint(plist); //尾删 DLTPopBack(plist); DLTPrint(plist); DLTPopBack(plist); DLTPrint(plist); DLTPopBack(plist); DLTPrint(plist); DLTPopBack(plist); DLTPrint(plist); } int main() { test01(); return 0; }
2.2.4 双链表头删
--对于头删的操作，画图弄清楚节点的前驱指针、后继指针的指向关系，即将头节点、第二个节点的前驱指针、后继指针不在指向第一个节点。
DList.c文件 #include "DList.h" //定义_头删 void DLTPopFront(DLTNode* phead) { assert(!DLTEmpty(phead)); //定义指针指向第1个节点 DLTNode* del = phead->next; phead->next = del->next; del->next->prev = phead; //释放del free(del); del = NULL; }先定义指针指向第一个节点，再根据图示，改变头节点后继指针指向第二个节点，改变第二个节点的前驱指针指向头节点。
test.c文件 #include "DList.h" void test01() { DLTNode* plist = NULL;//不是双向链表，初始化 //初始化 DLTInit(&plist);//传址 //尾插 DLTPushBack(plist, 1); DLTPushBack(plist, 2); DLTPushBack(plist, 3); DLTPushBack(plist, 4); DLTPrint(plist); //头删 DLTPopFront(plist); DLTPrint(plist); DLTPopFront(plist); DLTPrint(plist); DLTPopFront(plist); DLTPrint(plist); DLTPopFront(plist); DLTPrint(plist); } int main() { test01(); return 0; }
回顾：
《面试高频数据结构：单链表与顺序表之争，读懂“不连续”之美背后的算法思想》
《链表面试基础看点：这里不止“快慢指针”的完美实现，更懂“哨兵节点”的巧妙运用》
结语：从单链表的“单向枷锁”中解脱出来，我们初步领略了双向链表在头尾操作上的简洁与高效。但它的威力远不止于此。如何利用双指针的便利，实现比单链表更优雅、更高效的任意位置操作？这一切的背后，又隐藏着哪些不容错过的细节陷阱？下一篇，我们将拨开迷雾，一探究竟。
