第 3 章的数组和链表是「原材料」，本章把它们包装成两个正经的 ADT——向量（Vector） 和 列表（List）——并引出一个贯穿全书的问题：同一个功能，两种实现，到底选哪个？ 🤔
📦 向量 ADT：按下标说话
向量 = 「可以按下标访问的序列」，核心接口：
at(i)：返回第 i 个元素（越界抛异常，比裸下标安全）；insert(i, e)：在第 i 位插入 e；erase(i)：删除第 i 位。
数组实现自然流畅，但 insert/erase 要搬动后面所有元素，O(n)。书里给出一个工程级优化：容量不够时，申请 2 倍大的新数组整体搬家（ doubling strategy）——均摊下来，每次 push_back 居然是 O(1)！这个「均摊分析」（amortization）思想值得单独记住 💡。
🚶 列表 ADT：迭代器登场
链表实现的列表无法高效按下标访问，怎么办？换一种「访问哲学」——迭代器（iterator）：
for (Iterator p = l.begin(); p != l.end(); ++p)
cout << *p; // p 像箭头，*p 是箭头指着的元素
迭代器是「位置」的抽象：begin() 指向第一个元素，end() 指向最后一个元素的后面（左闭右开区间，STL 的经典约定）。有了迭代器，插入删除都在「箭头处」O(1) 完成——随机访问弱了，但位置操作起飞了 ✈️。
⚔️ 同一个 ADT，两种实现
书里给「序列（Sequence）」同时提供数组实现和链表实现，然后把选择变成一张对照表：
| 操作 | 数组实现 | 链表实现 |
|---|---|---|
| at(i) 随机访问 | O(1) 🏆 | O(n) |
| 头部插/删 | O(n) | O(1) 🏆 |
| 尾部插/删 | O(1) 均摊 🏆 | O(1) 🏆 |
| 迭代器处插/删 | O(n) | O(1) 🏆 |
| 内存布局 | 连续（缓存友好） | 散落（指针开销） |
没有赢家，只有场景：读多写少、常按下标取 → 向量；疯狂插删、拿着迭代器走 → 列表。这就是 ADT 思维的实战价值——用户代码不变，换实现即可。
🫧 实战：冒泡排序
本章用 Bubble-Sort 串场：相邻元素两两比较，逆序就交换，每一轮把最大值「冒」到末尾。
- 双重循环 → O(n²)，注定只适合小数据；
- 但妙处在于：它只依赖「序列」的抽象接口——数组版、链表版代码几乎一样，这就是面向接口编程的现场示范 🎓。
🎯 本章通关清单
- [ ] 解释「均摊 O(1)」为什么敢说 O(1)
- [ ] 说出 begin/end 左闭右开约定的好处
- [ ] 面试题：给五个场景，现场选向量还是列表并说明理由
- [ ] 理解冒泡排序为什么和底层实现无关
线性世界到此毕业 🎓。下一章进入非线性世界——树，数据结构真正的大boss开始登场 🌳