6

我正在阅读何时在ArrayListArrayList上使用 LinkedList？. 我开发了一个小示例应用程序来测试其主要优势，但我获得的结果并未证实，这超过了操作的性能：LinkedListLinkedListLinkedListArrayList

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

我注意到元素的增加显着损害了LinkedListwhile的性能，ArrayList表现出相当好的行为。我理解错了吗？

4

3 回答 3

6

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

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

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

LinkedList needed: 47
ArrayList needed: 4702
于 2013-10-05T15:17:33.743 回答
0

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

于 2013-10-05T15:27:57.287 回答
-1

据我了解，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());
}
于 2013-10-05T15:10:53.307 回答