Java LinkedList速度优势验证：仅头部插入更高效？

你的实验结果完全符合Java集合的实际性能表现，先给你明确结论：

1. 你观察到的LinkedList仅头部插入有明显速度优势，在基于索引的中间插入、随机访问场景下不如ArrayList，这个结论是对的；
2. 但LinkedList的实用场景不止头部插入，还有不少适合它的场景。

为什么你的中间插入测试里LinkedList更慢？ #

你用的add(int index, E)方法，对LinkedList来说分两步：

• 第一步是定位到索引对应的节点：因为LinkedList是双向链表，没有数组的随机访问能力，必须从头或尾开始遍历到目标位置（即使会判断从哪端更近，中间位置还是要遍历约n/2个节点），这一步是O(n)时间；
• 第二步才是插入节点，这一步确实是O(1)。

而ArrayList的add(int index, E)是直接移动index后的所有元素（O(n)时间），但因为数组是连续内存，CPU缓存命中率更高，实际执行速度反而比LinkedList的“遍历+插入”更快——从你的测试结果也能看出来：LinkedList中间插入用了6896ms，ArrayList只用了940ms，差距明显。

LinkedList还有哪些实用场景？ #

除了头部插入，这些场景选LinkedList更合适：

• 频繁在链表两端（头+尾）做插入/删除：比如实现队列、双端队列（Deque），LinkedList本身就实现了Deque接口，addFirst()、removeLast()这些操作都是O(1)，性能稳定；而ArrayList头部操作始终要移动所有元素，数据量越大越慢。
• 用迭代器遍历过程中频繁插入/删除：比如遍历列表时，在当前遍历位置插入或删除元素，LinkedList的ListIterator可以直接通过节点指针完成操作，不需要重新定位，O(1)时间；而ArrayList的迭代器做这些操作会触发后续元素移动，O(n)时间，频繁操作时差距极大。
• 超大容量数据存储：ArrayList需要连续的内存空间来存数组，当数据量达到几百万甚至更多时，可能无法分配到足够大的连续内存块；LinkedList的节点是分散存储的，不会有这个问题。

补充：如果想发挥LinkedList中间插入的优势 #

如果你的中间插入不是基于索引，而是基于迭代器的当前位置（比如先遍历到某个元素，然后在它旁边插入），那LinkedList的性能会立刻反超ArrayList——因为这时候不需要从头/尾遍历定位，直接插入即可。

总结下：你的实验结论针对“基于索引的操作场景”是准确的，但选择集合类要结合具体操作类型，LinkedList在很多非索引依赖的场景下，依然是最优选择。

内容的提问来源于stack exchange，提问作者tegowai