C / C++ / 系统课时
在链表头部插入节点
在链表头部插入节点
头插法把新节点直接放到当前首节点之前,只需修改两个指针关系,不需要移动已有节点。本节通过完整 C 程序实现头部插入,并重点分析两次赋值的先后顺序,避免更新 head 时意外丢失原链表入口。
学习目标
- 能实现单链表头部插入函数并正确更新头指针
- 能解释
new_node->next与head修改的正确顺序 - 能理解头插操作为什么与链表已有节点数量无关
头插实际修改了什么
假设原链表为 20 -> 30 -> NULL,现在要插入值为 10 的节点。操作并不修改节点 20 和节点 30 的数据,只需要让新节点先指向原来的首节点,再让 head 改为指向新节点。

这两次修改的正确顺序是先保存旧入口,再更新新入口:
- 执行
new_node->next = *head,让新节点连接原链表。 - 执行
*head = new_node,让头指针指向新的首节点。
如果先执行第二步,原来的 head 地址就会被覆盖;在没有其他指针保存旧首节点地址的情况下,后续无法再把新节点正确连接到原链表。
用二级指针更新调用者的 head
C 函数参数按值传递。如果函数只接收 Node *head,修改的只是函数内部那份指针副本。要让插入函数直接修改调用者持有的头指针,可以传入 Node **head,也就是头指针变量自身的地址。
下面程序先通过两次头插建立 20 -> 30,随后再次调用同一个函数插入 10,并打印插入前后的链表。
#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;
}预期输出
before: 20 -> 30 -> NULL
after: 10 -> 20 -> 30 -> NULL为什么头插不需要移动已有数据
数组在开头插入元素时,通常要把已有元素整体向后移动,才能腾出连续存储空间。单链表中的节点则通过地址连接,节点本身可以位于任意动态内存位置。因此头插只改变新节点的 next 和 head 两个指针,不需要复制或搬移原节点。
无论链表原来有 2 个节点还是 20000 个节点,头插涉及的指针修改数量都相同,因此其时间复杂度是 。这也是单链表适合频繁在头部加入元素的重要原因。
空链表也使用同一套逻辑
当链表为空时,*head 的值就是 NULL。执行 new_node->next = *head 会自然地把新节点的 next 设置为 NULL,随后 *head = new_node 使它成为唯一节点,因此不需要专门为“插入第一个节点”编写另一套指针逻辑。
真正需要特别处理的是内存分配失败:只有 malloc 成功后才能修改链表。如果分配失败就保持原 head 不变,调用者仍然拥有一条完整可用的旧链表。头插法看似只有两次指针赋值,但“先连接旧链表,再更新头指针”是保证节点不丢失的核心约束。