第35篇 双链表的增删查改实现

在各类链表结构中，单链表与带头双向循环链表是最具代表性的两种。深入剖析并掌握这两种核心结构，便能触类旁通，轻松推导并实现其他衍生类型。基于此，本文将重点对双链表（即带头双向循环链表）展开详细解析。

首先将结点类型和结点数据重命名：

typedef int itndate; typedef struct itnode { itndate val; struct itnode* prev; struct itnode* next; }itn;

接下来进行节点的创建与初始化。由于双链表采用带头结构，其哨兵节点可作为链表的固定操作入口，因此无需像单链表那样传递二级指针来修改头指针的指向。我们只需动态创建一个节点作为哨兵位，并使其前驱与后继指针均指向自身，即可完成链表的初始化。

1. 思路

在堆区动态分配一个节点，并将其前后指针指向自身，构建一个最小的带头双向循环链表（自环）。

2. 参数

无。

3. 返回值

itnode*：指向新创建并初始化完成的哨兵节点指针。

4. 核心逻辑实现

• 申请内存：使用malloc为节点分配内存。
• 初始化自环：将prev和next指针均指向节点自身。
• 返回指针：将节点地址返回给调用方。

5. 代码

itnode* buynode() { itnode* phead = (itnode*)malloc(sizeof(itnode)); assert(phead); phead->prev = phead; phead->next = phead; return phead; }

再来分装打印函数：

1. 思路

利用带头双向循环链表的“自环”特性，将“当前节点的下一个节点是否为头节点”作为遍历的终止条件，依次访问并输出有效数据节点。

2. 参数

itnode* phead：指向链表哨兵节点（头节点）的指针。

3. 返回值

无（void）。

4. 核心逻辑实现

• 循环遍历：当phead->next != phead时，说明还未绕回哨兵节点，继续遍历。
• 输出数据：打印当前节点的值。
• 指针后移：将指针移动到下一个节点。
• 换行：遍历结束后打印换行符。

5. 代码

void print(itnode* phead) { assert(phead); while (phead->next != phead) { printf("%d ", phead->val); phead = phead->next; } printf("\n"); }

好那么开始进行增删查改的接口的编写：

尾插：

1. 思路

在带头双向循环链表中，尾插操作本质上是在“哨兵节点（头节点）”与“当前尾节点（即头节点的前驱节点）”之间插入新节点。通过调整这四个节点的前后指针指向，即可将新节点无缝接入链表尾部。

2. 参数

itnode* phead：指向链表哨兵节点（头节点）的指针、新结点存储的数值。

3. 返回值

无（void）。

4. 核心逻辑实现

• 创建新节点：调用buynode()动态分配并初始化新节点。
• 设置新节点指针：将新节点的prev指向原尾节点（phead->prev），next指向头节点（phead）。
• 更新原尾节点指针：将原尾节点的next指向新节点。
• 更新头节点指针：将头节点的prev指向新节点，使其成为新的尾节点。

5. 代码

