测量时间并不能确认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();
    }

现在,it总是指向中间list.有了这个基准,LinkedList速度就快得多.结果为200000:

LinkedList needed: 47
ArrayList needed: 4702