测量时间并不能证实LinkedList的优势

Question

我正在阅读ArrayList和LinkedList之间的区别，指出何时使用LinkedList而不是ArrayList？。我开发了一个小型示例应用程序来测试LinkedList的主要优势，但我获得的结果并未证实，LinkedList在操作性能方面超过了ArrayList：

ListIterator.add(E element)

这是我的代码：

public static void main(String[] args) {
        int number = 100000;
        long startTime1 = System.currentTimeMillis();
        fillLinkedList(number);
        long stopTime1 = System.currentTimeMillis();
        long startTime2 = System.currentTimeMillis();
        fillArrayList(number);
        long stopTime2 = System.currentTimeMillis();
        System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
        System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));
    }

    public static void fillLinkedList(int number){
        LinkedList<Integer> list = new LinkedList<Integer>();
        ListIterator<Integer> it = list.listIterator();
        int i = 0;
        while(i++<number){
            it.add(i);
        }
    //  System.out.println("LinkedList size: "+list.size());
    }

    public static void fillArrayList(int number){
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListIterator<Integer> it = list.listIterator();
        int i = 0;
        while(i++<number){
            it.add(i);
        }
    //  System.out.println("ArrayList size: "+list.size());
    }

测量结果为：

number            10,000     100,000     500,000      1,000,000     5,000,000
ArrayList            7         17         60             77           170
LinkedList           7         21         89             838          4127

我注意到元素的增加会显着损害LinkedList的性能，而ArrayList则表现出更好的行为。我明白了什么错误吗？

Answer 1

在

容器末尾或非常接近的地方添加元素时ArrayList更快，因为它不需要移动很多元素。在中间或开始时添加时，它很慢。我将您的循环更改为以下内容：

    while(i++<number){
        it.add(i);
        if(i%2 == 0)
            it.previous();
    }

现在，it将始终指向list的中间。有了这个基准，LinkedList的速度要快得多。200000 的结果：

LinkedList needed: 47
ArrayList needed: 4702

Answer 2

在

（数组或列表的）开头或中间插入和删除是列表击败数组的地方。

Answer 3

据我了解，LinkedList 的好处是将值插入给定索引（例如，中间或开头）。ArrayList不会在顺序插入上失败，因为它不必移动元素。

按上述方式填充列表后，查看将就位插入到不同位置会得到什么。我已经修改了您的示例，以显示 LinkedList 显着获胜的示例（至少在我的设置中）：

public static void main(String[] args) {
    int number = 5000000;
    LinkedList<Integer> llist = new LinkedList<Integer>();
    ArrayList<Integer> alist = new ArrayList<Integer>();
    long startTime1 = System.nanoTime();
    fillLinkedList(number, llist);
    long stopTime1 = System.nanoTime();
    long startTime2 = System.nanoTime();
    fillArrayList(number, alist);
    long stopTime2 = System.nanoTime();
    System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
    System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));
    startTime1 = System.nanoTime();
    llist.add(1, 4);
    stopTime1 = System.nanoTime();
    startTime2 = System.nanoTime();
    alist.add(1, 4);
    stopTime2 = System.nanoTime();
    System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
    System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));
}
public static void fillLinkedList(int number, LinkedList<Integer> list){

    ListIterator<Integer> it = list.listIterator();
    int i = 0;
    while(i++<number){
        it.add(i);
    }
    //  System.out.println("LinkedList size: "+list.size());
}

public static void fillArrayList(int number, ArrayList<Integer> list){
    ListIterator<Integer> it = list.listIterator();
    int i = 0;
    while(i++<number){
        it.add(i);
    }
    //  System.out.println("ArrayList size: "+list.size());
}