Java集合框架中的ArrayList与LinkedList选择_技术教程

优先选ArrayList：随机访问多、频繁get/set或for循环遍历时；LinkedList内存开销大、GC压力高，固定大小场景应预设容量或用Arrays.asList。

随机访问多就选 `ArrayList`

如果代码里频繁用 get(i)、set(i, e) 或遍历用传统 for 循环（for (int i = 0; i ），ArrayList 几乎总是更优。它的底层是数组，get 是 O(1) 时间复杂度，而 LinkedList 要从头或尾开始跳节点，平均 O(n/2)，实际慢好几倍。

常见错误现象：把 LinkedList 当成“万能快链表”，在日志聚合、分页数据缓存等场景下盲目替换 ArrayList，结果 get(999) 变成性能瓶颈。

ArrayList 的 get 直接算内存偏移，无分支、无指针跳转
LinkedList 的 get 会先比对索引离头近还是离尾近，再决定正向/反向遍历 —— 这个判断本身就有开销
JVM 对数组连续内存的预取（prefetch）友好，ArrayList 遍历时 CPU 缓存命中率高得多

头尾频繁增删才值得考虑 `LinkedList`

LinkedList 真正有优势的场景非常窄：只在头或尾做大量 addFirst()、addLast()、removeFirst()、removeLast()，且几乎不用随机访问。比如实现栈（push/pop）、队列（offer/poll）的底层容器，或者消息缓冲区的双端写入。

注意：add(index, e) 和 remove(index) 在 LinkedList 中仍是 O(n)，因为必须先 get(index) 找到位置 —— 这点很多人误以为是 O(1)。

ArrayList 尾部 add(e) 均摊 O(1)，但头部或中间插入要移动后续所有元素，O(n)
LinkedList 头尾操作确实是 O(1)，但每个元素额外占用两个指针内存（8 字节 × 2，在 64 位 JVM + 压缩指针下可能为 12 字节）
现代 JVM 对小对象分配优化极好，ArrayList 扩容时的数组复制开销，常被低估但实际可控

别用 `LinkedList` 替代 `ArrayDeque`

如果你需要高效双端操作，优先看 ArrayDeque，而不是 LinkedList。前者是循环数组实现，内存局部性好、无

指针开销、GC 压力小，所有操作（addFirst、addLast、pollFirst、pollLast）都是 O(1) 且常数因子更低。

Deque queue = new ArrayDeque<>();
queue.offerLast("a");
queue.pollFirst(); // 比 LinkedList 快，且不产生多余对象

LinkedList 实现了 Queue 和 Deque 接口，容易让人误以为它是标准队列实现 —— 但 JDK 自己的文档都明确建议：“This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.”（指 ArrayDeque）

ArrayDeque 不允许 null 元素，LinkedList 允许 —— 如果业务逻辑依赖 null，才是少数必须用 LinkedList 的理由
LinkedList 的迭代器（Iterator）是 fail-fast，但它的 ListIterator 支持双向遍历；ArrayDeque 只提供单向迭代器

扩容机制和内存占用差异不能忽略

ArrayList 初始容量为 10，扩容时按 1.5 倍增长（oldCapacity + (oldCapacity >> 1)）；LinkedList 没有容量概念，每加一个元素就新建一个 Node 对象。这意味着：

存 1000 个 Integer，ArrayList 占用约 1000 × 4 字节（int 基本类型）+ 数组对象头 ≈ 4KB；LinkedList 是 1000 × (Node 对象头 + 3 个引用字段) ≈ 24–32KB，差一个数量级
ArrayList 扩容会产生旧数组的 GC 压力，但只发生在增长拐点；LinkedList 每次 add 都触发一次小对象分配，GC 频率更高
如果集合大小基本固定（如配置项列表、枚举映射），直接用 Arrays.asList(...) 或指定初始容量的 ArrayList(int initialCapacity)，避免扩容