如何选择顺序存储数据结构？¶
一、常见顺序存储¶
| 结构 | 随机访问 | 插入/删除 | 内存 |
|---|---|---|---|
| 数组 | O(1) | O(n) | 连续 |
| 链表 | O(n) | O(1)（已知位置） | 节点分散 |
| ArrayList | 同数组 | 尾部 O(1)，中间 O(n) | 连续 |
| LinkedList | 同链表 | O(1) | 指针开销 |
二、选择依据¶
1. 读多写少¶
用 ArrayList / 数组。随机访问快，缓存友好。
2. 频繁中间插入删除¶
用 LinkedList。但实际业务中 LinkedList 用得少，因为：
- 缓存不友好。
- 节点对象开销大。
- 即使知道位置，查找位置本身要 O(n)。
3. 频繁尾部追加¶
ArrayList 动态扩容就够。
4. 队列 / 栈¶
- 栈：
ArrayDeque比Stack好。 - 队列：
ArrayDeque或LinkedList。
三、实际经验¶
- 95% 场景用
ArrayList。 - LinkedList 几乎不用。
- 需要删除元素用迭代器或
removeIf，不要 for 循环里 remove。
四、对比 Vector¶
Vector 所有方法 synchronized，性能差。单线程用 ArrayList，多线程用 CopyOnWriteArrayList 或外部加锁。
一句话
优先 ArrayList，除非明确需要 LinkedList 的中间插入特性（实际很少）。