java - ArrayList 与 LinkedList 的 JDK8 性能对比

Question

我开始看到越来越多的基准测试证明 ArrayList 在“大型”插入的性能方面碾压 LinkedList，示例如下: Gluelist

Adding(1M) Elements (5 Tests Avg.)

LinkedList: 174.8 milliseconds
ArrayList:  76.4 milliseconds
GlueList:   39.2 milliseconds

Adding(10M) Elements (5 Tests Avg.)

LinkedList: 8975.6 milliseconds
ArrayList:  4118.2 milliseconds
GlueList:   3320.1 milliseconds

我在带有 JDK8.latest 的 RHEL 7.2 上运行了类似的测试，并看到了类似的结果。我的印象是，即使在最坏的情况下，LinkedList 插入也是 O(1)，而 ArrayList 由于复制操作而需要 > O(1)(我意识到我们可以讨论摊销成本，但这超出了范围) 。我的问题是:考虑到 ArrayList 在接近达到容量时强制进行复制操作，LinkedList 的性能如何比 ArrayList 差？

Answer 1

它们有相同的大 O，但这并不能告诉您恒定的关系。它告诉您它们在理想机器而不是真实机器上的行为方式。

LinkedList 分配并使用更多内存。它为每个节点创建一个 24 字节的对象，而 ArrayList 每个引用使用 4 个字节(通常)，并且创建的对象要少得多。