目录
🧱 一、什么是 std::list？
📘 定义：
std::list 是一个 双向链表容器，每个元素都有两个指针：指向前一个元素和后一个元素。
特点：
随时插、随时删，哪儿都能动，代价就是不支持随机访问。
它和 vector 的最大区别是：
vector是 动态数组（可随机访问，但插入/删除中间元素慢）list是 双向链表（不能随机访问，但插入/删除快）
⚙️ 二、底层结构图解
nullptr ← [10] ⇄ [20] ⇄ [30] → nullptr
每个节点：
包含一个值（value）
一个指向前驱节点的指针
一个指向后继节点的指针
🧪 三、list 的常见操作
🔧 引入头文件：
#include <list>
🔨 定义列表
std::list<int> l;
std::list<std::string> names = {"Tom", "Alice", "Bob"};
➕ 插入操作
l.push_back(10); // 末尾插入
l.push_front(5); // 头部插入
❌ 删除操作
l.pop_back(); // 删除末尾
l.pop_front(); // 删除头部
l.remove(10); // 删除所有值为10的元素
🔍 插入 / 删除 任意位置（使用迭代器）
auto it = l.begin();
++it; // 指向第二个元素
l.insert(it, 99); // 在第二个元素前插入 99
l.erase(it); // 删除第二个元素
🔁 遍历 list
for (auto x : l) {
std::cout << x << " ";
}
📦 四、完整示例代码
#include <iostream>
#include <list>
int main() {
std::list<int> l = {10, 20, 30};
l.push_front(5);
l.push_back(40);
auto it = l.begin();
std::advance(it, 2); // 迭代器移动到第三个元素
l.insert(it, 99); // 插入 99
l.remove(20); // 删除值为 20 的元素
for (auto x : l)
std::cout << x << " ";
return 0;
}
输出：
5 10 99 30 40
📌 五、特点总结对比
| 特性 | list |
vector |
|---|---|---|
| 内部结构 | 双向链表 | 动态数组 |
| 随机访问 | ❌ 不支持 | ✅ 支持（v[i]） |
| 中间插入/删除 | ✅ 快（O(1)） | ❌ 慢（O(n)） |
| 空间使用 | 多（节点有指针） | 紧凑 |
| 遍历效率 | 较慢 | 较快（连续内存） |
🛠 六、特殊函数
| 函数 | 用法 |
|---|---|
sort() |
对链表排序 |
merge() |
合并两个已排序的链表 |
reverse() |
反转链表顺序 |
unique() |
去除连续重复元素 |
splice() |
将另一个 list 插入本 list 的任意位置 |
📚 七、list 迭代器操作
list.begin()：指向第一个元素list.end()：指向“尾后位置”不能使用
it + 1，但可以用：
std::advance(it, n); // 将 it 向后移动 n 步
⚠️ 八、使用场景 vs vector
适合使用 list 的场景：
需要频繁插入或删除元素（特别是中间位置）
数据规模大，避免频繁内存移动
不需要随机访问
不适合 list 的场景：
经常访问第 i 个元素（比如排序后查找排名第 n）
遍历速度要求高，空间利用率要求高