如果在列表中间插入,LinkedList是否真的比ArrayList快？

Question

- LinkedList和之间有什么区别ArrayList？什么时候最好使用LinkedList？

我认为每个Java开发人员至少在面试时都听过一次这个问题.

- 如果您希望能够在列表中间插入项目,则最好使用链接列表.

这是这个问题的常见答案.大家都知道.每当你问一个关于List实现之间差异的问题时,你会得到如下答案:

我什么时候应该使用LinkedList？什么时候需要在元素之间或开始时有效删除？

从这里

忘了提到插入费用.在LinkedList中,一旦你有正确的位置,插入成本O(1),而在ArrayList中它会上升到O(n)- 必须移动经过插入点的所有元素.

从这里

当您希望能够在列表中间插入项目(例如优先级队列)时,链接列表优于数组.

从这里

ArrayList较慢,因为它需要复制部分数组才能删除已经空闲的插槽.LinkedList只需要操作几个引用.

从这里

和更多...

但你有没有试过自己重现它？我昨天试过并得到了这些结果:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List<Integer> linkedList = new LinkedList<Integer>();
        List<Integer> arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(MAX_VAL/2, i);
        }
        System.out.println("LL time: " + (System.nanoTime() - time));
        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            arrayList.add(MAX_VAL/2, i);
        }
        System.out.println("AL time: " + (System.nanoTime() - time));
    }
}

输出:

LL时间:114098106

AL时间:24121889

那是什么？为什么LinkedList太吸引人了？也许我们应该尝试删除操作而不是添加？好的,让我们试试:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List<Integer> linkedList = new LinkedList<Integer>();
        List<Integer> arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();
        for(int i = 0; i < MAX_VAL/2; i++) {
            linkedList.remove(MAX_VAL/2);
        }
        System.out.println("LL time: " + (System.nanoTime() - time));
        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL/2; i++) {
            arrayList.remove(MAX_VAL/2);
        }
        System.out.println("AL time: " + (System.nanoTime() - time));
    }
}

输出:

LL时间:27581163

AL时间:3103051

哦,ArrayList仍然比LinkedList快.是什么原因？这个神话被破坏了吗？或许我错了？

Answer 1

破获

并不是的.这里

for(int i = 0; i < MAX_VAL; i++) {
    linkedList.add(MAX_VAL/2, i);
}

你不只是插入项目; 你支付从一开始到i每次迭代的费用.当然,那就是O(i).

另一方面,在您真正见证中间列表插入的性能优势之前,列表必须非常大.System.arraycopy是一个超快速的操作,另一方面,每次插入都LinkedList需要分配一个节点实例.

总之,ArrayList对于99%或更多的实际案例来说,这是一个更好的选择,并且利用a的狭隘优势LinkedList需要非常谨慎.

关于微博加密JVM的一般说明

我还应警告您,您的基准测试代码严重不足.在JVM上进行微操作时,需要注意相当大的事项清单,例如:

• 总是热身代码让JIT编译器得到它;
• nanoTime由于准确性/精度问题,要非常小心地解释结果.使读数增长至少几毫秒(百万纳秒)以确保可靠性;
• 控制垃圾收集器的虚假副作用;
• 等等

因此,建议使用现成的微基准测试框架,如OpenJDK的jmh.

Answer 2

为了演示add()操作的(in)有效性,最好使用ListIterator对象而不是list对象.如果直接在链表上使用add()方法,它将从列表头开始,并且必须迭代到要插入项的位置.这部分需要O(n).如果使用ListIterator,它将保持我们添加元素的位置,并且算法不必每次都迭代到列表的中间.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List<Integer> linkedList = new LinkedList<Integer>();
        List<Integer> arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();


        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(MAX_VAL/2, i);
        }
        System.out.println("LL time:\t" + (System.nanoTime() - time));

        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            arrayList.add(MAX_VAL/2, i);
        }
        System.out.println("AL time:\t" + (System.nanoTime() - time));


        //Reset the lists
        linkedList = new LinkedList<Integer>();
        arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }

        time = System.nanoTime();
        ListIterator<Integer> li = linkedList.listIterator(MAX_VAL/2);
        for(int i = 0; i < MAX_VAL; i++) {
            li.add(i);
        }
        System.out.println("LL iterator:\t" + (System.nanoTime() - time));

        time = System.nanoTime();
        ListIterator<Integer> ali = arrayList.listIterator(MAX_VAL/2);
        for(int i = 0; i < MAX_VAL; i++) {
            ali.add(i);
        }
        System.out.println("AL iterator:\t" + (System.nanoTime() - time));
    }
}

我的结果显示在LinkedList上使用ListIterator可以在"中间"中插入元素的最佳性能:

LL time:     237819474
AL time:      31410507
LL iterator:   5423172
AL iterator:  23975798