---

title: 'Lesson 30: 单链表插入' description: >- 链表节点的内存布局（data+next）、malloc/free动态分配与释放、结构体指针->操作符、头插法O(1)逆序vs尾插法O(n)保序、空链表边界处理、C语言值传递与返回值设计、尾指针实现O(1)尾插、哨兵节点统一空表逻辑、malloc失败处理、头插/尾插的性能对比与应用场景 unit: 'unit2' lesson: 30 navigation: title: '30. 单链表插入'

Lesson 30: 单链表插入

练习任务

难度：易-中

实现单链表的两种基本插入操作：

1. insert_head(head, val) — 头插法：在链表头部插入新值为 val 的节点，返回新的头指针（head）。时间复杂度 O(1)。
2. insert_tail(head, val) — 尾插法：在链表尾部插入新值为 val 的节点，返回头指针（head）。时间复杂度 O(n)。

make_node、list_print、list_free 已提供。你需要填充 insert_head、insert_tail 和 main 中的 TODO 部分。

本课共有 3 组测试用例：

输入 "head 1 2 3"  → 输出 "3 2 1"    （头插法，结果逆序！）
输入 "tail 1 2 3"  → 输出 "1 2 3"    （尾插法，保持原序）
输入 "head 5"      → 输出 "5"        （单元素边界）

提示：链表的本质是“指针跳转”。头插法只需要 2 步——新节点指向原 head，返回新节点——不需要遍历。尾插法需要遍历找到最后一个节点，再把新节点挂上去。特别留意空链表（head == NULL）的情况：两种插入在空表时的行为有何异同？

核心知识点

• 链表节点内存布局 — struct node { int data; struct node *next; }，堆上 malloc 分配，free 释放
• -> 操作符 — 访问指针指向的结构体成员，p->data 等价于 (*p).data
• 头插法 O(1) — 新节点指向原 head，返回新节点；结果逆序
• 尾插法 O(n) — 遍历找到尾节点，挂上新节点；结果保序
• 空链表边界 — head == NULL 时两种插入都返回新节点，但逻辑路径不同
• 返回值设计 — C 语言的值传递特性决定了必须返回新 head（而非通过参数修改）
• 尾指针优化 — 维护 tail 指针可将尾插降至 O(1)
• 哨兵节点 — 在链表头部放置哑节点，统一空表与非空表的操作逻辑
• malloc 失败处理 — 返回 NULL 并在调用处检查

---

代码框架

30_singly_list_insert.c

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

struct node {
    int data;
    struct node *next;
};

/* 创建值为 val 的新节点（已实现） */
struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val;
    p->next = NULL;
    return p;
}

/* 头插法：新节点插入链表头部，成为新的 head */
struct node *insert_head(struct node *head, int val) {
    // 1. 创建值为 val 的新节点
    //    struct node *p = make_node(val);
    // 2. 新节点的 next 指向原来链表的第一个节点
    //    p->next = head;
    // 3. 返回新节点（它就是新的 head）
    //    return p;
}

/* 尾插法：新节点插入链表尾部 */
struct node *insert_tail(struct node *head, int val) {
    // 1. 创建值为 val 的新节点
    //    struct node *p = make_node(val);
    // 2. 如果链表为空（head == NULL），直接返回新节点
    //    if (head == NULL) return p;
    // 3. 遍历到链表尾部：找到最后一个节点
    //    struct node *cur = head;
    //    while (cur->next != NULL) cur = cur->next;
    // 4. 把尾节点的 next 指向新节点；返回原来的 head
    //    cur->next = p; return head;
}

void list_print(struct node *head) {
    struct node *p = head;
    while (p) { printf("%d", p->data); p = p->next; if (p) printf(" "); }
    printf("\n");
}

void list_free(struct node *head) {
    while (head) { struct node *next = head->next; free(head); head = next; }
}

int main(void) {
    char line[256];
    fgets(line, sizeof(line), stdin);
    char *mode = strtok(line, " \n");
    struct node *head = NULL;
    // 循环读取后续数字 token，每个数字转为 int
    // 根据 mode 决定调用 insert_head 还是 insert_tail
    // 提示：strcmp(mode, "head") == 0 判断模式
    list_print(head);
    list_free(head);
    return 0;
}

