Filling ArrayList vs LinkedList

Question

我一直认为LinkedList填充得比ArrayList快。正如我所知，ArrayList是基于长度有限（常数）的简单数组。因此，每次数组超出范围时，都会创建范围更高的新数组。CCD_ 4要简单得多。它没有任何限制（除了内存），所以应该更快地填充。但我运行下一个代码：

 public static void main(String[] args) {
        int length = 7000000;
        List<Integer> list = new LinkedList<Integer>();
        long oldTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            list.add(i);
        }
        System.out.println("LinkedList fill: " + (System.currentTimeMillis() - oldTime));
        list = new ArrayList<Integer>();
        oldTime = System.currentTimeMillis();
        for (int i = 0; i < length; i++) {
            list.add(i);
        }
        System.out.println("ArrayList fill: " + (System.currentTimeMillis() - oldTime));
    }

输出为：

LinkedList fill: 3936
ArrayList fill: 628

为什么会这样？

Answer 1

在Java中，不能真正对性能进行基准测试。请参阅如何用Java编写正确的微基准测试？以获得对许多可能出错的事情的更详细的解释。

如果我用jmh测试你的代码，我会得到以下结果：

Benchmark                      Mode  Samples  Score   Error  Units
c.a.p.SO26404256.arrayList     avgt        5  7.661 ± 0.672  ms/op
c.a.p.SO26404256.linkedList    avgt        5  9.675 ± 1.213  ms/op

因此，填充LinkedList似乎比填充arrayList稍微慢一些，但差异比测试显示的要小得多。

至于差异的原因，可能是因为LinkedList的每个元素都封装在Node中：这意味着更多的对象创建和更多的垃圾收集。ArrayList中的数组副本所造成的损失可能比您想象的要小，因为它们经过了高度优化。