C / C++ / 系统课时

删除双向链表节点

删除双向链表节点

删除双向链表节点时,真正要处理的是“把目标节点从前驱和后继之间摘掉”。普通中间节点只需重新连接两侧,但头节点、尾节点和单节点链表会出现 NULL 边界。本节给出统一删除函数,并用四种情况验证结果。

学习目标

  • 理解删除节点时前驱、后继和头指针各自需要承担的更新职责
  • 能用同一段逻辑处理头节点、尾节点、中间节点和唯一节点
  • 能在释放内存前完成所有必要的指针重连并验证链表结构

删除的核心关系

假设目标节点是 B,它的前驱是 A、后继是 C。删除后应从 A <-> B <-> C 变成 A <-> C。如果 A 不存在,说明删除的是头节点;如果 C 不存在,说明删除的是尾节点;两者都不存在时,链表原本只有一个节点。

双向链表删除节点的四种边界情况

统一思路不是分别写四套删除代码,而是分别判断“前驱是否存在”和“后继是否存在”。这样边界情况会自然落入同一组条件分支。

完整实现

删除函数接收 Node **head,因为删除头节点时必须修改调用者持有的头指针。函数先保存目标节点两侧的指针,再完成重连,最后才释放目标节点。

c
#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;
}

预期输出

text
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。只要删除后两侧节点仍互相指向,且头尾边界正确,链表结构就是一致的。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

删除双向链表节点

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通