ArrayList vs. LinkedList vs. Vector
原文地址：http://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/
1. List 概述
List，如其名称，它是一个有序的元素序列。 当我们谈论 List 时，最好将它与 Set（一组独特和无序的元素）进行比较。以下是集合的类层次结构图，从图中我们可以对 Java Collections 有一个大体的了解。
2. ArrayList vs. LinkedList vs. Vector
上图中可以看出，它们都实现了 List 接口。 它们的使用方法也非常类似。但它们的主要区别在于它们的实现，不同操作将会导致它们具有不同的性能。
ArrayList 被实现为一个可调整大小的数组。 随着更多的元素被添加到 ArrayList，它的大小也是动态增加的。 它可以通过使用 get 和 set 方法直接访问元素，因为 ArrayList 本质上就是一个数组。
LinkedList 被实现为一个双向链表。 其添加和删除的性能优于 Arraylist，但在 get 和 set 方法上较前者差一些。
Vector 与 ArrayList 类似，但它是同步的。
如果您的程序是线程安全的，那么 ArrayList 是一个较好的选择。 当添加更多元素时，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。 通常情况下，大多数 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);
输出结果为：
ArrayList add: 13265642
LinkedList add: 9550057
ArrayList get: 1543352
LinkedList get: 85085551
ArrayList remove: 199961301
LinkedList remove: 85768810
他们性能的差异是显而易见的。 LinkedList 在添加和删除操作时更快，但在 get 时较慢。 基于复杂度表和测试结果，我们可以弄清楚何时使用 ArrayList 或 LinkedList。 简而言之，当以下情况，我们可以优先使用 LinkedList：
- 没有大量随机访问的元素
- 有大量的添加/删除操作