阅读骨架后，尝试自己填充 // ... 标记的部分。头插法只需要 3 行 C 代码（不含变量声明），尾插需要处理空表的特殊情况。

TIP

先不要往下翻看参考解答。尝试画出指针变化的示意图——新节点的 next 指向谁？head 变成谁？尾插时遍历的终止条件是用 cur 还是 cur->next 来判断？

深度讲解

1. 链表节点的内存模型

1.1 栈与堆 — 为什么链表必须用 malloc？

在进入链表操作之前，先回顾一个根本问题：为什么链表节点必须用 malloc 分配在堆上，而不能用局部变量放在栈上？

stack_vs_heap.c

// 错误：局部变量在栈上，函数返回后内存被回收
struct node *bad_node(int val) {
    struct node n = {val, NULL};
    return &n;                     // 返回栈地址 → 悬垂指针！
}
// 正确：malloc 在堆上分配，函数返回后内存仍有效
struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val;
    p->next = NULL;
    return p;                      // 返回堆地址 → 安全
}

栈 vs 堆的生命周期：

栈（局部变量）:
  make_node 调用开始 → 分配栈帧 → 局部变量 n 存在
  make_node return    → 栈帧销毁 → n 不存在
  调用者拿到的指针    → 指向已回收的内存 → 悬垂指针

堆（malloc）:
  make_node 调用 → malloc 从堆上取一块内存
  make_node return → 栈帧销毁，但堆内存还在
  调用者拿到的指针 → 指向有效的堆内存

WARNING

局部变量的地址在函数返回后失效，这是 C 语言最常见的陷阱之一。任何需要比函数调用寿命更长的数据，都必须通过 malloc（或全局/静态变量）分配在堆上。

1.2 单个节点的内存布局

node_layout.c

struct node {
    int data;              // 数据域
    struct node *next;     // 指针域
};

单个节点在内存中的布局:

        struct node (malloc 分配在堆上)
       ┌────────────┬──────────────┐
       │    data    │     next     │
       │     42     │     NULL     │
       └────────────┴──────────────┘
        sizeof(struct node) = 16 字节（64位系统）
        (int 4 + padding 4 + pointer 8 = 16)

padding（填充字节）是因为 CPU 访问内存时要求地址对齐。编译器在 data 后面自动插入 4 字节填充，使 next 对齐到 8 字节边界。

1.3 make_node 的内部过程

make_node(42) 执行过程:

步骤 1: malloc(sizeof(*p))
        ┌────────────┬──────────────┐
        │  ???????   │   ???????    │  ← 堆上新分配（内容未初始化）
        └────────────┴──────────────┘
        ↑ p

步骤 2: p->data = 42;  p->next = NULL;
        ┌────────────┬──────────────┐
        │     42     │     NULL     │
        └────────────┴──────────────┘
        ↑ p

步骤 3: return p;  → 调用者拿到此指针

TIP

用 sizeof(*p) 而不是 sizeof(struct node) ——如果将来修改了 p 的类型，前者会自动适配。

---

2. 头插法：O(1) 的快速插入

2.1 核心思想

头插法把新节点放在链表最前面——新节点的 next 指向原来的 head，然后新节点成为新的 head。不需要遍历任何节点。

只需要 2 步:
  p->next = head;  // 新节点接上原链表
  return p;        // 新节点成为 head

2.2 步步图解：将 3 头插到链表 1→2 之前

初始状态:
   head
   ┌───┐     ┌────┬────┐    ┌────┬────┐
   │ ●─┼──→  │ 1  │ ●──┼─→ │ 2  │NULL│
   └───┘     └────┴────┘    └────┴────┘

步骤 1: 创建新节点 p (值为 3)
          ┌────┬────┐
          │ 3  │NULL│
          └────┴────┘
          ↑ p

步骤 2: p->next = head;
          ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
          │ 3  │ ●──┼─→ │ 1  │ ●──┼─→ │ 2  │NULL│
          └────┴────┘    └────┴────┘    └────┴────┘
          ↑ p             ↑ head (还没改)

