一、上期回顾

掌握vector动态数组：连续内存、随机访问、自动扩容、size/capacity 区别、常用增删接口。今天学习STL list 双向循环链表，和 vector 做对标选型。

二、list 底层本质

list底层是双向循环链表

• 每一个节点：存数据 + 前驱指针 + 后继指针
• 内存不连续，不支持下标随机访问
• 任意位置插入、删除O(1)效率极高

三、list 与 vector 核心差异

表格

选型口诀：

• 频繁查询、随机访问 → 用 vector
• 频繁中间 / 头部插入删除、不常查找 → 用 list

四、list 常用构造方式

#include <iostream> #include <list> using namespace std; int main() { // 1. 空链表 list<int> l1; // 2. 5个默认0 list<int> l2(5); // 3. 5个值为8 list<int> l3(5, 8); // 4. 拷贝构造 list<int> l4(l3); // 5. 区间构造 list<int> l5(l4.begin(), l4.end()); return 0; }

五、list 常用赋值与遍历

赋值

list<int> l1 = {1,2,3,4}; list<int> l2; l2 = l1; l2.assign(3, 66); l2.assign(l1.begin(), l1.end());

遍历方式

注意：list 不支持下标[]访问只能用迭代器、范围 for：

list<int> l = {10,20,30}; // 1. 迭代器遍历 for(list<int>::iterator it = l.begin(); it != l.end(); ++it) { cout << *it << " "; } // 2. 范围for遍历 for(auto val : l) { cout << val << " "; }

六、list 核心常用接口

list<int> l; // 尾插、头插 l.push_back(10); l.push_front(5); // 尾删、头删 l.pop_back(); l.pop_front(); // 大小、判空、清空 l.size(); l.empty(); l.clear(); // 指定位置插入 l.insert(l.begin(), 99); // 删除 l.erase(l.begin()); // 移除指定元素 l.remove(10); // 反转链表 l.reverse(); // 排序 l.sort();

重点：

• remove(值)：直接删除所有等于该值的元素，vector 没有这个便捷接口
• sort()：list 自带排序，不用算法库 sort，因为不支持随机访问迭代器

七、list 迭代器失效特性

1. 插入元素：所有迭代器都不失效
2. 删除元素：仅被删除节点的迭代器失效，其他仍有效对比 vector：插入删除极易导致大量迭代器失效，list 更安全。

八、完整综合示例代码

#include <iostream> #include <list> using namespace std; int main() { list<int> l; // 头尾插入 l.push_back(1); l.push_back(3); l.push_front(0); l.push_back(5); cout << "遍历元素："; for(auto val : l) { cout << val << " "; } cout << endl; // 反转 l.reverse(); cout << "反转后："; for(auto val : l) cout << val << " "; cout << endl; // 排序 l.sort(); cout << "排序后："; for(auto val : l) cout << val << " "; return 0; }

运行结果：

遍历元素：0 1 3 5 反转后：5 3 1 0 排序后：0 1 3 5

九、今日核心总结

1. list 底层双向循环链表，内存不连续
2. 不支持下标随机访问，只能迭代器 / 范围 for 遍历
3. 中间、头部增删效率远高于 vector
4. 独有接口：remove、reverse、自带sort
5. 迭代器不易失效，适合频繁插入删除场景
6. 业务选型：查多用 vector，插删多用 list

十、课后练习

1. 创建 list 存入 5 个数字
2. 头插、尾插各加一个数
3. 调用 reverse 反转、sort 排序并打印