ArrayList vs. LinkedList vs. Vector

1. List概览

List,就像它的名字暗示的一样,是一组排列有序的元素。当我们讨论List的时候,很容易将它和Set作比较。Set是一组唯一的而且排列无序的元素。

下图是集合类的层次结构图。你可以总体上知道我们今天讨论的主题。

2. ArrayList vs. LinkedList vs. Vector

从上图可知,它们都实现了List接口。它们的用法差不多,主要的区别在于它们对于不同操作的操作速度不同。

ArrayList是可以改变大小的数组。当有元素添加到ArrayList中去时,它的大小动态的增加。元素可以直接通过get()和set()方法进行访问,因为ArrayList实际上是数组。LinkedList是个双向链表。它的add()和remove()方法比ArrayList快,但是get()和set()方法却比ArrayList慢。Vector和ArrayList类似,但是Vector是同步的。如果在线程安全的环境下,使用ArrayList是更好的选择。添加元素的时候,当超过初始容量的时候,Vector和ArrayList需要更多的空间:Vector需要将数组的大小增加一倍,而ArrayList需要增加50%。

LinkedList还实现了Queue接口,这样就比ArrayList和Vector多出了一些方法如offer(), peek(), poll()等。

注意:ArrayList的初始容量(initial capacity)很小。我们应该设置一个比较大的初始容量,这样可以避免重新改变大小。

3. ArrayList的例子

ArrayList al = new ArrayList();
al.add(3);
al.add(2);      
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(6);

Iterator iter1 = al.iterator();
while(iter1.hasNext()){
    System.out.println(iter1.next());
}

4. LinkedList的例子

LinkedList ll = new LinkedList();
ll.add(3);
ll.add(2);      
ll.add(1);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(6);

Iterator iter2 = ll.iterator();
while(iter2.hasNext()){
    System.out.println(iter2.next());
}

由上可见,它们的用法相同,主要的区别在于它们内部的实现,以及操作的复杂度的不同。

5. Vector

Vector几乎和ArrayList相等,主要的区别在于Vector是同步的。正因为此,Vector比ArrayList的开销更大。通常大部分程序员都使用ArrayList,他们可以自己写代码进行同步。

6. ArrayList vs. LinkedList的性能比较

时间复杂度如下:

* 表中的add()指的是add(E e)(即是在列表末尾添加元素),remove()方法指的是remove(int index)。

ArrayList对于任意索引的插入/删除操作的时间复杂度是O(n),而在列表的尾部的操作时间为O(1)。

LinkedList对于任意索引的插入/删除操作的时间复杂度是O(n),而在列表的头部或尾部的操作时间为O(1)。

(译者注:这里原文解释的不是太清楚。对于任意索引的插入/删除操作

Arrays:

  • 找到插入/删除位置的时间复杂度是O(1)
  • 进行插入/删除操作的时间复杂度是O(n)

Linked Lists:

  • 找到插入/删除位置的时间复杂度是O(n)
  • 进行插入/删除操作的时间复杂度是O(1)

我使用下面的代码测试它们的性能:

ArrayList arrayList = new ArrayList();
LinkedList linkedList = new LinkedList();

// ArrayList add
long startTime = System.nanoTime();

for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("ArrayList add:  " + duration);

// LinkedList add
startTime = System.nanoTime();

for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList add: " + duration);

// ArrayList get
startTime = System.nanoTime();

for (int i = 0; i < 10000; i++) {
    arrayList.get(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList get:  " + duration);

// LinkedList get
startTime = System.nanoTime();

for (int i = 0; i < 10000; i++) {     linkedList.get(i); } endTime = System.nanoTime(); duration = endTime - startTime; System.out.println("LinkedList get: " + duration); // ArrayList remove startTime = System.nanoTime(); for (int i = 9999; i >=0; i--) {
    arrayList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("ArrayList remove:  " + duration);

// LinkedList remove
startTime = System.nanoTime();

for (int i = 9999; i >=0; i--) {
    linkedList.remove(i);
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedList remove: " + duration);

输出如下:

ArrayList add:  13265642
LinkedList add: 9550057
ArrayList get:  1543352
LinkedList get: 85085551
ArrayList remove:  199961301
LinkedList remove: 85768810

它们的性能的差别很显著。LinkedList对于add()和remove()相对于ArrayList要快,但是get()要慢些。按照复杂度以及测试结果来看,我们很容易知道什么时候该使用ArrayList,什么时候该使用LinkedList。简而言之,下面的情况该使用LinkedList:

  • 如果没有大量的随机访问
  • 如果有很多add/remove的操作
原文链接: Programcreek 翻译: ImportNew.com - 唐小娟
译文链接: http://www.importnew.com/8782.html
[ 转载请保留原文出处、译者和译文链接。]

关于作者: 唐小娟

一名在路上的程旭媛

查看唐小娟的更多文章 >>



相关文章

发表评论

Comment form

(*) 表示必填项

5 条评论

  1. Carl Ye 说道:

    很荣幸每天都能在这里重新复习,以及学习更多的细节。

    上文提到“当添加元素的时候,Vector和ArrayList需要更多的空间:Vector每次将数组的大小增加一倍,而ArrayList每次增加50%。”

    我觉得应该加入以下说明会更清楚:
    每次添加元素的时候,都会先判断大小是否超过当前的空间大小,如果是,才进行扩容。

    我第一次看的时候迷惑了,”每次讲数组的大小xxx“.

    谢谢。

    Thumb up 0 Thumb down 0

  2. Ryan 说道:

    最后对比性能的代码似乎不能代表他们的性能差异。
    比如说al和ll的add方法。单纯的add都是在末尾添加,这样他们的时间复杂度应该都是O(1),而没有体现al需要移动元素,而ll只需要修改指针的特性。
    删除同理。

    Thumb up 0 Thumb down 0

  3. sddtc 说道:

    想补充一下为什么会有这个:
    注意:ArrayList的初始容量(initial capacity)很小。我们应该设置一个比较大的初始容量,这样可以避免重新改变大小

    因为数组扩容是对ArrayList效率影响比较大的一个因素
    每当执行Add、AddRange、Insert、InsertRange等添加元素的方法,都会检查内部数组的容量是否不够了,如果是,它就会以当前容量的两倍来重新构建一个数组,将旧元素Copy到新数组中,然后丢弃旧数组,在这个临界点的扩容操作,应该来说是比较影响效率的
    比如,一个可能有200个元素的数据动态添加到一个以默认16个元素大小创建的ArrayList中,将会经过: 16*2*2*2*2 = 256 四次的扩容才会满足最终的要求,那么如果一开始就以:
    ArrayList List = new ArrayList( 210 );
    的方式创建ArrayList,不仅会减少4次数组创建和Copy的操作,还会减少内存使用

    Thumb up 1 Thumb down 0

  4. kameleon 说道:

    谢谢楼主,复习了好多东西,另外就是那个性能的测试可以用Spring的AOP来写,应该会更方便一点!

    Thumb up 0 Thumb down 0

跳到底部
返回顶部