list 是双向链表，头文件 <list>。任意位置插入/删除 O(1)，不支持随机访问。
一、核心特点
| 项目 | 说明 |
|---|
| 底层 | 双向链表 |
| 迭代器 | 双向（只能 ++/--） |
| 内存 | 节点独立堆分配 |
| 优势 | 中间插入/删除不移动元素，迭代器不失效（除被删节点） |
| 劣势 | 无下标访问，访问第 n 个元素 O(n) |
二、声明与初始化
list<int> L; // 空
list<int> L(5, 10); // 5个10
list<int> L{1,2,3}; // 初始化列表
list<int> L(beg, end); // 迭代器区间
list<int> L2(L1); // 拷贝
三、元素访问（仅两端 O(1)）
| 操作 | 说明 |
|---|
L.front() | 首元素 |
L.back() | 尾元素 |
四、插入操作
| 操作 | 示例 | 时间复杂度 |
|---|
| 头插 | L.push_front(10); | O(1) |
| 尾插 | L.push_back(20); | O(1) |
| 指定位置前插入 | L.insert(it, 30); | O(1) |
| 插入 n 个相同值 | L.insert(it, 3, 5); | O(k) |
| 头构造插入 | L.emplace_front(args...); | O(1) |
| 尾构造插入 | L.emplace_back(args...); | O(1) |
| 指定位置前构造 | L.emplace(it, args...); | O(1) |
emplace 与 push 的区别：emplace 直接传递构造函数参数原地构造元素，避免临时对象拷贝；push 需要先创建临时对象再拷贝/移动。对自定义类型更高效。
struct Point {
int x,y;
Point(int a,int b):x(a),y(b){}
};
list<Point> pts;
pts.emplace_back(1,2); // 直接构造，无需临时 Point(1,2)
pts.push_back(Point(3,4)); // 需要临时对象
五、删除操作
| 操作 | 时间复杂度 |
|---|
L.pop_front() | O(1) |
L.pop_back() | O(1) |
L.erase(it) | O(1) |
L.erase(beg,end) | O(k) |
L.remove(val) — 删除所有等于 val 的节点 | O(n) |
L.remove_if(pred) | O(n) |
L.clear() | O(n) |
六、大小相关
| 操作 | 时间复杂度 |
|---|
L.empty() | O(1) |
L.size() | O(1)（C++11起） |
L.resize(n) / L.resize(n,val) | O(min(n,size)) |
七、迭代器操作（均 O(1)）
| 操作 | 说明 |
|---|
begin()/end() | 正向 |
rbegin()/rend() | 反向 |
cbegin()/cend() | 常量正向 |
八、高级操作（list 特有）
| 操作 | 说明 | 时间复杂度 |
|---|
L.splice(pos, other) | 将 other 全部移到 pos 前 | O(1) |
L.splice(pos, other, it) | 将 other 的单个节点 it 移到 pos 前 | O(1) |
L.splice(pos, other, beg, end) | 将 other 的 [beg,end) 移到 pos 前 | O(1) |
L.sort() / L.sort(cmp) | 排序（需随机访问则用全局 sort） | O(n log n) |
L.merge(other) | 合并两个已排序链表，other 清空 | O(n+m) |
L.unique() | 移除连续重复元素（常先 sort） | O(n) |
L.reverse() | 反转链表 | O(n) |
L.assign(n,val) / L.assign(beg,end) | 替换内容 | O(n) |
L.swap(other) | 交换内容 | O(1) |
九、时间复杂度速查表
| 操作 | 复杂度 |
|---|
push_*, pop_*, insert, erase(单节点), emplace_* | O(1) |
size, empty, begin, end, front, back | O(1) |
splice（任意形式） | O(1) |
remove, remove_if, reverse, unique | O(n) |
sort | O(n log n) |
merge | O(n+m) |
clear, resize, assign | O(n) |
访问任意位置（如 advance(it,k)） | O(k) |