1.List 概述
正如名字所指，List是元素的有序序列。在谈论List的时候和Set比较是个好主意，Set是一组唯一的无序的元素。 以下是Collection的类层次结构图。 从层次结构图中，您可以获得Java集合的一般概念。
2.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
它们的性能差异是显而易见的。LinkedList在添加和删除中更快，但是get操作中更慢。基于复杂度表和测试结果，我们可以确定何时用ArrayList或LinkedList，总之LinkedList也许是更好的选择：
- 没有大量元素的随机访问。
- 有大量的数据添加和删除。
