前面几节讨论了顺序表和链表的原理及选型。本节把这些结论放回真实的软件工程里：标准库到底封装了哪些细节？没有原生指针时怎么表达链式关系？一个看似简单的 LRU 缓存为什么还需要考虑并发问题？

学习目标

• 区分标准库的公开接口与具体实现细节；
• 理解静态链表中游标、自由表的作用和限制；
• 搞清楚 LRU 里哈希表和双向链表各自负责什么，以及基础版本为什么不支持并发。

5.1 标准库：先看接口，再看源码

标准库文档给出的是公开接口——也就是你可以依赖的行为、复杂度和失效规则。源码展示的是某个版本的具体实现，它解释了为什么这个版本做了这样的取舍，但不能推广到所有实现。

5.1.1 std::vector 与 std::list

std::vector 是连续存储的动态数组，按下标访问直接对应地址计算；std::list 是双向链表，插入删除已知节点时不需要搬移元素。它们都实现了容器接口，但连续空间、节点稳定性和修改成本的权衡完全不同。

以 GCC 的 libstdc++ 为例，vector 内部用 _M_start、_M_finish、_M_end_of_storage 三个指针分别标记已分配区间的起点、已构造元素的末尾和容量末尾。注意：这只是 libstdc++ 的一种实现方式，不是 C++ 标准强制的布局。

vector 的 push_back 在容量足够时只需在末尾构造元素，容量不足时才需要重新分配并搬移已有元素。在通常的 1.5 倍或 2 倍扩容策略下，多次尾部追加的均摊复杂度是 $O(1)$，但单次调用并不保证恒为 $O(1)$。

另外要注意一个常见误区："list 的插入删除是 $O(1)$" 这句话的前提是已经给出了有效节点或迭代器。如果输入只是下标或键，定位节点的遍历成本必须算进总成本里。

std::list 的节点布局同样不是标准规定的；不要把"带循环哨兵"当成所有实现的共同事实。工程选型时仍然要回到第 1.4 节的核心问题：访问者手里拿的是下标、键，还是稳定的节点句柄？

5.1.2 ArrayList 与 LinkedList

Java 的 ArrayList 用数组作缓冲区，LinkedList 同时实现了 List 和 Deque 接口。前者适合按位置读取和顺序遍历，后者在双端操作和已知节点附近的局部修改上更直接。

OpenJDK 的 ArrayList 扩容通常按 oldCapacity + (oldCapacity >> 1) 计算，也就是约 1.5 倍增长。但 JDK 文档只保证追加的均摊常数时间，增长倍率本身不是 Java API 的公开契约，不同版本可能不同。

还有一个容易被忽略的点：ArrayList 在结构性修改与并发访问交叠时并不安全，需要外部同步。这不是"数组"或"链表"的名称就能自动解决的问题。

5.2 静态链表与 Free List

静态链表把"节点存在哪里"和"下一个逻辑节点是谁"分开：节点槽位预先放在数组中，游标保存逻辑后继的数组下标。它适用于没有原生指针、容量上界可预先确定，或希望把节点分配控制在固定池中的场景。

下面是一段示意代码，展示了活动链表和空闲链表共存的结构：

constexpr int null_index = 0;

struct Slot {
    int value{};
    int next{null_index};
};

std::array<Slot, 101> slots{};  // 1..100 是可用槽位
int head = null_index;          // 活动链表的首槽位
int free_head = 1;              // 空闲链表的首槽位

cursor-list.cpp

初始化时，把 1 -> 2 -> ... -> 100 -> 0 串成自由表。分配节点时从 free_head 摘下一个槽位；删除节点时把该槽位重新接回自由表，而不是交给运行时逐个 new 或 free。

静态链表要维持几个基本约束：每个可用槽位要么在活动链表中，要么在自由表中，不能同时出现；head 和 free_head 都用 0 表示空链；沿任一链表的 next 遍历必须能终止，不能出现意外环。

已知前驱游标时，插入或删除只修改常数个 next 字段，是 $O(1)$；但按逻辑位序访问第 $i$ 个元素仍然需要沿游标走 $i-1$ 步，是 $O(i)$。数组下标是物理槽位，不等于逻辑位序。 比如逻辑序列是 slots[7] -> slots[2] -> slots[19]，第二个逻辑元素在 slots[2]，第三个在 slots[19]，你不能直接用 slots[i] 取第 $i$ 个逻辑元素。

可以先完成 Lab 01-T-05：静态链表选择题精练，再用上面的约束复核每个选项的前提。

5.3 LRU：组合结构与线程安全边界

第 1.4 节已经给出了 LRU 缓存的完整基础实现：哈希表把键映射到链表节点，双向链表维护"最近使用到最久未使用"的顺序。

这个组合结构有两个核心约束必须同时满足：

1. 每个缓存键至多对应一个链表节点，哈希表里的迭代器必须指向仍存在的节点；
2. 链表从表头到表尾严格表示最近使用到最久未使用的顺序，且每个缓存项恰好出现一次。

基础实现用来解释组合结构的工作原理，但不等同于并发缓存。如果两个线程同时执行"查表、移动节点、淘汰节点"这组动作，任一步的交错都可能破坏上面两条约束，或者让哈希表保留已经失效的迭代器。

针对不同场景，同步策略的取舍也不同：

需求	可考虑的策略	需要说明的代价
正确性优先、并发较低	用一个互斥锁保护整个复合操作	实现简单，但所有访问在同一临界区竞争
并发较高	分片缓存或分段锁	需要定义跨分片淘汰与容量统计语义
读取很多	重新设计读写路径和一致性规则	get 会更新使用顺序，因此并非天然只读

这里有一个容易踩的坑：严格 LRU 里的 get 不是只读操作。命中时会把节点提升到最近使用端，因此会修改链表顺序；如果没明确同步策略，不能因为接口名字叫"读取"就允许并发执行。

本节不提供并发 LRU 的代码或基准结果。选择同步策略之前，应该先想清楚：是否必须保持严格全局 LRU？容量是否允许分片近似？能接受的延迟和内存成本是多少？

参考来源

• GCC libstdc++：stl_vector.h，访问日期：2026-08-17。三指针示例仅对应该实现。
• C++ reference：std::vector 与 std::list，访问日期：2022026-08-17。
• OpenJDK：ArrayList.java，访问日期：2026-08-17。增长策略随实现版本变化。
• Java SE 21：ArrayList 与 LinkedList。

小结

• 标准库接口告诉你"可以依赖什么"，源码阅读告诉你"这个版本为什么这样取舍"；不要把二者混为一谈。
• 静态链表用游标链接逻辑顺序，自由表负责可复用槽位；数组本身不自动带来逻辑上的随机访问能力。
• LRU 通过"哈希表定位 + 双向链表调序"组合出两种能力；并发时必须把这两个结构视为一个需要共同保护的整体。

思考两个问题：为什么严格 LRU 的 get 不能天然当成只读操作处理？当静态链表的自由表为空时，插入操作应如何定义失败行为？