测量时间不能确认LinkedList优势

Question

我正在阅读ArrayList和LinkedList之间的区别，在何时使用LinkedList而不是ArrayList？中指出了这一点。我开发了一个小示例applcation来测试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();
    }

现在，它将始终指向列表的中间。有了这个基准，LinkedList要快得多。200000的结果：

LinkedList needed: 47
ArrayList needed: 4702