题目重点：把已知位置插删与先查找位置分开算复杂度，说明连续内存、指针开销和动态扩容。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 比较普通动态数组与单/双链表；数组元素等长/连续存储，链表节点可分散分配。不同语言的 Python list/Java ArrayList/C++ vector 细节另定。
解题路线
- 数组可按下标 O(1) 随机访问、顺序扫描有较好 cache locality；动态数组尾部 append 均摊 O(1)，扩容时一次 O(N) 搬移。
- 数组中间插入/删除需搬移后续元素 O(N)；链表已持有目标节点/前驱时改指针可 O(1)，但寻找第 i 个节点或按值查找 O(N)。不能把‘链表删除 O(1)’误说成按值删除总 O(1)。
- 链表节点有 next/prev 指针与分配器开销，随机访问差、CPU cache miss 多；大量小节点会带来内存碎片和 GC/allocator 压力。
- 选结构按操作比例与约束：按索引读/批遍历偏数组；频繁在已知节点附近增删、需稳定节点地址才可能偏链表。若要同时按 key 快速定位，可加 hash map，这已是复合结构。
手动走一遍
10 万元素按索引取第 5 万项：数组直接地址计算，链表要走约 5 万步。若已握住链表节点指针，在它后面插入只改少量指针；数组同位置要搬移约 5 万元素。
规模与取舍
数组索引 O(1)、中间插删 O(N)、尾 append 均摊 O(1)；链表按索引/值查找 O(N)，已知节点及前驱的插删 O(1)。数组 O(N) 连续元素空间，链表 O(N) 节点加指针开销。
易错点与追问
容易失分的边界
- 只列 Big-O 不谈缓存局部性。
- 把链表按值删除写 O(1)，漏查找成本。
- 把动态数组 append 写严格最坏 O(1)。
- 忘记单链表删除当前节点常需前驱。
- 忽略节点地址稳定性与内存开销。
继续深挖
- 需要 O(1) get 与 O(1) 删除已知 key 怎样组合？
- 为什么 vector 遍历通常比链表快？
- 数组扩容怎样证明均摊 O(1)？
- 并发插删哪种更容易保证一致性？