步骤 3: return p; 调用者用 head = insert_head(head, 3) 更新 head

2.3 完整示例：依次头插 1, 2, 3

初始: head = NULL
head = insert_head(head, 1):  head → [1] → NULL
head = insert_head(head, 2):  head → [2] → [1] → NULL
head = insert_head(head, 3):  head → [3] → [2] → [1] → NULL
最终输出: "3 2 1"  ← 逆序！

关键观察：头插法产生的是逆序（后进先出 LIFO），这正是栈的行为。

---

3. 尾插法：O(n) 的顺序插入

3.1 核心思想

尾插法遍历到链表末尾，将新节点挂在最后一个节点的 next 上。需要区分空链表和非空链表。

非空链表:  遍历 → 找到尾节点 → cur->next = p → 返回 head
空链表:    直接返回新节点（新节点就是全部链表）

3.2 完整示例：依次尾插 1, 2, 3

初始: head = NULL
head = insert_tail(head, 1):  1 → NULL
head = insert_tail(head, 2):  1 → 2 → NULL
head = insert_tail(head, 3):  1 → 2 → 3 → NULL
最终输出: "1 2 3"  ← 顺序！

关键观察：尾插法产生的是顺序（先进先出 FIFO），这正是队列的行为。

---

4. 头插法 vs 尾插法：全面对比

维度	头插法 insert_head	尾插法 insert_tail
时间复杂度	O(1)	O(n)
空间复杂度	O(1)	O(1)
结果顺序	逆序（后进先出 LIFO）	顺序（先进先出 FIFO）
是否需要遍历	不需要	需要遍历到尾部
空链表处理	p->next = NULL(head) → return p	if (head == NULL) return p
返回值	新节点（新 head）	原 head（或新节点，当空表时）
指针操作次数	1 次	1 次 + n 次遍历
类似数据结构	栈（Stack）	队列（Queue）
常见用途	反转数据、临时缓冲	保持原始顺序、日志追加

---

5. 为什么返回 struct node * 而不是 void？

5.1 C 语言的值传递陷阱

value_semantics.c

// 错误写法：试图通过参数修改 head
void insert_head_wrong(struct node *head, int val) {
    struct node *p = make_node(val);
    p->next = head;
    head = p;    // 这里只修改了局部变量 head！
}
struct node *my_head = NULL;
insert_head_wrong(my_head, 42);  // my_head 仍然是 NULL！

因为 C 语言的参数传递是按值传递：函数内的 head 是 my_head 的一个副本。修改副本不会影响原值。

correct_return.c

// 正确写法：返回新 head
struct node *insert_head(struct node *head, int val) {
    struct node *p = make_node(val);
    p->next = head;
    return p;      // 返回新 head
}
struct node *my_head = NULL;
my_head = insert_head(my_head, 42);   // 用返回值更新
my_head = insert_head(my_head, 99);   // 链式更新

---

6. 进阶话题

6.1 尾指针：让尾插法变成 O(1)

tail_pointer.c

struct node *head = NULL;
struct node *tail = NULL;
void insert_tail_fast(int val) {
    struct node *p = make_node(val);
    if (head == NULL) { head = tail = p; }
    else { tail->next = p; tail = p; }
}

TIP

Linux 内核的链表（list_head）使用双向循环链表 + 头节点，所有插入/删除都是 O(1)。

6.2 哨兵节点（Sentinel Node）

sentinel.c

struct node *sentinel = make_node(0);
sentinel->next = NULL;
void insert_head_sentinel(struct node *sentinel, int val) {
    struct node *p = make_node(val);
    p->next = sentinel->next;
    sentinel->next = p;  // 不需要特判空链表！
}

哨兵节点模式:
  sentinel         实际数据节点
  [- │ ●] → [1 │ ●] → [2 │ NULL]
  ↑
  C++ std::list 内部正是这样实现的

6.3 malloc 失败处理

malloc_check.c

struct node *insert_head_safe(struct node *head, int val) {
    struct node *p = malloc(sizeof(*p));
    if (p == NULL) { fprintf(stderr, "malloc failed\n"); return head; }
    p->data = val; p->next = head;
    return p;
}

CAUTION

