# 链表

> 计算机科学 · CIE A-Level 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u10-linked-lists/

本模块讲解链表的结构、常用操作、优缺点和时间复杂度，链表是CIE A-Level计算机科学两张试卷都常考的核心动态线性数据结构。

**先修:** [数组与静态数据结构](https://www.owlsprep.com/zh/study/cie-9618-u10-arrays/); [指针与内存寻址](https://www.owlsprep.com/zh/study/cie-9618-u04-memory-management/)

## 学习目标

- 描述单向链表和双向链表的结构
- 实现链表的常用操作（插入、删除、遍历）
- 比较链表与静态数组的性能
- 解释链表在不同使用场景下的优缺点
- 写出常用链表操作的时间复杂度

## 链表的结构

链表是一种动态线性数据结构，每个元素（称为**节点**）同时存储数据和指向序列中下一个节点的指针。与数组不同，节点不需要存储在连续内存位置，因此链表大小可以在运行时动态增减。

**节点** — 链表的基本单元，存储数据值以及指向链表中下一个节点的引用（指针）。

*记法:* Node { data, next_pointer }

*例:* 存储整数`42`的节点会有`data = 42`，`next`指针指向下一个节点，如果是最后一个节点则为`null`。

> **info**
>
> 单向链表仅存储指向后继节点的指针，因此只能向前遍历。双向链表同时存储后继和前驱指针，支持双向遍历，但额外指针会占用更多内存。

**例题:** 绘制并描述一个带头指针、存储值`[10, 20, 30]`的单向链表结构。

1. 创建三个独立节点，分别存储对应数据值：节点1 = 10，节点2 = 20，节点3 = 30
2. 设置节点1的next指针指向节点2
3. 设置节点2的next指针指向节点3
4. 设置节点3的next指针为`null`，标记链表结束
5. 设置头指针指向第一个节点节点1

## 常用链表操作

链表的四个核心操作是遍历、查找、插入和删除。每个操作都遵循指针操作规则来维护链表结构。

- **遍历**：从头节点开始，通过next指针从一个节点移动到下一个节点，直到到达`null`
- **查找**：遍历链表，找到存储目标数据值的节点
- **插入**：在链表的头部、中间或尾部添加新节点
- **删除**：从链表的任意位置移除已有节点

**例题:** 在链表`[10, 20, 30]`中值为10的节点后插入一个值为15的新节点。

1. 创建新节点，将其数据值设为15
2. 从头开始遍历，找到数据为10的节点，将其记为`current`
3. 将新节点的next指针设为`current.next`（这样就保存了指向20的引用）
4. 更新`current.next`指向新节点
5. 新链表现在是`[10, 15, 20, 30]`

**例题:** 从链表`[10, 20, 30]`中删除值为20的节点。

1. 从头节点开始，遍历链表同时跟踪当前节点和前驱节点
2. 当当前节点的数据等于20时停止遍历；这里前驱节点是10
3. 将前驱节点的next指针设为当前节点的next指针（即指向30）
4. 从内存中移除当前节点，避免内存泄漏
5. 更新后的链表现在是`[10, 30]`

> **考试提示:** 一定要先设置新节点的指针，再修改原有节点的指针。这样可以避免丢失链表剩余部分的引用。

## 链表 vs 静态数组

链表和数组都是线性数据结构，但常用操作的性能特征差异很大。下表总结了关键区别：

| 操作 | 链表 | 静态数组 |
| --- | --- | --- |
| 随机访问 | O(n) | O(1) |
| 头部插入/删除 | O(1) | O(n) |
| 中间插入/删除 | O(n) | O(n) |
| 最大容量 | 动态，无固定限制 | 分配时固定 |
| 内存开销 | 指针占用额外空间 | 无额外开销 |

当需要频繁插入/删除操作，且事先不知道集合大小时，更适合使用链表。当核心需求是元素的随机访问时，数组更有优势。

**例题:** 解释为什么实现动态队列时，链表比静态数组更合适。

1. 队列需要两个核心操作：队尾添加、队头删除
2. 对于静态数组，删除队头元素需要移动所有元素，时间复杂度为O(n)，且数组可能会用完空间
3. 带头尾指针的链表可以在O(1)时间完成队尾添加和队头删除，并且可以按需动态增长
4. 因此，链表对于动态队列是更高效的选择

## 操作的时间复杂度

CIE 9618经常要求你写出并解释常用链表操作的时间复杂度。时间复杂度描述了操作时间随链表节点数`n`的变化关系。

- 遍历 / 查找：最坏情况 O(n)
- 头部插入 / 删除：总是 O(1)
- 尾部插入 / 删除：带尾指针为O(1)，不带尾指针为O(n)
- 中间插入 / 删除：最坏情况 O(n)

**例题:** 无序单向链表中查找一个值的最坏时间复杂度是多少？解释你的答案。

1. 最坏情况下，目标值不存在于链表中，或者存储在最后一个节点
2. 要找到目标，你必须从头节点开始，遍历链表中的每个节点，直到遇到空的尾指针
3. 访问的节点数等于链表中总元素数`n`
4. 因此，最坏时间复杂度是 $O(n)$

> **考试提示:** 一定要说明复杂度是最坏情况还是平均情况，并解释你的推理过程才能拿到满分。

## 常见错误

- **错误做法:** 在设置新节点的next指针之前，先更新原有节点的next指针
  - 原因: 这会丢失链表剩余部分的引用，破坏整个数据结构
  - 正确做法: 一定要先设置新节点的next指针，再更新原有节点的next指针
- **错误做法:** 插入或删除第一个节点时，忘记更新头指针
  - 原因: 头指针是访问链表的唯一入口，因此修改第一个节点时必须更新它
  - 正确做法: 一定要先检查操作是否影响头节点，必要时更新头指针
- **错误做法:** 认为链表插入操作总是O(1)
  - 原因: 只有当你已经获得插入位置的指针时，插入才是O(1)。对于大多数位置，找到插入位置需要O(n)时间
  - 正确做法: 说明只有头部插入（或带尾指针的尾部插入）是O(1)，任意位置插入是O(n)
- **错误做法:** 删除节点后，让前驱节点的next指针仍指向被删除节点
  - 原因: 这会产生悬挂指针，被删除节点仍然可访问，破坏链表结构
  - 正确做法: 删除节点前，一定要先将前驱节点的next指针更新为指向被删除节点的后继节点
- **错误做法:** 假设链表节点存储在连续内存中
  - 原因: 这会导致错误地认为链表和数组一样支持随机访问
  - 正确做法: 记住节点可以存储在内存的任意位置，只能通过指针从头开始遍历访问节点

## 速查表

| 属性 | 单向链表 |
| --- | --- |
| 核心结构 | 节点 = 数据 + next指针 |
| 入口点 | 头指针指向第一个节点 |
| 遍历方向 | 仅向前 |
| 随机访问 | 不支持，O(n) |
| 头部插入 | O(1) |
| 头部删除 | O(1) |
| 中间插入/删除 | O(n) |
| 查找值 | O(n) |
| 大小 | 动态，无固定限制 |
| 核心优势 | 插入删除快，大小动态可变 |
| 核心劣势 | 指针占用额外内存，不支持随机访问 |

## 下一步

链表是基础的动态数据结构，是栈、队列、图、哈希表等更复杂数据结构的基础，所有这些内容都在CIE 9618的考察范围内。掌握链表的指针操作也能为你后续单元学习树和图遍历等更高级的主题做好准备。考试中经常会出现要求你比较链表和数组等其他动态结构，以及编写插入删除操作伪代码的题目。

- [栈](https://www.owlsprep.com/zh/study/cie-9618-u10-stacks/)
- [队列](https://www.owlsprep.com/zh/study/cie-9618-u10-queues/)
- [树](https://www.owlsprep.com/zh/study/cie-9618-u10-trees/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u10-linked-lists/