ArrayList的VS链表 [英] ArrayList Vs LinkedList

问题描述

我是跟随<一个href=\"http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist/322742#322742\">$p$pvious帖子这个，说：

 有关的LinkedList    *获取是O（n）
    *补充说明的是O（1）
    *删除是O（n）
    * Iterator.remove是O（1）对于ArrayList的    *得到的是O（1）
    *添加为O（1）摊销，但O（n）的最坏情况，因为数组必须调整大小和复制
    *删除是O（n）
 

所以通过看这个问题，我的结论是，如果我这样做只是顺序插在我的收藏的发言权5000000元，LinkedList的将远高于ArrayList的。

和如果我只是通过遍历即不敛于中元素获取从集合的元素，仍然会的LinkedList ArrayList的远高于。

现在来验证我上述两种说法，我写了下面的示例程序......但我很惊讶，我的上述发言被证明是错误的。

的ArrayList远胜链表在这两种情况下。花更少的时间比LinkedList的添加，以及从集合获取它们。有什么我做错了，或约链表和ArrayList最初的声明不会为规模500万的收藏品也是如此？

我提到的大小，因为如果我要素的数量减少到50000，LinkedList的表现更好，并首次发言也是如此。

 长nano1 = System.nanoTime（）;清单＆LT;整数GT; ARR =新的ArrayList（）;
的for（int i = 0; I＆LT; 5000000; ++ I）{
    arr.add（ⅰ）;
}
的System.out.println（（System.nanoTime（） -  nano1））;对于（INT记者：ARR）{
    ;
}
的System.out.println（（System.nanoTime（） -  nano1））;长亚硝酸钠= System.nanoTime（）;清单＆LT;整数GT; ARRL =新的LinkedList（）;
的for（int i = 0; I＆LT; 5000000; ++ I）{
    arrL.add（ⅰ）;
}
的System.out.println（（System.nanoTime（） - 亚硝酸钠））;对于（INT记者：ARRL）{
    ;
}
的System.out.println（（System.nanoTime（） - 亚硝酸钠））;
 

解决方案

记住，大O的复杂性描述渐近行为而不代表实际执行速度。它描述了每个操作的成本是如何生长的列表的大小，而不是各操作的速度。例如，的实施如下添加是O（1），但并不快：

 公共类MYLIST扩展的LinkedList {
    公共无效添加（对象o）{
        视频下载（10000）;
        super.add（O）;
    }
}
 

我怀疑你的情况ArrayList中表现良好，因为它会增加它的内部缓冲区的大小相当积极所以不会有大量的重新分配的。当缓冲区并不需要调整大小的ArrayList将会有更快的添加秒。

您还需要你的时候做这种分析要非常小心。我建议你​​改变你的分析code做一个预热阶段（所以JIT有机会做一些优化，而不会影响你的结果），并在若干运行的平均结果。

 私人最终静态INT热身= 1000;
私人最终静态INT TEST = 1000;
私人最终静态INT SIZE = 500000;公共无效perfTest（）{
    // 暖身
    的for（int i = 0; I＆LT;预热; ++ I）{
        buildArrayList（）;
    }
    //测试
    长总和= 0;
    的for（int i = 0; I＆lt;试; ++ I）{
        总和+ = buildArrayList（）;
    }
    的System.out.println（平均时间来建立数组列表：+（SUM / TEST））;
}众长buildArrayList（）{
    长启动= System.nanoTime（）;
    ArrayList的一个=新的ArrayList（）;
    的for（int i = 0; I＆LT;大小; ++ I）{
        a.add（ⅰ）;
    }
    长端= System.nanoTime（）;
    回到终点 - 启动;
}...同样为buildLinkedList
 

（注意：之可能溢出，你可能会更好使用 System.currentTimeMillis的（））

这也有可能是编译器优化了你的空 GET 循环。确保循环实际上并东西确保正确的code获取调用。

I was following a previous post on this that says:

For LinkedList

    * get is O(n)
    * add is O(1)
    * remove is O(n)
    * Iterator.remove is O(1)

For ArrayList

    * get is O(1)
    * add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
    * remove is O(n)

So by looking at this, I concluded that If I've to do just sequential insert in my collection for say 5000000 element, LinkedList will outclass ArrayList.

And If I've to just fetch the elements from collection by iterating i.e. Not grabbing the element in middle, still LinkedList will outclass ArrayList.

Now to verify my above two statements, I wrote below sample program... But I'm surprised that my above statements were proven wrong.

ArrayList outclass Linkedlist in both the cases. It took less time than LinkedList for adding as well as fetching them from Collection. Is there anything I'm doing wrong, or the initial statements about LinkedList and ArrayList does not holds true for collections of size 5000000?

I mentioned size, because if i reduce the number of elements to 50000, LinkedList perform better and initial statements holds true.

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for(int i=0;i<5000000;++i){
    arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );

for(int j: arr){
    ;
}
System.out.println( (System.nanoTime() - nano1) );

long nano2 = System.nanoTime();

List<Integer> arrL = new LinkedList();
for(int i=0;i<5000000;++i){
    arrL.add(i);
}
System.out.println( (System.nanoTime() - nano2) );

for(int j:arrL){
    ;
}
System.out.println( (System.nanoTime() - nano2) );

解决方案

Remember that big-O complexity describes asymptotic behaviour and may not reflect actual implementation speed. It describes how the cost of each operation grows with the size of the list, not the speed of each operation. For example, the following implementation of add is O(1) but is not fast:

public class MyList extends LinkedList {
    public void add(Object o) {
        Thread.sleep(10000);
        super.add(o);
    }
}

I suspect in your case ArrayList is performing well because it increases it's internal buffer size fairly aggressively so there will not be a large number of reallocations. When the buffer does not need to be resized ArrayList will have faster adds.

You also need to be very careful when you do this kind of profiling. I'd suggest you change your profiling code to do a warm-up phase (so the JIT has the opportunity to do some optimization without affecting your results) and average the results over a number of runs.

private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;

public void perfTest() {
    // Warmup
    for (int i = 0; i < WARMUP; ++i) {
        buildArrayList();
    }
    // Test
    long sum = 0;
    for (int i = 0; i < TEST; ++i) {
        sum += buildArrayList();
    }
    System.out.println("Average time to build array list: " + (sum / TEST));
}

public long buildArrayList() {
    long start = System.nanoTime();
    ArrayList a = new ArrayList();
    for (int i = 0; i < SIZE; ++i) {
        a.add(i);
    }
    long end = System.nanoTime();
    return end - start;
}

... same for buildLinkedList

(Note that sum may overflow and you might be better to use System.currentTimeMillis()).

It's also possible that the compiler is optimizing away your empty get loops. Make sure the loop actually does something to ensure that the right code is getting called.

这篇关于ArrayList的VS链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！