Appearance
第3章 list 容器详解
list 是 STL 中的双向链表容器，底层由双向循环链表实现，支持在任意位置高效插入、删除元素，但不支持随机访问，是频繁进行中间操作的最优选择。
🎯 本章学习目标
学完本章，你将能够：
- 理解 list 的双向链表底层结构
- 熟练使用 list 的增删改查等基本操作
- 掌握 list 的迭代器特性（双向迭代器、稳定性）
- 理解 list 为什么不支持随机访问
- 掌握 list 独有的操作（sort、merge、reverse 等）
- 区分 list 与 vector、deque 的核心区别
- 理解迭代器失效的情况（list 与 vector 的区别）
- 根据场景选择合适的序列式容器
🗺️ 本章知识图谱
list 双向链表
├── 核心特性
│ ├── 双向循环链表
│ ├── 任意位置插入删除 O(1)
│ ├── 不支持随机访问
│ └── 迭代器稳定
├── 基本用法
│ ├── 定义与头文件
│ ├── 头尾操作（push/pop front/back）
│ ├── 中间插入删除（insert/erase）
│ ├── 访问头尾（front/back）
│ └── 遍历（迭代器/范围for）
├── 专属操作
│ ├── sort（链表排序）
│ ├── merge（合并有序链表）
│ ├── reverse（反转）
│ ├── remove（按值删除）
│ └── unique（去重）
├── 底层原理
│ ├── 节点结构（prev + data + next）
│ ├── 双向循环
│ └── 迭代器实现
├── 与其他容器对比
│ ├── vs vector
│ └── vs deque
├── 注意事项
│ ├── 不支持 [] 随机访问
│ ├── 迭代器只能 ++ --
│ ├── 空间开销大
│ └── 缓存不友好
└── 适用场景与选型一、list 核心特性
🍎 生活比喻：list 就像一串珍珠项链——每颗珍珠（节点）通过线（指针）连起来，每颗珍珠都知道前一颗和后一颗在哪。你可以在任意两颗珍珠之间插入新珍珠（中间插入 O(1)），只需要把线重新接一下就行。但你不能直接跳到第 10 颗珍珠（不支持随机访问），必须从头一颗一颗数过去。
- 双向链表结构：每个节点保存前驱（prev）和后继（next）指针，支持双向遍历；
- 高效插入/删除：在任意位置插入、删除元素效率均为 O(1)（只要有迭代器指向该位置）；
- 不支持随机访问：不能使用
[]或at()访问元素，只能通过迭代器逐个遍历； - 迭代器稳定性：插入、删除元素不会导致原有迭代器失效（仅被删除节点的迭代器失效）；
- 自带头尾操作：支持
push_front、pop_front、push_back、pop_back等高效头尾操作。
🔥 高频考点：list 的任意位置插入删除 O(1)、不支持随机访问、迭代器稳定，这些是选择题的常考点。
二、list 基础用法
使用 list 需包含 <list> 头文件。
cpp
#include <iostream>
#include <list> // list 头文件
using namespace std;
int main() {
// 1. 定义 list（多种方式）
list<int> lst1; // 空 list
list<int> lst2(5, 0); // 5 个元素，都初始化为 0
list<int> lst3 = {1, 2, 3, 4, 5}; // 初始化列表（C++11）
// 2. 头尾插入（都是 O(1)）
lst1.push_back(10); // 尾插
lst1.push_back(20);
lst1.push_front(5); // 头插
lst1.push_front(1);
// 此时 lst1：1 -> 5 -> 10 -> 20
// 3. 遍历链表（只能用迭代器或范围 for，不能用 []）
cout << "遍历结果：";
for (int num : lst1) {
cout << num << " "; // 输出：1 5 10 20
}
cout << endl;
// 4. 访问头尾元素
cout << "头部元素：" << lst1.front() << endl; // 输出：1
cout << "尾部元素：" << lst1.back() << endl; // 输出：20
// 5. 指定位置插入（需要先找到迭代器位置，O(1) 插入）
auto it = lst1.begin();
it++; // 指向第二个元素（5）
lst1.insert(it, 8); // 在 5 前面插入 8
// 此时 lst1：1 -> 8 -> 5 -> 10 -> 20
// 6. 删除元素
lst1.pop_front(); // 删除头部，lst1：8 -> 5 -> 10 -> 20
lst1.pop_back(); // 删除尾部，lst1：8 -> 5 -> 10
lst1.erase(lst1.begin()); // 删除迭代器指向元素，lst1：5 -> 10
// 7. 常用操作
cout << "链表大小：" << lst1.size() << endl; // 输出：2
cout << "是否为空：" << (lst1.empty() ? "是" : "否") << endl;
lst1.clear(); // 清空链表
return 0;
}操作汇总表
| 操作 | 语法 | 说明 | 时间复杂度 |
|---|---|---|---|
| 头插 | push_front(元素) | 在头部插入元素 | O(1) |
| 尾插 | push_back(元素) | 在尾部插入元素 | O(1) |
| 头删 | pop_front() | 删除头部元素 | O(1) |
| 尾删 | pop_back() | 删除尾部元素 | O(1) |
| 指定位置插入 | insert(迭代器, 元素) | 在迭代器位置插入元素 | O(1) |
| 指定位置删除 | erase(迭代器) | 删除迭代器指向的元素 | O(1) |
| 访问头部 | front() | 返回头部元素引用 | O(1) |
| 访问尾部 | back() | 返回尾部元素引用 | O(1) |
| 清空 | clear() | 删除所有元素 | O(n) |
| 判空 | empty() | 是否为空 | O(1) |
| 获取大小 | size() | 返回元素个数 | O(1) |
💡 小技巧：list 的 insert 和 erase 都是 O(1)，前提是你已经有了指向该位置的迭代器。如果需要先查找位置，查找本身是 O(n) 的。
三、list 的专属操作
因为 list 是链表结构，它有一些独有的成员函数（算法库中的同名函数对 list 效率低，所以 list 自己实现了）：
1. sort（排序）
cpp
list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6};
lst.sort(); // 升序排序
// 结果：1 1 2 3 4 5 6 9⚠️ 易错点：list 不能用 sort(lst.begin(), lst.end())（算法库的 sort），因为算法库的 sort 需要随机访问迭代器，而 list 只有双向迭代器。所以 list 自己提供了 sort 成员函数。
2. reverse（反转）
cpp
list<int> lst = {1, 2, 3, 4, 5};
lst.reverse(); // 反转链表
// 结果：5 4 3 2 13. remove（按值删除）
cpp
list<int> lst = {1, 2, 3, 2, 4, 2, 5};
lst.remove(2); // 删除所有值为 2 的元素
// 结果：1 3 4 54. unique（去重）
cpp
list<int> lst = {1, 1, 2, 2, 3, 3, 3};
lst.unique(); // 删除相邻的重复元素（只保留一个）
// 结果：1 2 3⚠️ 易错点：unique 只能删除相邻的重复元素。如果要完全去重，需要先 sort 再 unique。
5. merge（合并有序链表）
cpp
list<int> lst1 = {1, 3, 5};
list<int> lst2 = {2, 4, 6};
lst1.merge(lst2); // 合并两个有序链表，合并后 lst2 为空
// lst1 结果：1 2 3 4 5 6
// lst2 结果：空🔥 高频考点：list 有自己的 sort、reverse、merge 等成员函数，不能用算法库的版本，这是选择题和判断题的常考点。
四、底层原理（进阶）
1. 节点结构
list 的每个节点包含三部分：
struct Node {
T data; // 数据
Node* prev; // 前驱指针
Node* next; // 后继指针
};2. 双向循环链表
list 通常实现为双向循环链表，即：
- 头节点的 prev 指向尾节点
- 尾节点的 next 指向头节点
- 这样头尾操作都很方便
3. 迭代器
list 的迭代器是双向迭代器，只支持 ++ 和 -- 操作，不支持 +n、-n（那是随机访问迭代器才有的）。
cpp
list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
it++; // ✅ 正确，指向下一个
it--; // ✅ 正确，指向上一个
// it += 2; // ❌ 错误！list 迭代器不支持跳跃五、迭代器稳定性
这是 list 的一个重要特性，也是和 vector 的核心区别之一。
vector 的迭代器失效
vector 在插入元素时，如果发生扩容，所有迭代器都会失效。即使不扩容，插入点之后的迭代器也会失效。
list 的迭代器稳定
list 在插入、删除元素时，只有被删除的那个节点的迭代器会失效，其他所有迭代器都仍然有效。
🍎 生活比喻：就像项链上的珍珠——摘掉一颗珍珠，其他珍珠之间的连接不变，你仍然可以从任意一颗珍珠开始遍历。而 vector 像公交车——如果中间加了座位，后面的座位都往后挪了，你之前记的座位号就不对了。
🔥 高频考点：list 迭代器的稳定性（插入删除不影响其他迭代器）是选择题和判断题的常考点。
六、list 与其他容器对比
| 特性 | vector | deque | list |
|---|---|---|---|
| 内存结构 | 一整块连续 | 分段连续 | 不连续（链表） |
| 随机访问 | ✅ O(1) 最快 | ✅ O(1) 稍慢 | ❌ O(n) |
| 尾插尾删 | ✅ O(1) 均摊 | ✅ O(1) | ✅ O(1) |
| 头插头删 | ❌ O(n) | ✅ O(1) | ✅ O(1) |
| 中间插入删除 | ❌ O(n) | ❌ O(n) | ✅ O(1) |
| 迭代器类型 | 随机访问 | 随机访问 | 双向 |
| 迭代器稳定性 | 差（扩容全失效） | 一般 | 好（仅删除节点失效） |
| 空间开销 | 小 | 中 | 大（指针开销） |
| 缓存友好性 | 最好 | 一般 | 最差 |
七、常见误区与注意事项
⚠️ 易错点 1：用 [] 访问元素。list 不支持 [] 和 at()，不能随机访问。只能用迭代器遍历或用 front/back 访问头尾。
⚠️ 易错点 2：迭代器可以 +n。list 的迭代器是双向迭代器，只支持 ++ 和 --，不支持 +n、-n、+= 等跳跃操作。要移动 n 步，只能循环 n 次 ++。
⚠️ 易错点 3：用算法库的 sort 排序 list。算法库的 sort 需要随机访问迭代器，list 不满足。list 有自己的 sort 成员函数。
⚠️ 易错点 4：list 的 size() 是 O(1) 还是 O(n)。在 C++11 及以后，list 的 size() 是 O(1) 的（有一个计数器成员）。但在一些老版本编译器中可能是 O(n)，需要遍历计数。
⚠️ 易错点 5：list 空间效率高。实际上 list 的空间效率很低，因为每个节点都要存两个指针（prev 和 next），对于 int 这种小类型，指针的开销甚至比数据本身还大。
⚠️ 易错点 6：list 插入删除一定比 vector 快。不一定！list 插入虽然是 O(1)，但找到插入位置需要 O(n) 遍历，而且链表节点的分配释放也有开销。对于小数据量，vector 可能更快（因为缓存友好）。
八、适用场景总结
- 频繁在任意位置插入/删除：这是 list 最大的优势，只要有迭代器，插入删除都是 O(1)；
- 需要迭代器稳定：如果插入删除后其他迭代器必须保持有效，list 是最佳选择；
- 频繁头尾操作：list 的头尾操作也是 O(1)，和 deque 一样；
- 大数据量 + 频繁中间操作：数据量很大且经常在中间增删时，list 的优势才明显。
不适合的场景：
- 需要随机访问 → 用 vector 或 deque
- 数据量小、操作简单 → 用 vector（缓存友好，更快）
- 空间敏感 → 用 vector（list 指针开销大）
九、🔖 本章小结
list 是一种双向链表容器，最大的优势是任意位置插入删除 O(1) 和迭代器稳定，但代价是不支持随机访问、空间开销大、缓存不友好。它和 vector 正好互补——vector 擅长随机访问和尾插，list 擅长中间插入删除。在实际使用中，需要根据具体场景选择最合适的容器。
十、📝 实战练习
练习题 1（选择题）
题目： list 的底层数据结构是？
A. 连续内存的动态数组 B. 双向链表 C. 红黑树 D. 哈希表
🔑 点击查看答案与解析
答案： B
**解析：**list 底层是双向链表，每个节点有前驱和后继指针。A 是 vector 的底层结构，C 是 set/map 的底层结构，D 是 unordered_set/unordered_map 的底层结构。
练习题 2（判断题）
题目： list 支持使用 [] 进行随机访问（ ）
🔑 点击查看答案与解析
答案： 错误
**解析：**list 是双向链表，不支持随机访问，没有 [] 和 at() 操作符。只能通过迭代器逐个遍历，或用 front()/back() 访问头尾元素。
练习题 3（选择题）
题目： 在 list 中，已知迭代器指向某个位置，在该位置插入一个元素的时间复杂度是？
A. O(1) B. O(log n) C. O(n) D. O(n^2)
🔑 点击查看答案与解析
答案： A
**解析：**list 是双向链表，只要有了指向插入位置的迭代器，插入操作只需要修改相邻节点的指针，时间复杂度是 O(1)。这是 list 最大的优势。
注意：如果需要先查找插入位置，查找本身是 O(n) 的。
练习题 4（选择题）
题目： 以下关于 list 迭代器的说法，正确的是？
A. list 的迭代器是随机访问迭代器 B. list 插入元素后，所有迭代器都会失效 C. list 删除元素后，只有被删除节点的迭代器失效 D. list 的迭代器支持 += n 操作
🔑 点击查看答案与解析
答案： C
解析：
- A 错误：list 的迭代器是双向迭代器，不是随机访问迭代器
- B 错误：list 插入元素不会导致任何迭代器失效
- C 正确：list 删除元素只有被删除节点的迭代器失效，其他都有效
- D 错误：只有随机访问迭代器才支持
+= n，list 只支持++和--
练习题 5（程序阅读题）
题目： 阅读以下代码，写出输出结果：
cpp
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> lst = {1, 2, 3, 4, 5};
lst.push_front(0);
lst.push_back(6);
lst.pop_front();
lst.pop_back();
auto it = lst.begin();
it++;
lst.insert(it, 10);
for (int x : lst) {
cout << x << " ";
}
cout << endl;
return 0;
}🔑 点击查看答案与解析
答案： 1 10 2 3 4 5
解析：
- 初始：1 2 3 4 5
- push_front(0) → 0 1 2 3 4 5
- push_back(6) → 0 1 2 3 4 5 6
- pop_front() → 1 2 3 4 5 6
- pop_back() → 1 2 3 4 5
- it = begin() 指向 1，it++ 后指向 2
- insert(it, 10) 在 it 前面（即 2 前面）插入 10 → 1 10 2 3 4 5
最终输出：1 10 2 3 4 5
练习题 6（选择题）
题目： 以下哪个操作，list 有自己的成员函数版本，而不能直接用 algorithm 库的版本？
A. find B. sort C. count D. for_each
🔑 点击查看答案与解析
答案： B
**解析：**algorithm 库的 sort 需要随机访问迭代器（用了快排等需要随机访问的算法），而 list 只有双向迭代器，所以不能用 sort(lst.begin(), lst.end())。list 自己提供了 sort 成员函数（用归并排序实现）。
find、count、for_each 只需要单向或双向迭代器，list 可以直接使用 algorithm 库的版本。
练习题 7（编程题）
题目： 输入 n 个整数，存入 list 中，然后删除所有值为 x 的元素，最后输出剩余元素。
**输入格式：**第一行两个整数 n 和 x，第二行 n 个整数 **输出格式：**一行，删除后的元素，用空格隔开
样例输入：
7 2
1 2 3 2 4 2 5样例输出：
1 3 4 5🔑 点击查看答案与解析
参考代码（方法一：用 list 的 remove 成员函数）：
cpp
#include <iostream>
#include <list>
using namespace std;
int main() {
int n, x;
cin >> n >> x;
list<int> lst;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
lst.push_back(num);
}
lst.remove(x); // 删除所有值为 x 的元素
bool first = true;
for (int num : lst) {
if (!first) cout << " ";
cout << num;
first = false;
}
cout << endl;
return 0;
}参考代码（方法二：手动遍历删除，演示 erase 的用法）：
cpp
#include <iostream>
#include <list>
using namespace std;
int main() {
int n, x;
cin >> n >> x;
list<int> lst;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
lst.push_back(num);
}
// 注意：erase 会使当前迭代器失效，所以要接收返回值
for (auto it = lst.begin(); it != lst.end(); ) {
if (*it == x) {
it = lst.erase(it); // erase 返回下一个元素的迭代器
} else {
it++;
}
}
bool first = true;
for (int num : lst) {
if (!first) cout << " ";
cout << num;
first = false;
}
cout << endl;
return 0;
}解析：
- 方法一：直接用 list 的 remove 成员函数，最简单，一行搞定。
- 方法二：手动遍历删除，注意 erase 之后迭代器会失效，要用 erase 的返回值（指向下一个元素）。这是 list 遍历删除的标准写法，vector 也是类似的。
方法一是 list 专属的便捷操作，方法二更通用，也更考验对迭代器的理解。
十一、📊 考点总结表
| 知识点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| 底层是双向链表 | ⭐⭐⭐⭐⭐ | 选择题、判断题 | 与 vector 混淆 |
| 不支持随机访问 | ⭐⭐⭐⭐⭐ | 选择题、判断题 | 以为可以用 [] |
| 任意位置插入删除 O(1) | ⭐⭐⭐⭐⭐ | 选择题 | 忘了前提是有迭代器 |
| 迭代器稳定性 | ⭐⭐⭐⭐ | 选择题、判断题 | 与 vector 混淆 |
| 双向迭代器（只有 ++ --） | ⭐⭐⭐ | 选择题 | 以为支持 += n |
| 有自己的 sort 成员函数 | ⭐⭐⭐⭐ | 选择题、判断题 | 用 algorithm 的 sort |
| 空间开销大（指针） | ⭐⭐⭐ | 选择题 | 以为 list 更省空间 |
| remove 按值删除 | ⭐⭐⭐ | 选择题、编程题 | 不知道有这个函数 |
| 与 vector/deque 对比 | ⭐⭐⭐⭐⭐ | 选择题、简答题 | 三者区别记不清 |
⭐ 必背速记卡
┌──────────────────────────────────────┐
│ list 必背速记卡 │
├──────────────────────────────────────┤
│ 1. 底层是双向循环链表 │
│ 2. 任意位置插入删除都是 O(1) │
│ 3. 不支持随机访问，不能用 [] │
│ 4. 迭代器是双向的，只能 ++ -- │
│ 5. 插入不失效迭代器，删除仅失效当前 │
│ 6. 有自己的 sort、reverse、merge │
│ 7. remove 按值删，unique 去相邻重复 │
│ 8. 空间开销大（每个节点两个指针） │
│ 9. 缓存不友好，小数据可能比 vector 慢│
│ 10. 适合：频繁中间插入删除的场景 │
└──────────────────────────────────────┘