C / C++ / 系统课时
插入双向链表节点
插入双向链表节点
双向链表插入的难点不在分配节点,而在同时维护前驱和后继关系。只要漏改一条指针,链表就可能断裂或形成错误回链。本节用“在指定节点后插入”为主线,掌握四次指针更新的正确顺序,并用前后遍历验证结构。
学习目标
- 理解插入节点时
prev、next两组关系为什么必须成对维护 - 能实现指定节点后的插入,并正确处理尾部插入
- 能通过正向与反向遍历检查链表是否仍然闭合一致
插入时真正要维护什么
假设当前有 A <-> B,现在把新节点 N 插入到它们之间。插入完成后,需要建立 A <-> N <-> B。这实际上包含四条指针关系:N->prev = A、N->next = B、A->next = N,以及当 B 存在时的 B->prev = N。

关键原则是:先让新节点记住原来的邻居,再让原邻居改指向新节点。如果过早执行 A->next = N,却没有提前保存原来的 B,就可能丢失后半段链表的位置。
完整实现
下面实现 insert_after:在指定节点 pos 后插入一个整数节点。若 pos 原来是尾节点,则 old_next 为 NULL,不需要修改后继节点的 prev。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *prev;
struct Node *next;
} Node;
Node *create_node(int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL) {
return NULL;
}
node->value = value;
node->prev = NULL;
node->next = NULL;
return node;
}
int insert_after(Node *pos, int value) {
if (pos == NULL) {
return 0;
}
Node *node = create_node(value);
if (node == NULL) {
return 0;
}
Node *old_next = pos->next;
/* 先让新节点连接原来的前驱与后继,避免丢失 old_next。 */
node->prev = pos;
node->next = old_next;
/* 原后继存在时,必须把它的 prev 改为新节点。 */
if (old_next != NULL) {
old_next->prev = node;
}
pos->next = node;
return 1;
}
void print_forward(const Node *head) {
for (const Node *p = head; p != NULL; p = p->next) {
printf("%d ", p->value);
}
printf("\n");
}
void print_backward(const Node *tail) {
for (const Node *p = tail; p != NULL; p = p->prev) {
printf("%d ", p->value);
}
printf("\n");
}
void free_list(Node *head) {
while (head != NULL) {
Node *next = head->next;
free(head);
head = next;
}
}
int main(void) {
Node *n10 = create_node(10);
Node *n30 = create_node(30);
if (n10 == NULL || n30 == NULL) {
free(n10);
free(n30);
return 1;
}
n10->next = n30;
n30->prev = n10;
if (!insert_after(n10, 20)) {
free_list(n10);
return 1;
}
print_forward(n10);
print_backward(n30);
free_list(n10);
return 0;
}预期输出
10 20 30
30 20 10 正向与反向结果互为逆序,说明 next 和 prev 两个方向都连接正确。末尾空格来自示例中的 printf("%d ", ...),不影响验证。
为什么修改顺序很重要
最安全的顺序可以概括为“保存后继、连接新节点、修复后继、修复前驱”。其中 old_next = pos->next 是关键:它把插入前的后继节点保存在局部变量中,后续即使修改了 pos->next,也不会失去原链表剩余部分。
尾部插入是这个逻辑的自然边界。此时 old_next == NULL,所以跳过 old_next->prev = node 即可;新节点的 next 保持 NULL,它自然成为新的尾节点。
如何验证插入没有破坏结构
只做正向遍历还不够,因为 next 正确并不能证明 prev 也正确。测试双向链表时,至少应从头到尾遍历一次,再从尾到头遍历一次;两次结果应严格互为逆序。
实际项目中还可以检查局部不变量:若 p->next != NULL,应满足 p->next->prev == p;若 p->prev != NULL,应满足 p->prev->next == p。插入操作只改动少量相邻节点,因此一旦出错,优先检查这四条关系即可。