数组（Array）
连续内存，逻辑下标与物理地址线性对应。支持 O(1) 随机读写；尾部摊还 O(1) 追加（动态数组扩容）；中间插入/删除需移动元素，O(n)。
面试常考：
- 原地操作：双指针、快慢指针、反转、去重。
- 前缀和 / 差分：区间查询与多次区间修改。
- 环形数组：下标取模模拟队列。
# 反转区间 [left, right]，1-indexed 示例
def reverse_between(head, left, right):
dummy = ListNode(0, head)
prev = dummy
for _ in range(left - 1):
prev = prev.next
cur = prev.next
for _ in range(right - left):
nxt = cur.next
cur.next = nxt.next
nxt.next = prev.next
prev.next = nxt
return dummy.next缓存友好：遍历顺序访问命中 CPU 缓存；链表节点分散，常数因子大。
单链表、双链表
单链表：val + next，省空间；无法 O(1) 删前驱节点（需 dummy 或记录 prev）。
双链表：prev + next，O(1) 删除已知节点（如 LRU 哈希+双向链）。
虚拟头结点 dummy 可统一「头插/删头」边界，减少分支。
复杂度对照
| 操作 | 数组 | 链表 | |---|---|---| | 按下标访问 | O(1) | O(n) | | 头插 | O(n) | O(1) | | 尾插 | O(1)* | O(n) / O(1)若维护 tail | | 按值查找 | O(n) | O(n) |
*动态数组尾部摊还 O(1)。
选型与真题方向
- 读多、下标访问、排序后双指针 → 数组。
- 频繁头插删、长度不定、合并链表 → 链表。
- 设计 LRU → 哈希表 + 双向链表。