【总结】Java基础之List：ArrayList vs. LinkedList vs. Vector

总结平时常用的Collection子接口：List接口以及其实现类。

类图如下：


List接口，它是一个有序的collection容器（也被叫做序列）。List允许存入空元素，也允许存入重复的元复（这和另一个接口Set不同）。List常用的实现类有ArrayList, LinkedList以及Vector。

1、Vector
它是最古老的实现（since JDK1.0），但并不是很常用，原因是因为它是线程安全的，这意味着所有方法都加锁，效率不高。

2、ArrayList和LinkedList
List另外两个实现类是ArrayList和LinkedList。
a. 两个类的实现不一样，ArrayList是动态数组，所以它的长度是动态增加的。而LinkedList是双向链表的一个实现。两个类主要的区别在于对于元素操作的时间复杂度不一样：

	ArrayList<E>	LinkedList<E>
get(int index)	O(1) <---优势	O(n)
add(E element)	O(1) amortized。但是最坏结果是O(n)，原因是array数组需要重新计算长度	O(1)
add(int index, E element)	O(n - index) amortized但是最坏结果是O(n)，原因同上	O(n)。步骤：a.需要先找到元素的位置O(n)，b.插入元素O(1)
remove(int index)	O(n - index)。例如：删除最后一个元素O(1)	O(n)。步骤：a.需要先找到元素的位置O(n)，b.删除元素O(1)
Iterator.remove()	O(n - index)	O(1) <--- 优势
ListIterator.add(E element)	O(n - index)	O(1) <---优势

注：amortized：平摊代价，即每个操作的平均代价。

综上：
ArrayList对于元素的读取效率很高，因为ArrayList允许随机的按索引（index）读取元素。（同Array特点）。但对于插入、删除的效率不高，原因是需要重新计算长度。
LinkedList对于元素的插入、删除效率比较高（双向链表的特点），但取特定的元素比较慢。

以下是来自programcreek.com 的效率对比：


因为ArrayList的高效率，总的来说平时我们都选用ArrayList。

b. 另外，ArrayList和LinkedList都是线程不安全的，如果想要得到一个线程安全的对象，可以使用Collections类的synchronizedList方法返回线程安全的对象：

List list = Collections.synchronizedList(new ArrayList(...));
//或
List list = Collections.synchronizedList(new LinkedList(...));

c. List排序
可以使用工具类java.util.Collections提供的方法：

public static <T> void sort(List<T> list, Comparator<? super T> c)

public void sortTest() {
	List<String> list = new ArrayList<String>();
		
	list.add("aaa");
	list.add("ccc");
	list.add("bbb");
	System.out.println(list); // [aaa, ccc, bbb]
		
	// 倒序排列
	Collections.sort(list, new Comparator<String>(){
		@Override
		public int compare(String arg0, String arg1) {
			return -arg0.compareTo(arg1);
		}
	});

	System.out.println(list); // [ccc, bbb, aaa]
}

-------------------------------------------
参考：
http://docs.oracle.com/javase/6/docs/api/java/util/List.html
http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List,%20java.util.Comparator)
http://www.programcreek.com
http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist