Java中的ArrayList，LinkedList和Vector_java arraylist、linkedlist、vector

原文地址： ArrayList vs. LinkedList vs. Vector，https://dzone.com/articles/arraylist-vs-linkedlist-vs
by Ryan Wang · Mar. 28, 13 · Java Zone · Analysis

1.List概述

顾名思义，List 是元素的有序序列。当我们谈论List时，最好将其与Set进行比较，Set是一组无序的元素集合，每个元素都是唯一的。以下是Collection的类层次结构图。

2. ArrayList，LinkedList 与 Vector

从层次结构图中，它们都实现了List接口。它们的用法非常相似。它们的主要区别是它们的实现，这会导致不同操作的不同性能。 ArrayList被实现为可调整大小的数组。随着将更多元素添加到ArrayList中，其大小将动态增加。由于ArrayList本质上是一个数组，因此可以使用get和set方法直接访问其元素。 LinkedList被实现为双链表。它在添加和删除上的性能优于Arraylist，但在获取和设置方法上却较差。 Vector与ArrayList相似，但是它是同步的。如果您的程序是线程安全的，则ArrayList是更好的选择。随着添加更多元素，Vector和ArrayList需要空间。向量每次都会使其数组大小加倍，而ArrayList每次都会增加其大小的50％。但是，LinkedList还实现了Queue接口，该接口添加了比ArrayList和Vector更多的方法，例如offer()，peek()，poll()等。注意：ArrayList的默认初始容量很小。构造具有较高初始容量的ArrayList是一个好习惯。这样可以避免调整大小的成本。

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

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 = al.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 的性能

时间复杂度比较如下：

使用以下代码测试其性能：

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);
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

输出为：

ArrayList add:      13,265,642 ns
LinkedList add:      9,550,057 ns
ArrayList get:       1,543,352 ns
LinkedList get:     85,085,551 ns
ArrayList remove:  199,961,301 ns
LinkedList remove:  85,768,810 ns
1
2
3
4
5
6