Java List 对比：ArrayList vs. LinkedList vs. Vector_java 排行 arraylist vector

Java List 对比：ArrayList vs. LinkedList vs. Vector

本文译自：ArrayList vs. LinkedList vs. Vector

1. List概览

List，顾名思义，是元素的有序序列。当我们谈论 List 时，最好将它与 Set 进行比较，Set 是一组唯一且无序的元素。下面是Collection的类层次结构图。从层次结构图中，您可以大致了解 Java 集合。

2. ArrayList vs. LinkedList vs. Vector

从层级图来看，都是实现列表界面。它们的使用非常相似。它们的主要区别在于它们的实现会导致不同操作的不同性能。

数组列表被实现为一个可调整大小的数组。随着更多元素添加到 ArrayList，其大小会动态增加。它的元素可以通过使用 get 和 set 方法直接访问，因为 ArrayList 本质上是一个数组。

LinkedList被实现为双LinkedList。它在 add 和 remove 上的性能优于 Arraylist，但在 get 和 set 方法上更差。

向量与 ArrayList 类似，但它是同步的。

如果您的程序是线程安全的，ArrayList 是更好的选择。随着添加更多元素，Vector 和 ArrayList 需要更多空间。Vector 每次都会将其数组大小加倍，而 ArrayList 每次都会增加其大小的 50%。然而，LinkedList 也实现了队列接口比 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());
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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());
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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

5. Vector

Vector 和 ArrayList 几乎是一样的，不同的是 Vector 是同步的。正因为如此，它比 ArrayList 有开销。通常，大多数 Java 程序员使用 ArrayList 而不是 Vector，因为它们可以自己显式同步。

6. ArrayList 与 LinkedList 的性能

时间复杂度对比如下：

• 表中的add()指的是add(E e)，remove()指的是remove(int index)

• ArrayList 对于任意索引的添加/删除具有 O(n) 时间复杂度，但对于列表末尾的操作具有 O(1) 时间复杂度。

• LinkedList 对于添加/删除的任意索引具有 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);
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 add:  13265642
LinkedList add: 9550057
ArrayList get:  1543352
LinkedList get: 85085551
ArrayList remove:  199961301
LinkedList remove: 85768810
1
2
3
4
5
6

它们的性能差异是显而易见的。LinkedList 添加和删除速度更快，但获取速度更慢。根据复杂度表和测试结果，我们可以确定何时使用 ArrayList 或 LinkedList。简而言之，在以下情况下，应首选 LinkedList：

• 没有大量随机访问元素
• 有大量的添加/删除操作