void push_back(itnode* phead, itndate val) { assert(phead); // 1. 创建新节点并赋值 itnode* newnode = buynode(); newnode->val = val; // 2. 将新节点接入链表尾部 newnode->prev = phead->prev; newnode->next = phead; // 3. 更新原尾节点和头节点的指针 phead->prev->next = newnode; phead->prev = newnode; }

头插：

1. 思路

在带头双向循环链表中，头插操作是在“哨兵节点（头节点）”与“当前第一个有效节点（即头节点的后继节点）”之间插入新节点。通过调整这四个节点的前后指针指向，将新节点无缝接入链表头部。

2. 参数

• itnode* phead：指向链表哨兵节点（头节点）的指针。
• itndate x：待插入节点的数据值。

3. 返回值

无（void）。

4. 核心逻辑实现

• 创建新节点：调用buynode()动态分配并初始化新节点，并将传入的数据x赋值给新节点。
• 设置新节点指针：将新节点的prev指向头节点（phead），next指向原首节点（phead->next）。
• 更新原首节点指针：将原首节点的prev指向新节点。
• 更新头节点指针：将头节点的next指向新节点，使其成为新的首节点。

5. 代码

void push_front(itnode* phead, itndata x) { assert(phead); // 1. 创建新节点并赋值 itnode* newnode = buynode(); newnode->val = x; // 2. 将新节点接入链表头部 newnode->prev = phead; newnode->next = phead->next; // 3. 更新原首节点和头节点的指针 phead->next->prev = newnode; phead->next = newnode; }

尾删：

1. 思路

在带头双向循环链表中，尾删操作需要摘除“当前尾节点（即头节点的前驱节点）”。通过调整头节点与新的尾节点之间的指针指向，将原尾节点从链表中剥离，最后释放其占用的堆区内存。

2. 参数

itnode* phead：指向链表哨兵节点（头节点）的指针。

3. 返回值

无（void）。

4. 核心逻辑实现

• 定位待删节点：通过phead->prev找到当前的尾节点，并用临时指针del记录其地址。
• 断开尾节点连接：将头节点的prev指向原尾节点的前驱节点（即新的尾节点）。
• 建立新循环：将新的尾节点的next指针重新指向头节点，维持循环结构。
• 释放内存：调用free释放原尾节点占用的内存，并将临时指针置为NULL，防止悬空指针。

5. 代码

补充说明：若链表为空时调用尾删，会导致哨兵节点被错误释放。应在代码中补充该防御性判断。

void pop_back(itnode* phead) { assert(phead); // 1. 边界检查：如果链表为空（头节点自环），则无需删除，直接返回 if (phead->next == phead) { return; } // 2. 定位待删除的尾节点 itnode* del = phead->prev; // 3. 重新连接头节点与新的尾节点 phead->prev = del->prev; del->prev->next = phead; // 4. 释放原尾节点内存，并将指针置空 free(del); del = NULL; }

头删 ：

1. 思路

在带头双向循环链表中，头删操作需要摘除“当前首节点（即头节点的后继节点）”。通过调整头节点与新的首节点之间的指针指向，将原首节点从链表中剥离，最后释放其占用的堆区内存。

2. 参数

itnode* phead：指向链表哨兵节点（头节点）的指针。

3. 返回值

无（void）。

4. 核心逻辑实现

• 边界检查：判断链表是否为空（即phead->next == phead），若为空则直接返回，防止非法操作。
• 定位待删节点：通过phead->next找到当前的首节点，并用临时指针del记录其地址。
• 断开首节点连接：将头节点的next指向原首节点的后继节点（即新的首节点）。
• 建立新循环：将新的首节点的prev指针重新指向头节点，维持循环结构。
• 释放内存：调用free释放原首节点占用的内存，并将临时指针置为NULL，防止悬空指针。

5. 代码

void pop_front(itnode* phead) { // 1. 边界检查：如果链表为空（头节点自环），则无需删除，直接返回 if (phead->next == phead) { return; } // 2. 定位待删除的首节点 itnode* del = phead->next; // 3. 重新连接头节点与新的首节点 phead->next = del->next; del->next->prev = phead; // 4. 释放原首节点内存，并将指针置空 free(del); del = NULL; }

find查找数据：

1. 思路

在带头双向循环链表中，查找操作需从哨兵节点的后继节点（即第一个有效节点）开始依次遍历。由于是循环结构，遍历的终止条件应为“当前节点回到哨兵节点”，而非单链表中的NULL。若遍历过程中找到目标值，则直接返回该节点的指针；若绕回哨兵节点仍未找到，则返回NULL。

2. 参数

• itnode* phead：指向链表哨兵节点（头节点）的指针。
• itndate x：待查找的目标数据值。

3. 返回值

itnode*：若找到目标数据，返回指向该节点的指针；若未找到，返回NULL。

4. 核心逻辑实现

• 边界断言：使用assert确保传入的哨兵节点指针不为空。
• 遍历链表：将指针移动至phead->next，在当前节点 != phead的条件下进行循环。
• 数据比对：在循环中判断当前节点的val是否等于目标值x，若相等则立即返回当前节点的指针。
• 指针后移：若当前节点不匹配，则将指针向后移动。
• 返回未找到：若循环正常结束（即已遍历完所有有效节点），返回NULL。

5. 代码。

itnode* find(itnode* phead, itdata x) { assert(phead); // 从第一个有效节点开始遍历，直到绕回哨兵节点为止 itnode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; }

指定位置删除：

1. 思路

在带头双向循环链表中，删除指定位置节点的操作，本质上是将其从链表中“摘除”。通过修改该节点的前驱和后继节点的指针，使它们互相指向，从而将目标节点从双向链表中剥离，最后释放该节点占用的堆区内存。

2. 参数

itnode* pos：指向待删除节点的指针。

3. 返回值

无（void）。

4. 核心逻辑实现

• 边界断言：使用assert确保传入的待删除节点指针不为空。
• 断开前驱连接：将待删除节点的前驱节点的next指针，指向待删除节点的后继节点。
• 断开后继连接：将待删除节点的后继节点的prev指针，指向待删除节点的前驱节点。
• 释放内存：调用free释放待删除节点占用的内存，并将临时指针置为NULL，防止悬空指针。

5. 代码

void delect(itnode* pos) { assert(pos); // 1. 将 pos 从链表中摘除 pos->prev->next = pos->next; pos->next->prev = pos->prev; // 2. 释放节点内存，并将指针置空 free(pos); pos = NULL; }

指定位置之前插入:

1. 思路

在带头双向循环链表中，在指定节点pos之前插入新节点。该操作本质上是修改四个节点的指针指向：将新节点无缝接入pos的前驱节点与pos之间。

2. 参数

• itnode* pos：指定插入位置的节点指针（新节点将插入到该节点之前）。
• itndate x：待插入节点的数据值（注：原代码类型名itndate存在拼写错误，已修正为itdata）。

3. 返回值

无（void）。

4. 核心逻辑实现

• 边界断言：使用assert确保传入的指定位置节点指针不为空。
• 创建新节点：调用buynode()动态分配并初始化新节点，并将传入的数据x赋值给新节点。
• 设置新节点指针：将新节点的next指向pos，prev指向pos的前驱节点。
• 更新前后节点指针：将pos的前驱节点的next指向新节点，并将pos的prev指向新节点，完成链表的重新链接。

5. 代码

void insert_front(itnode* pos, itndata x) { assert(pos); // 1. 创建新节点并赋值 itnode* newnode = buynode(); newnode->val = x; // 2. 将新节点接入 pos 之前 newnode->next = pos; newnode->prev = pos->prev; // 3. 更新 pos 的前驱节点和 pos 本身的指针 pos->prev->next = newnode; pos->prev = newnode; }

指定位置之后插入:

1. 思路

在带头双向循环链表中，在指定节点pos之后插入新节点。该操作本质上是修改四个节点的指针指向：将新节点无缝接入pos与pos的后继节点之间。

2. 参数

• itnode* pos：指定插入位置的节点指针（新节点将插入到该节点之后）。
• itndate x：待插入节点的数据值（注：原代码类型名itndate存在拼写错误，已修正为itdata）。

3. 返回值

无（void）。

4. 核心逻辑实现

• 边界断言：使用assert确保传入的指定位置节点指针不为空。
• 创建新节点：调用buynode()动态分配并初始化新节点，并将传入的数据x赋值给新节点。
• 设置新节点指针：将新节点的next指向pos的后继节点，prev指向pos。
• 更新前后节点指针：将pos的后继节点的prev指向新节点，并将pos的next指向新节点，完成链表的重新链接。

5. 代码

void insert_back(itnode* pos, itndata x) { assert(pos); // 1. 创建新节点并赋值 itnode* newnode = buynode(); newnode->val = x; // 2. 将新节点接入 pos 之后 newnode->next = pos->next; newnode->prev = pos; // 3. 更新 pos 的后继节点和 pos 本身的指针 pos->next->prev = newnode; pos->next = newnode; }

销毁链表（destroy）:

1. 思路

销毁带头双向循环链表需要释放链表中所有的节点内存。首先通过循环遍历，逐个摘除并释放有效数据节点；当所有有效节点释放完毕后，链表将退化为仅有哨兵节点（头节点）自环的状态，最后释放哨兵节点本身，完成整个链表的销毁。

2. 参数

itnode* phead：指向链表哨兵节点（头节点）的指针。

3. 返回值

无（void）。

4. 核心逻辑实现

• 边界断言：使用assert确保传入的头节点指针不为空。
• 循环释放有效节点：当phead->next != phead时，说明链表中仍有有效数据节点。在循环中，定位当前首节点pcur及其后继节点next，将头节点的next指向next（完成摘除），随后释放pcur的内存。
• 释放哨兵节点：当循环结束时，所有有效节点已被清空，最后释放哨兵节点phead的内存。

5. 代码

void destroy(itnode* phead) { assert(phead); // 1. 循环遍历，逐个摘除并释放有效数据节点 while (phead->next != phead) { itnode* pcur = phead->next; itnode* next = pcur->next; phead->next = next; free(pcur); pcur = NULL; } // 2. 释放哨兵节点（头节点）本身 free(phead); phead = NULL; }

OK ，那么到这里链表的学习先告一段落，

🌟 写在最后
代码写完了，但我想对正在阅读这篇博客的你说几句心里话。
最近身边有很多同学在迷茫、害怕，大体原因是只能靠自己一个人在这个世界打拼，无依无靠；而世界又在不断变化进步，不知道自己的出路在哪里。
我把送给他们的话，也送给正在屏幕前努力的你：
保持乐观，悲观者正确，乐观者前行。
相信时间的力量，就不必问何时才有回报。
拥有坚持的毅力，就不必在意暂时的苟且。
保持每天的进步，就不必对未来感到迷茫。
愿你在代码的世界里披荆斩棘，也在人生的道路上步履不停。