考研算法进阶：双链表插入与删除操作详解

2025年10月14日 互联网

一、双链表基础与考研重要性

双链表（Doubly Linked List）是线性表的一种链式存储结构，每个节点包含三个域：数据域（data）、前驱指针（prev）和后继指针（next）。与单链表相比，双链表支持双向遍历，能高效完成前驱节点的访问。在考研算法中，双链表的操作是数据结构基础题的高频考点，尤其是插入和删除操作，涉及指针的灵活修改，考察考生对动态数据结构的理解能力。

1.1 双链表的结构定义

  1. typedef struct DNode {
  2.     int data;               // 数据域
  3.     struct DNode *prev;     // 前驱指针
  4.     struct DNode *next;     // 后继指针
  5. } DNode, *DLinkList;

关键点：prev和next指针的协同工作是双链表操作的核心，任何修改需同时维护两个方向的链接。

二、双链表的插入操作

插入操作分为三种场景：头部插入、尾部插入和中间插入。考研中常考察中间插入的通用性，需处理前驱和后继节点的指针更新。

2.1 在节点p之后插入新节点s

步骤：

  1. 将s的prev指向p；
  2. 将s的next指向p->next；
  3. 若p->next非空，更新p->next->prev为s；
  4. 更新p->next为s。

代码实现：

  1. int InsertAfterDNode(DNode *p, DNode *s) {
  2.     if (p == NULL || s == NULL) return 0;  // 参数合法性检查
  3.     s->next = p->next;
  4.     s->prev = p;
  5.     if (p->next != NULL) {
  6.         p->next->prev = s;  // 更新原后继节点的前驱
  7.     }
  8.     p->next = s;
  9.     return 1;
  10. }

2.2 头部插入与尾部插入的特例

  • 头部插入：将s的next指向头节点，原头节点的prev指向s，并更新头指针。
  • 尾部插入：遍历至尾节点（next == NULL），执行InsertAfterDNode。

时间复杂度：

  • 头部插入：O(1)
  • 中间/尾部插入：O(n)（需遍历定位）

三、双链表的删除操作

删除操作的核心是断开目标节点与前后节点的链接，并释放内存。考研中常结合边界条件（如删除头/尾节点）考察代码的健壮性。

3.1 删除节点p

步骤：

  1. 若p为空，直接返回错误；
  2. 若p有前驱节点（非头节点），更新p->prev->next为p->next；
  3. 若p有后继节点，更新p->next->prev为p->prev；
  4. 释放p的内存。

代码实现：

  1. int DeleteDNode(DNode *p) {
  2.     if (p == NULL) return 0;  // 空节点检查
  3.     if (p->prev != NULL) {
  4.         p->prev->next = p->next;  // 更新前驱节点的后继
  5.     }
  6.     if (p->next != NULL) {
  7.         p->next->prev = p->prev;  // 更新后继节点的前驱
  8.     }
  9.     free(p);  // 释放内存
  10.     return 1;
  11. }

3.2 删除操作的边界条件

  • 删除头节点：需更新头指针，并处理原头节点的next节点的前驱。
  • 删除尾节点：只需更新尾节点的前驱节点的next为NULL。
  • 删除唯一节点：需同时将头指针置为NULL。

时间复杂度：

  • 定位节点：O(n)
  • 删除操作本身：O(1)

四、考研高频考点与易错点

4.1 指针更新顺序的陷阱

在插入和删除操作中，指针更新的顺序至关重要。例如，若先修改p->next再更新s->prev，可能导致链表断裂。正确顺序应为：

  1. 更新新节点的指针；
  2. 更新原链表节点的指针；
  3. 更新相邻节点的反向指针。

4.2 内存管理细节

  • 删除节点后必须调用free，避免内存泄漏；
  • 插入新节点前需检查内存分配是否成功（如malloc返回NULL）。

4.3 链表为空的特殊情况

  • 插入操作：若链表为空，新节点需同时作为头节点和尾节点；
  • 删除操作：若链表为空或删除唯一节点，需更新头指针为NULL。

五、实战例题解析

例题：在双链表L中，删除所有值为x的节点。

解题思路：

  1. 遍历链表，定位值为x的节点；
  2. 对每个目标节点执行DeleteDNode；
  3. 注意跳过已删除节点的指针（避免重复删除）。

代码实现：

  1. void DeleteAllX(DLinkList *L, int x) {
  2.     DNode *p = (*L)->next;  // 假设L为带头节点的链表
  3.     while (p != NULL) {
  4.         DNode *temp = p;
  5.         p = p->next;
  6.         if (temp->data == x) {
  7.             DeleteDNode(temp);
  8.         }
  9.     }
  10. }

六、总结与备考建议

  1. 理解指针关系：双链表操作的核心是维护prev和next的双向链接，任何修改需同步更新两个方向；
  2. 画图辅助：复杂操作（如中间插入）可通过画图理清指针更新顺序；
  3. 边界条件训练：重点练习头/尾节点、空链表、唯一节点等特殊情况；
  4. 代码规范：养成检查空指针、内存分配失败的习惯，避免低级错误。

备考资源推荐：

  • 《数据结构（C语言版）》严蔚敏：双链表章节的经典教材；
  • LeetCode双链表专题：通过实战巩固操作技巧；
  • 考研真题解析：分析历年考题中双链表的命题规律。

通过系统学习双链表的插入与删除操作，考生不仅能掌握链表动态操作的核心算法，还能提升对指针类问题的解决能力，为考研算法题打下坚实基础。

最新文章