2.3.6 顺序表还是链表：比较必须带上操作场景

没有脱离工作负载的“最好结构”。顺序表的优势是按位访问 $O(1)$、内存紧凑、缓存局部性好；缺点是中间插删需移动元素，连续大块空间和容量规划可能成为限制。链表按位访问 $O(n)$，每结点有指针开销且缓存不友好；但已知操作位置的前驱时插删只需 $O(1)$，容量按结点增长。

注意“查到位置”和“修改链接”应分开计费。题目若说“在给定结点后插入”，单链表为 $O(1)$；若只说“在第 $i$ 位插入”，先定位通常是 $O(n)$。顺序表尾部插入在容量足够时为 $O(1)$，动态数组采用倍增时连续尾插通常也是均摊 $O(1)$。

空间上，顺序表可能有未用容量，链表每个元素多存一个或两个指针。若元素很小，指针比例很高；若元素很大，指针开销相对减小。工程上还要考虑遍历占比、数据规模是否可预测、是否需要稳定的结点地址。

场景判断：频繁按索引读取、很少中间插删，优先顺序表；频繁在已知结点附近插删、规模波动大，考虑链表；需要双向迭代，考虑双链表；需要轮转，考虑循环链表。若同时需要快速索引和快速任意插删，单一线性结构通常无法全部满足，可能需要额外索引或更复杂结构。

错解反馈：把链表插入一概写 $O(1)$ 是漏算定位；认为链表一定省空间，忽略指针域和分配器开销；只列渐近复杂度不考虑缓存，无法解释实际遍历中数组常更快。

迁移练习：实现文本编辑器光标附近频繁插删、但很少按编号随机读取，应选什么？答案可选双链表或分块结构，理由是光标已给出局部位置，插删无需整体搬移。独立验收：面对一个场景，至少从访问、插删、空间、局部性四项给出带条件结论。