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

Question

我正在阅读 When to use LinkedList over ArrayList? 中指出的 ArrayList 和 LinkedList 之间的区别.我开发了一个小示例应用程序来测试 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();
    }

现在，它 将始终指向list 的中间。有了这个基准，LinkedList 就快多了。 200000 的结果:

LinkedList needed: 47
ArrayList needed: 4702