C / C++ / 系统课时
删除双向链表节点
删除双向链表节点
删除双向链表节点时,真正要处理的是“把目标节点从前驱和后继之间摘掉”。普通中间节点只需重新连接两侧,但头节点、尾节点和单节点链表会出现 NULL 边界。本节给出统一删除函数,并用四种情况验证结果。
学习目标
- 理解删除节点时前驱、后继和头指针各自需要承担的更新职责
- 能用同一段逻辑处理头节点、尾节点、中间节点和唯一节点
- 能在释放内存前完成所有必要的指针重连并验证链表结构
删除的核心关系
假设目标节点是 B,它的前驱是 A、后继是 C。删除后应从 A <-> B <-> C 变成 A <-> C。如果 A 不存在,说明删除的是头节点;如果 C 不存在,说明删除的是尾节点;两者都不存在时,链表原本只有一个节点。

统一思路不是分别写四套删除代码,而是分别判断“前驱是否存在”和“后继是否存在”。这样边界情况会自然落入同一组条件分支。
完整实现
删除函数接收 Node **head,因为删除头节点时必须修改调用者持有的头指针。函数先保存目标节点两侧的指针,再完成重连,最后才释放目标节点。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *prev;
struct Node *next;
} Node;
Node *append(Node **head, int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL) {
return NULL;
}
node->value = value;
node->prev = NULL;
node->next = NULL;
if (*head == NULL) {
*head = node;
return node;
}
Node *tail = *head;
while (tail->next != NULL) {
tail = tail->next;
}
tail->next = node;
node->prev = tail;
return node;
}
void delete_node(Node **head, Node *target) {
if (head == NULL || *head == NULL || target == NULL) {
return;
}
Node *prev = target->prev;
Node *next = target->next;
/* 没有前驱时,target 就是头节点,需要移动 head。 */
if (prev != NULL) {
prev->next = next;
} else {
*head = next;
}
/* 没有后继时,target 就是尾节点,无需再改 next->prev。 */
if (next != NULL) {
next->prev = prev;
}
free(target);
}
void print_list(const Node *head) {
if (head == NULL) {
printf("empty\n");
return;
}
for (const Node *p = head; p != NULL; p = p->next) {
printf("%d ", p->value);
}
printf("\n");
}
int main(void) {
Node *head = NULL;
Node *n10 = append(&head, 10);
Node *n20 = append(&head, 20);
Node *n30 = append(&head, 30);
if (n10 == NULL || n20 == NULL || n30 == NULL) {
return 1;
}
delete_node(&head, n20);
print_list(head);
delete_node(&head, n10);
print_list(head);
delete_node(&head, n30);
print_list(head);
Node *only = append(&head, 99);
if (only == NULL) {
return 1;
}
delete_node(&head, only);
print_list(head);
return 0;
}预期输出
10 30
30
empty
empty第三次删除后链表已经为空;随后重新插入唯一节点 99 再删除,结果仍为空,说明单节点场景也能正确更新头指针。前两行末尾空格来自示例的打印格式。
四种情况如何落入同一逻辑
删除中间节点时,prev 和 next 都存在,因此同时执行 prev->next = next 与 next->prev = prev。删除头节点时 prev == NULL,于是改为 *head = next,再把新头节点的 prev 设为 NULL。
删除尾节点时 next == NULL,只需让前驱的 next 变为 NULL。如果链表只有一个节点,则 prev 与 next 都为 NULL,函数会把 *head 设为 NULL,随后释放唯一节点。
这也是双向链表删除最值得保留的实现方式:针对“是否存在前驱、是否存在后继”编程,而不是为四种位置复制四套逻辑。
释放内存前不要再访问目标节点
free(target) 必须放在重连完成之后。节点一旦释放,再读取 target->prev 或 target->next 就属于未定义行为。因此实现时应先把需要的相邻指针保存到局部变量,再完成链接修改,最后释放。
实际验证时,除了检查打印结果,还应确认新的头节点满足 head == NULL || head->prev == NULL,尾节点满足 tail->next == NULL。只要删除后两侧节点仍互相指向,且头尾边界正确,链表结构就是一致的。