1. List概念

List正如其名，是一个一组有序的元素。当我说List，最好比较一下。Set 中的元素是唯一、有序的。下图是集合的层次结构图，从中你可以了解到集合的概念。

集合层次图

2.ArrayList vs. LinkedList vs. Vector

从上面的继承图我们了解到它们都实现了List接口。它们使用方式都很相似。最主要是的实现区别是当使用不同操作性能会不同。

ArrayList是可变大小(容量)数组的实现。当有更多的元素加入ArrayList，ArrayList是会自动增加大小的。它的元素可以使用get 和 set方法来访问，因为ArrayList 本质还是地址连续的数组。

LinkedList是双链表的实现。它add 和 remove操作的性能会比Arraylist高不少，但是get 和 set操作就比 Arraylist差。

Vector和ArrayList很像，但是它是同步的。

当你的程序是线程安全的，那么ArrayList 是比较好的选择。当添加比较多的元素的时候Vector 和 ArrayList 需要更多的空间。Vector的增长方式是双倍其大小，ArrayList 是50% 的增长。LinkedList也实现Queue 接口所以功能比ArrayList 和 Vector较多，比如：offer(), peek(), poll()等等。

注意：默认初始化ArrayList 的大小是非常小的，如果你想创建一个有很大容量的ArrayList，好的习惯是使用构造方法指定大小。这样会减少增加容量的时间花费。

3.ArrayList 例子

1
2
3
4
5
6
7
8
9
10
11
12
13
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 例子

1
2
3
4
5
6
7
8
9
10
11
12
13
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开销多。通常情况下，大多数Java程序员使用的ArrayList，而不是Vector，因为他们可以自己的显式控制同步。

6.ArrayList vs. LinkedList的性能

时间复杂度比较如下：

时间复杂度比较

add() 在表中代表 add(E e), 同样 remove() 是说 remove(int index)

  • ArrayList 在随意的add/remove时，时间复杂度是O(n)，但是只是在最后add/remove时是O(1).
  • LinkedList 在随意add/remove时，时间复杂度是O(n)，但是在开头或者结尾操作时间复杂度是 O(1)。

我使用了下面的代码测试了其性能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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

性能图

对于这两者，很明显LinkedList在add 和 remove比较快，但是get比较慢。基于这个表的测试结果，我们可以知道什么时使用的ArrayList，什么时候使用LinkedList。总之，如果满足如下情况LinkedList应该优先考虑：

  • 元素访问不是随机访问
  • add/remove比较频繁

参考文档