java - Java 中 ArrayList 和 LinkedList 的区别——性能的原因

Question

我认为我在理论上很好地理解了 ArrayList 和 LinkedList 之间的区别。然而，这是第一次，我对其进行了一些测试，测试结果与我的预期大相径庭。

期望:

1. Arraylist 在插入时会比 LinkedList 慢 开始，因为它必须“移动”元素，对于链表，它的 仅更新 2 个引用。

   现实:在大多数迭代中都是一样的。对于少数人 迭代，它更慢。

现实:从 beg 中删除时性能相同。

测试用例:1,000,000 个元素

public static void main(String[] args) {
    int n = 1000000;

    List arrayList = new ArrayList(n+10);
    long milis = System.currentTimeMillis();
    for(int i= 0 ;i<n;i++){
        arrayList.add(i);
    }
    System.out.println("insert arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    List linkedList = new LinkedList();
    milis = System.currentTimeMillis();
    for(int i= 0 ;i<n;i++){
        linkedList.add(i);
    }
    System.out.println("insert linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //System.out.println("Adding at end");
    milis = System.currentTimeMillis();
    arrayList.add(n-5,n+1);
    System.out.println("APPEND arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(n-5,n+1);
    System.out.println("APPEND linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //add at front
    milis = System.currentTimeMillis();
    arrayList.add(0,0);
    System.out.println("INSERT BEG arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(0,0);
    System.out.println("INSERT BEG linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //add at middle
    milis = System.currentTimeMillis();
    arrayList.add(n/2,n/2);
    System.out.println("INSERT MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.add(n/2,n/2);
    System.out.println("INSERT MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //get from front, mid, end
    milis = System.currentTimeMillis();
    arrayList.get(0);
    System.out.println("get front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(0);
    System.out.println("get front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.get(n/2);
    System.out.println("get MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(n/2);
    System.out.println("get MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.get(n-4);
    System.out.println("get last arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.get(n-4);
    System.out.println("get last linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    //delete from front, mid, end.
    milis = System.currentTimeMillis();
    arrayList.remove(0);
    System.out.println("del front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(0);
    System.out.println("del front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.remove(n/2);
    System.out.println("del mid arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(n/2);
    System.out.println("del mid linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    arrayList.remove(n-4);
    System.out.println("del end arraylist takes "+(System.currentTimeMillis()-milis)+" ms");

    milis = System.currentTimeMillis();
    linkedList.remove(n-4);
    System.out.println("del end linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");

}

输出日志

insert arraylist takes 141 ms
insert linkedlist takes 312 ms
APPEND arraylist takes 0 ms
APPEND linkedlist takes 0 ms
INSERT BEG arraylist takes 0 ms
INSERT BEG linkedlist takes 0 ms
INSERT MIDDLE arraylist takes 0 ms
INSERT MIDDLE linkedlist takes 0 ms
get front arraylist takes 0 ms
get front linkedlist takes 0 ms
get MIDDLE arraylist takes 0 ms
get MIDDLE linkedlist takes 16 ms
get last arraylist takes 0 ms
get last linkedlist takes 0 ms
del front arraylist takes 0 ms
del front linkedlist takes 0 ms
del mid arraylist takes 0 ms
del mid linkedlist takes 15 ms
del end arraylist takes 0 ms
del end linkedlist takes 0 ms

那是什么原因呢？使用 JDK 1.6。

编辑:使用 System.nanotime() 后，它确实如我所料地给出了答案。同意，这只是一次试验，应该取平均值。

insert arraylist takes 137076082 ns
insert linkdlist takes 318985917 ns
APPEND arraylist takes 69751 ns
APPEND linkdlist takes 98126 ns
**INSERT BEG arraylist takes 2027764 ns
INSERT BEG linkdlist takes 53522 ns**
INSERT MIDDLE arraylist takes 1008253 ns
INSERT MIDDLE linkdlist takes 10395846 ns
get front arraylist takes 42364 ns
get front linkdlist takes 77473 ns
get MIDDLE arraylist takes 39499 ns
get MIDDLE linkdlist takes 9645996 ns
get last arraylist takes 46165 ns
get last linkdlist takes 43446 ns
**del front arraylist takes 1720329 ns
del front linkdlist takes 108063 ns**
del mid arraylist takes 1157398 ns
del mid linkdlist takes 11845077 ns
del end arraylist takes 54149 ns
del end linkdlist takes 49744 ns

Answer 1

对您的前两个(奇怪的)测试编号的解释是:

插入到 ArrayList 中通常比较慢，因为一旦达到其边界，它就必须增长。它将必须创建一个新的更大的数组，并从原始数组复制数据。

但是当您创建一个已经很大足以容纳所有插入的 ArrayList 时(这是您的情况，因为您正在执行 new ArrayList(n+10) ) - 它显然不会涉及任何数组复制操作。添加到它甚至比使用 LinkedList 更快，因为 LinkedList 将不得不处理它的“链接”(指针)，而巨大的 ArrayList 只是在给定的(最后一个)索引处设置值。

此外，您的测试也不好，因为每次迭代都涉及自动装箱(从 int 到 Integer 的转换)- 这样做既需要额外的时间，也会因为 Integers cache 而搞砸结果。这将在第一次通过时被填充。