C / C++ / 系统课时

在链表头部插入节点

在链表头部插入节点

头插法把新节点直接放到当前首节点之前,只需修改两个指针关系,不需要移动已有节点。本节通过完整 C 程序实现头部插入,并重点分析两次赋值的先后顺序,避免更新 head 时意外丢失原链表入口。

学习目标

  • 能实现单链表头部插入函数并正确更新头指针
  • 能解释 new_node->next 与 head 修改的正确顺序
  • 能理解头插操作为什么与链表已有节点数量无关

头插实际修改了什么

假设原链表为 20 -> 30 -> NULL,现在要插入值为 10 的节点。操作并不修改节点 20 和节点 30 的数据,只需要让新节点先指向原来的首节点,再让 head 改为指向新节点。

单链表头插前后与指针修改顺序

这两次修改的正确顺序是先保存旧入口,再更新新入口:

  1. 执行 new_node->next = *head,让新节点连接原链表。
  2. 执行 *head = new_node,让头指针指向新的首节点。

如果先执行第二步,原来的 head 地址就会被覆盖;在没有其他指针保存旧首节点地址的情况下,后续无法再把新节点正确连接到原链表。

用二级指针更新调用者的 head

C 函数参数按值传递。如果函数只接收 Node *head,修改的只是函数内部那份指针副本。要让插入函数直接修改调用者持有的头指针,可以传入 Node **head,也就是头指针变量自身的地址。

下面程序先通过两次头插建立 20 -> 30,随后再次调用同一个函数插入 10,并打印插入前后的链表。

c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

static int push_front(Node **head, int value) {
    Node *new_node = malloc(sizeof *new_node);
    if (new_node == NULL) {
        return 0;
    }

    new_node->value = value;
    /* 必须先保存原来的链表入口,再修改 head。 */
    new_node->next = *head;
    *head = new_node;
    return 1;
}

static void print_list(const Node *head) {
    for (const Node *current = head; current != NULL; current = current->next) {
        printf("%d -> ", current->value);
    }
    puts("NULL");
}

static void free_list(Node *head) {
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void) {
    Node *head = NULL;

    if (!push_front(&head, 30) || !push_front(&head, 20)) {
        free_list(head);
        fprintf(stderr, "allocation failed\n");
        return 1;
    }

    printf("before: ");
    print_list(head);

    if (!push_front(&head, 10)) {
        free_list(head);
        fprintf(stderr, "allocation failed\n");
        return 1;
    }

    printf("after:  ");
    print_list(head);

    free_list(head);
    return 0;
}

预期输出

text
before: 20 -> 30 -> NULL
after:  10 -> 20 -> 30 -> NULL

为什么头插不需要移动已有数据

数组在开头插入元素时,通常要把已有元素整体向后移动,才能腾出连续存储空间。单链表中的节点则通过地址连接,节点本身可以位于任意动态内存位置。因此头插只改变新节点的 next 和 head 两个指针,不需要复制或搬移原节点。

无论链表原来有 2 个节点还是 20000 个节点,头插涉及的指针修改数量都相同,因此其时间复杂度是 O(1)O(1)。这也是单链表适合频繁在头部加入元素的重要原因。

空链表也使用同一套逻辑

当链表为空时,*head 的值就是 NULL。执行 new_node->next = *head 会自然地把新节点的 next 设置为 NULL,随后 *head = new_node 使它成为唯一节点,因此不需要专门为“插入第一个节点”编写另一套指针逻辑。

真正需要特别处理的是内存分配失败:只有 malloc 成功后才能修改链表。如果分配失败就保持原 head 不变,调用者仍然拥有一条完整可用的旧链表。头插法看似只有两次指针赋值,但“先连接旧链表,再更新头指针”是保证节点不丢失的核心约束。

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

目录与阅读设置

阅读设置

17

记录一个想法

在链表头部插入节点

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

登录哪都通