ArrayList vs. LinkedList vs. Vector

1. List 概述

正如名字所指,List是元素的有序序列。在谈论List的时候和Set比较是个好主意,Set是一组唯一的无序的元素。 以下是Collection的类层次结构图。 从层次结构图中,您可以获得Java集合的一般概念。

Collection类关系图

2. ArrayList vs. LinkedList vs. Vector

从层次结构图中,它们都实现了List接口,使用起来非常相似,它们的主要区别是它们的实现方式,这导致了它们在不同的操作中不同的性能表现。

ArrayList 通过可变长度的数组来实现。随着更多的元素被添加到ArrayList中,它的长度随着动态增长。它的元素可以通过get和set方法直接访问,所以ArrayList实际上是一个数组。

LinkedList 通过一个双向链接实现。它在添加和删除元素上比ArrayList有更好的性能,但是在get和set上则相反。

Vector 和ArrayList类似,只是做了同步。

如果你的程序是要求线程安全的,ArrayList(译者注:Vector)是一个更好的选择。随着元素的添加Vector和ArrayList则需要更多的空间。Vector每次将数组的大小加倍,而ArrayList每次增加其大小的50%,然而LinkedList还实现了Queue接口,它增加了比ArrayList和Vector更多的方法,比如offer(),peek()、poll()等。

注意:ArrayList的默认初始化容量非常小。构造具有更高初始容量的ArrayList是一个好习惯。这可以避免调整大小成本。

3.ArrayList例子

ArrayList<Integer> al = new ArrayList<Integer>();
al.add(3);
al.add(2);      
al.add(1);
al.add(4);
al.add(5);
al.add(6);
al.add(6);
 
Iterator<Integer> iter1 = al.iterator();
while(iter1.hasNext()){
    System.out.println(iter1.next());
}

4. LinkedList 例子

LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(3);
ll.add(2);      
ll.add(1);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(6);
 
Iterator<Integer> iter2 = ll.iterator();
while(iter2.hasNext()){
    System.out.println(iter2.next());
}

正如上面例子所示,它们在使用上相似。真正的区别是它们底层的实现和它们操作的复杂性。

5.Vector

Vector几乎等同于ArrayList,区别是Vector是同步的。因为这个,它的开销比ArrayList高。通常大多数程序员使用ArrayList,因为他们自己可以显示同步。

6.ArrayList vs. LinkedList的性能比较

时间复杂度比较如下:

性能比较

add()在表中引用add(E e)(即是在列表末尾添加元素),而remove()引用remove(int index).

  • ArrayList 对于add/remove的任何索引都有O(1)时间复杂度,而对于列表结束出操作具有O(n)。
  • LinkedList对于Add/Remove的任意索引具有O(n)时间复杂度,而对于列表的结束/开始处的操作具有O(1)复杂度。

我用下面的代码来测试他们的性能:

ArrayList<Integer> arrayList = new ArrayList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
 
// 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

List性能比较

它们的性能差异是显而易见的。LinkedList在添加和删除中更快,但是get操作中更慢。基于复杂度表和测试结果,我们可以确定何时用ArrayList或LinkedList,总之LinkedList也许是更好的选择:

  • 没有大量元素的随机访问。
  • 有大量的数据添加和删除。

原文链接:ArrayList vs. LinkedList vs. Vector

  • qq_43638135
    妲己再美究为妃: 博主没有想过自己接一些私活干吗?我现在还没毕业,但是我也确实听说外挂市场自动化游戏脚本市场挺火热的,并且报酬也很丰厚,但是具体的我也不是很清楚,求解答。 (1个月前 #47楼) 查看回复(2) 举报 回复
    22