C++ 链表、节点与指针复习｜C++ 第 17 课

Easy explanation

链表像一场每个人只知道下一站的接力。

火车车厢彼此连接，不需要整列占用一块连续空间。插入新车厢只要改变附近连接，不必把后面所有车厢搬走；但想找第十节车厢时，必须从车头一节节走过去。链表的优点和代价都来自这种连接方式。

手写节点能帮助理解指针，但实际项目优先使用标准容器或智能指针。每个节点的 next 表示谁拥有下一个节点，使用 unique_ptr 可以让整条链从头节点开始自动释放，避免手写 delete 和泄漏。

目标 1画出节点、数据和 next 的关系

目标 2实现链表头部插入与遍历

目标 3理解插入删除怎样修改连接

目标 4比较 vector、list 与链表的适用场景

C++ 链表、节点与指针复习通俗学习插图 — 节点不必连续，只需用地址保持正确顺序和所有权。

Core concepts

先把四个核心知识点说清楚。

01

节点

struct Node { int value; unique_ptr<Node> next; };

节点包含数据和下一节点。最后一个节点的 next 为空，表示链结束。

02

头节点

unique_ptr<Node> head;

head 是进入整条链的入口。失去 head 且没有其他拥有者，就无法再访问后续节点。

03

顺序遍历

for (Node* p = head.get(); p; p = p->next.get())

从头开始反复跟随 next，每个节点访问一次，按位置查找是 O(n)。

04

标准 list

list<string> songs;

双向链表支持已知位置的快速插入删除，但不支持 songs[5] 这种随机下标。

newNode->next = move(head); head = move(newNode);

头插先让新节点接住旧链，再把 head 移到新节点。

auto next = move(current->next);

修改连接前先保存后半段所有权，避免节点意外销毁。

songs.insert(position, "New song");

std::list 在已有迭代器位置插入，不移动其他节点。

distance(list.begin(), it)

链表计算位置需要逐步前进，不是常数时间。

Complete examples

两个例子，把知识变成能运行的程序。

Example 1

例子一：智能指针实现头插链表

pushFront 创建节点，把旧 head 的所有权移动给新节点，再把新节点交给 head。顺序不能写反，否则可能丢掉旧链。

打印只观察节点，不取得所有权，所以使用普通 Node 指针遍历。拥有关系与观察关系要分开。

自动管理节点生命期

struct Node
{
    int value;
    unique_ptr<Node> next;
};

void pushFront(unique_ptr<Node>& head, int value)
{
    auto node = make_unique<Node>();
    node->value = value;
    node->next = move(head);
    head = move(node);
}

void print(const unique_ptr<Node>& head)
{
    for (Node* p = head.get(); p != nullptr; p = p->next.get())
        cout << p->value << ' ';
}

依次插入 10、20、30链表：30 -> 20 -> 10 -> null

Example 2

例子二：使用 std::list 管理播放列表

list 的迭代器像指向节点的位置。找到当前歌曲后，next(it) 表示它后面的位置，insert 在那里加入新歌。

查找歌曲仍要从头遍历，因此 list 并不会让所有操作都变快。容器选择必须针对主要操作。

在当前歌曲后插入

list<string> songs{"Intro", "Ocean", "Finale"};
auto current = find(songs.begin(), songs.end(), "Ocean");
if (current != songs.end())
    songs.insert(next(current), "Night Sky");

for (const string& song : songs)
    cout << song << '\n';

IntroOceanNight SkyFinale

Algorithm thinking

复杂度取决于“是否已经知道位置”。

链表在已知节点位置时插入删除很快，因为只改几个连接；若先要按编号寻找位置，寻找本身仍是 O(n)。因此“链表插入是 O(1)”这句话必须带条件，不能脱离场景。

修改指针前要画图并标出所有权。先保存不能丢失的后半段，再改变连接，最后移动入口。每完成一步就确认所有节点仍然能从 head 到达。对于初学者，画三节点小图比盯着代码更有效。

1
画出原连接
标明 head、当前节点、前驱节点和 next 指向。
2
保存后半段
任何可能被覆盖的 next 都要先保存，避免失去入口。
3
修改局部连接
按图逐条改变，移动 unique_ptr 后不要再当作拥有者使用。
4
检查可达性
从 head 遍历，确认节点数量、顺序和结尾 nullptr。

Common mistakes

这些错误很常见，学会自己排查。

1

丢失头节点

直接覆盖 head 会让旧链失去入口，必须先把所有权交给新节点。

2

形成环

错误连接可能让节点再次指向前面，遍历永不结束。

3

移动后继续使用

unique_ptr 被 move 后通常为空，原变量不再拥有节点。

4

以为 list 可随机访问

链表没有常数时间下标，advance 也需要逐节点移动。

本课通用调试法

先准备一个最小输入，只保留能够重现问题的几行数据；再在关键步骤输出变量值，确认程序究竟在哪一步偏离预期。编译错误从第一条开始处理，运行错误则比较“实际结果”和“期望结果”。修复后别只重跑原来的例子，还要增加空输入、边界值和错误输入，防止问题换一个形式再次出现。

Homework

第 17 课课后作业：从模仿到独立完成。

建议按顺序完成。前四题帮助巩固语法和基本操作，第五到第七题要求把多个知识点组合起来，第八题是小项目。每道题都要先写输入、处理、输出三行计划，再开始敲代码；程序运行后至少测试正常情况、边界情况和错误情况。

1

手画链表

画出头插 3、5、7 后的每一步，标出 head、value、next 和 null。

2

计算长度

编写 size 函数遍历智能指针链表，分别测试空链、一节点和多节点。

3

查找节点

返回第一个目标值的观察指针，找不到返回 nullptr，不转移所有权。

4

删除头部

实现 popFront，把 head 移动到下一个节点，并输出被删除的值。

5

尾部插入

找到最后节点后添加，比较它与头插在空链和长链中的操作次数。

6

删除目标

删除第一个匹配节点，正确连接前后两段并处理目标在头部。

7

反转思路

先画图，再尝试用 prev、current、next 三个角色反转链表，逐步输出。

8

播放列表项目

用 std::list 实现插入、删除、上一首、下一首和循环播放，处理空列表。

本课验收标准：能画出每次连接变化；智能指针链表离开作用域可自动释放；空链、头部和尾部操作正确；能说明 vector 与 list 在访问和插入方面的取舍。

提交内容应包括源代码、三组测试输入与输出、一个曾经出现的错误及修复方法。最后请用自己的话解释本课最重要的概念；如果只能照着代码念，还需要再独立重写一次核心例子。

Lesson 17 summary

链表用连接换取灵活插入，也放弃了快速下标访问。

Nodenextheadunique_ptrstd::list

下一课会学习递归与回溯。链表遍历已经展示“处理当前，再进入剩余部分”的思想，递归会把这种分解写成函数调用。

进入第 18 课返回第 16 课查看课程大纲