本课练习模板中的 make_node 没有做 malloc 失败检查——教学简化，面试中主动提出是加分点。

---

7. -> 操作符与指针赋值

arrow_operator.c

struct node n = {42, NULL};
struct node *p = &n;
p->data = 100;       // 推荐写法
(*p).data = 100;     // 等价但啰嘦

-> 是 C 语言为"通过指针访问结构体成员"设计的语法糖：

• p->data — 读取/写入节点数据
• p->next — 读取/写入下一个节点地址

IMPORTANT

链表的本质就是指针跳转。a->next = b 不拷贝数据，只是告诉 a："你的下一个节点在地址 b 处"。

参考解答

练习: insert_head 和 insert_tail 完整实现

solution_30_singly_list_insert.c

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

struct node { int data; struct node *next; };
struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val; p->next = NULL; return p;
}
struct node *insert_head(struct node *head, int val) {
    struct node *p = make_node(val);
    p->next = head; return p;
}
struct node *insert_tail(struct node *head, int val) {
    struct node *p = make_node(val);
    if (head == NULL) return p;
    struct node *cur = head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = p; return head;
}
void list_print(struct node *head) {
    struct node *p = head;
    while (p) { printf("%d", p->data); p = p->next; if (p) printf(" "); }
    printf("\n");
}
void list_free(struct node *head) {
    while (head) { struct node *next = head->next; free(head); head = next; }
}
int main(void) {
    char line[256]; fgets(line, sizeof(line), stdin);
    char *mode = strtok(line, " \n");
    struct node *head = NULL;
    char *token;
    while ((token = strtok(NULL, " \n")) != NULL) {
        int val = atoi(token);
        head = (strcmp(mode, "head") == 0) ? insert_head(head, val) : insert_tail(head, val);
    }
    list_print(head); list_free(head);
    return 0;
}

核心逻辑解析：

1. 头插法：3 行核心代码——make_node → p->next = head → return p。O(1) 时间。
2. 尾插法：先判空表（if (head == NULL) return p），然后遍历到 cur->next == NULL。
3. main 循环：strtok(NULL, ...) 反复取 token，根据 mode 调用对应插入函数。
4. 内存释放：list_free 必须在 list_print 之后调用。

课堂讨论

1. 头插和尾插哪种方式在插入大量数据时更高效？
2. 空链表时，头插和尾插的代码路径有何不同？
3. 如果尾插也希望做到 O(1)，需要引入什么额外的数据结构？
4. insert_head 为什么必须返回 struct node * 而不能写成 void？
5. 如果你在链表头部放置一个哨兵节点，头插和尾插的代码会如何简化？

讨论答案

Q1: 头插和尾插哪种更高效？

**头插 O(1) 更高效，但尾插更常用。**头插结果是逆序，尾插是顺序。实际应用中，顺序保持比插入性能更重要。

Q2: 空链表时头插和尾插的代码路径

头插自然兼容空表（p->next = NULL 正确），尾插需要显式特判 if (head == NULL) return p。

Q3: 尾插 O(1) 方案

维护一个 tail 指针，始终指向最后一个节点。代价：需要维护 tail 的状态一致性。

Q4: 为什么必须返回 struct node *？

C 语言的参数传递是按值传递，函数内的 head 是调用者 head 的副本。另一种方案是传二级指针。

Q5: 哨兵节点的简化与代价

哨兵节点统一了空表和非空表的处理逻辑。代价：多占用一个节点（16 字节）。

课后练习

1. 构建并反转: 用尾插法构建链表，再用头插法重新构建，观察顺序差异。Lesson 32 会讲原地反转。

2. 统计链表长度: int list_length(struct node *head) 遍历返回节点总数。

3. 尾插法批量构建: 维护尾指针，O(n) 替代 O(n^2)。

4. 内存泄漏检测: 每个 malloc 必须对应 free。理解链表泄漏场景。

---

参考资料

• K&R《C程序设计语言》§6.7
• 《数据结构与算法分析》§3.2
• man malloc / man free
• Linux Kernel linked list
• 《算法导论》§10.2

"The computing scientist's main challenge is not to get confused by the complexities of his own making." -- Edsger W. Dijkstra