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

（数组或列表）开头或中间的插入和删除是一个列表胜过一个数组的地方

Answer 2

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

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

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

LinkedList needed: 47
ArrayList needed: 4702

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());
}