每个元素各住各的，靠指针互相连接——任意位置插入删除都是 O(1)，但放弃了下标随机访问的能力。
list 是一个双向链表。链表不像数组那样所有元素挤在一块连续的内存里，而是每个元素各住各的，彼此用"指针"串起来。这带来的好处是：在任意位置插入或删除元素都是 O(1)，快到飞起。代价是：不能用下标直接跳到第 n 个元素，只能顺着链条一个一个找。使用前需引入 <list> 头文件。
list 不支持随机访问，不能像 vector 那样用 l[0] 或 l.at(0) 访问元素，必须通过迭代器遍历。list 支持 O(1) 的头部插入/删除（push_front / pop_front），这是 vector 不具备的。
| 1 | #include <iostream> |
| 2 | #include <list> // list 位于此头文件中 |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | list<int> l1; // 空链表 |
| 8 | list<int> l2(5); // 5 个元素，全部初始化为 0 |
| 9 | list<int> l3(5, 7); // 5 个元素，全部初始化为 7 |
| 10 | list<int> l4 = {1, 2, 3, 4, 5}; // 用花括号初始化 |
| 11 | list<int> l5(l4); // 拷贝构造 |
| 12 | return 0; |
| 13 | } |
🔍 元素访问
| 1 | list<int> l = {10, 20, 30}; |
| 2 | int first = l.front(); // 10——第一个元素 |
| 3 | int last = l.back(); // 30——最后一个元素 |
| 4 | // ❌ l[0] —— 编译错误！list 不支持下标访问 |
✏️ 增删修改
| 1 | list<int> l = {2, 3, 4}; |
| 2 | l.push_front(1); // {1, 2, 3, 4}——头部插入 |
| 3 | l.push_back(5); // {1, 2, 3, 4, 5}——尾部插入 |
| 4 | l.pop_front(); // {2, 3, 4, 5}——头部删除 |
| 5 | l.pop_back(); // {2, 3, 4}——尾部删除 |
| 6 | |
| 7 | auto it = l.begin(); |
| 8 | ++it; // it 指向第二个元素（3） |
| 9 | l.insert(it, 99); // 在 it 前面插入 99：{2, 99, 3, 4} |
| 10 | l.erase(it); // 删除 it 指向的元素：{2, 99, 4} |
| 11 | l1.swap(l2); // 交换两个链表的内容 |
🔄 迭代器遍历
| 1 | list<int> l = {1, 2, 3}; |
| 2 | // 用迭代器遍历（list 的迭代器只支持 ++ 和 --，不支持 it + 3 这种跳转） |
| 3 | for (auto it = l.begin(); it != l.end(); ++it) |
| 4 | { |
| 5 | cout << *it << " "; // 输出：1 2 3 |
| 6 | } |
| 7 | |
| 8 | // 范围 for 更简洁 |
| 9 | for (int x : l) { |
| 10 | cout << x << " "; // 输出：1 2 3 |
| 11 | } |
| 1 | #include <iostream> |
| 2 | #include <list> |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | list<int> l; |
| 8 | |
| 9 | // 在头部和尾部随意插入 |
| 10 | l.push_back(2); |
| 11 | l.push_front(1); |
| 12 | l.push_back(3); |
| 13 | // l = {1, 2, 3} |
| 14 | |
| 15 | cout << "链表内容: "; |
| 16 | for (int x : l) { |
| 17 | cout << x << " "; // 输出：1 2 3 |
| 18 | } |
| 19 | cout << endl; |
| 20 | |
| 21 | // 删除中间的偶数 |
| 22 | for (auto it = l.begin(); it != l.end(); ) { |
| 23 | if (*it % 2 == 0) |
| 24 | it = l.erase(it); // list 的 erase 也返回下一个有效迭代器 |
| 25 | else |
| 26 | ++it; |
| 27 | } |
| 28 | // l = {1, 3} |
| 29 | |
| 30 | cout << "首元素: " << l.front() << endl; // 输出：1 |
| 31 | cout << "尾元素: " << l.back() << endl; // 输出：3 |
| 32 | cout << "大小: " << l.size() << endl; // 输出：2 |
| 33 | |
| 34 | return 0; |
| 35 | } |
把本节出现过的方法按用途归类汇总，写代码时可以直接当参考卡用。
| 方法 | 分类 | 作用 |
|---|---|---|
| l.size() / l.empty() | 容量 | 元素个数 / 判断是否为空 |
| l.clear() | 容量 | 清空所有元素 |
| l.front() / l.back() | 访问 | 第一个 / 最后一个元素 |
| l.push_front(x) / l.pop_front() | 修改 | 头部插入 / 删除，O(1)（vector 没有） |
| l.push_back(x) / l.pop_back() | 修改 | 尾部插入 / 删除，O(1) |
| l.insert(it, x) | 修改 | 在 it 前插入元素，O(1) |
| l.erase(it) | 修改 | 删除 it 指向的元素，返回下一个有效迭代器 |
| l1.swap(l2) | 修改 | 交换两个链表的全部内容 |
| l.begin() / l.end() | 遍历 | 正向迭代器范围（只支持 ++ / --，不支持跳转） |
vector；需要频繁在头部或中间插入删除、不在乎随机访问 → 用 list。两者都需要的场景，下一节的 deque 是折中方案。