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。

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

预期输出

text
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。插入操作只改动少量相邻节点,因此一旦出错,优先检查这四条关系即可。

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

目录与阅读设置

阅读设置

17

记录一个想法

插入双向链表节点

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

登录哪都通