Java LinkedList 头尾高效插入技巧

Java LinkedList 在头尾插入（如 addFirst/addLast）时具有 O(1) 时间优势，远快于 ArrayList 的 O(n) 插入开销，但这一优势极易被误用抹杀：调用 add(0, e) 或 add(size(), e) 会触发链表遍历，性能骤降10–50倍；随机访问 get(i) 同样导致 O(n) 开销，应改用 getFirst()/getLast() 或更安全的 peekFirst()/peekLast()；更佳实践是直接使用 Deque 接口（如 offerFirst/pollFirst），语义清晰且规避空指针风险；还需警惕 LinkedList 内存不友好——每个节点携带 prev/next/item 三个引用，GC 压力大、缓存命中率低，高频插入后若需频繁遍历，ArrayList 配合批量操作反而更高效。

LinkedList 头尾插入为什么比 ArrayList 快

因为 LinkedList 是双向链表实现，addFirst() 和 addLast() 都是 O(1) 操作，不涉及数组扩容或元素搬移；而 ArrayList 的 add(0, e) 是 O(n)，每次都要整体右移元素。

但注意：这仅对「纯头尾插入」成立。一旦混入随机索引访问（如 get(100)），LinkedList 就会退化成 O(n) 遍历，比 ArrayList 慢得多。

用 addFirst() / addLast() 而不是 add(int, E)

add(int, E) 在 LinkedList 中仍需遍历定位索引位置——哪怕你总传 0 或 size()，它也不会自动优化为头/尾操作。

• ✅ 正确：list.addFirst("a")、list.addLast("b")
• ❌ 低效：list.add(0, "a")、list.add(list.size(), "b")（触发内部遍历）

实测在万级元素下，后者比前者慢 10–50 倍，取决于 JVM 和链表长度。

避免用 get(i) 触发链表遍历

即使你只偶尔查一下头/尾元素，也别写 list.get(0) 或 list.get(list.size()-1)——它们会从头/尾开始逐个 next/prev，O(n) 开销白送。

• ✅ 查头：用 list.getFirst()（或 list.peekFirst()，空时返回 null）
• ✅ 查尾：用 list.getLast()（或 list.peekLast()）
• ⚠️ 注意：getFirst()/getLast() 在空列表时抛 NoSuchElementException，生产环境优先用 peekXxx()

别为了“看起来像队列”而忽略接口语义

LinkedList 实现了 Deque，但直接用 Deque 接口更安全、意图更清晰：

Deque<String> queue = new LinkedList<>();
queue.offerFirst("a"); // 等价 addFirst，但失败时返回 false 而非异常
queue.offerLast("b"); // 等价 addLast
String head = queue.pollFirst(); // 安全取头，空时返回 null

这样既避免空指针风险，又让代码明确表达「我就是在当双端队列用」，而不是误用 List 接口干队列的事。

真正容易被忽略的是：JVM 对 LinkedList 的内存布局不友好——每个节点含 3 个引用（prev/next/item），GC 压力和缓存命中率都比紧凑的数组差。高频插入场景下，如果后续还要批量遍历，有时用 ArrayList + 批量 addAll() 反而更稳。

今天关于《Java LinkedList 头尾高效插入技巧》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！