c++：双向链表容器（std::list）

目录

🧱 一、什么是 std::list？

⚙️ 二、底层结构图解 

🧪 三、list 的常见操作

📦 四、完整示例代码

📌 五、特点总结对比

🛠 六、特殊函数

📚 七、list 迭代器操作

⚠️ 八、使用场景 vs vector

---

🧱 一、什么是 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);        // 插入 99l.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）

• 遍历速度要求高，空间利用率要求高