前面 LZ 已經(jīng)充分介紹了有關于 List 接口的大部分知識，如 ArrayList、LinkedList、Vector、Stack，通過這幾個知識點可以對 List 接口有了比較深的了解了。只有通過歸納總結的知識才是你的知識。所以下面 LZ 就 List 接口做一個總結。推薦閱讀：
List 接口，成為有序的 Collection 也就是序列。該接口可以對列表中的每一個元素的插入位置進行精確的控制，同時用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素。 下圖是 List 接口的框架圖：
http://wiki.jikexueyuan.com/project/java-enhancement/images/32-1.png" alt="fig.1" />
通過上面的框架圖，可以對 List 的結構了然于心，其各個類、接口如下：
Collection：Collection 層次結構 中的根接口。它表示一組對象，這些對象也稱為 collection 的元素。對于 Collection 而言，它不提供任何直接的實現(xiàn)，所有的實現(xiàn)全部由它的子類負責。
AbstractCollection：提供 Collection 接口的骨干實現(xiàn)，以最大限度地減少了實現(xiàn)此接口所需的工作。對于我們而言要實現(xiàn)一個不可修改的 collection，只需擴展此類，并提供 iterator 和 size 方法的實現(xiàn)。但要實現(xiàn)可修改的 collection，就必須另外重寫此類的 add 方法（否則，會拋出 UnsupportedOperationException），iterator 方法返回的迭代器還必須另外實現(xiàn)其 remove 方法。
Iterator：迭代器。
ListIterator：系列表迭代器，允許程序員按任一方向遍歷列表、迭代期間修改列表，并獲得迭代器在列表中的當前位置。
List：繼承于 Collection 的接口。它代表著有序的隊列。
AbstractList：List 接口的骨干實現(xiàn)，以最大限度地減少實現(xiàn)“隨機訪問”數(shù)據(jù)存儲（如數(shù)組）支持的該接口所需的工作。
Queue：隊列。提供隊列基本的插入、獲取、檢查操作。
Deque：一個線性 collection，支持在兩端插入和移除元素。大多數(shù) Deque 實現(xiàn)對于它們能夠包含的元素數(shù)沒有固定限制，但此接口既支持有容量限制的雙端隊列，也支持沒有固定大小限制的雙端隊列。
AbstractSequentialList：提供了 List 接口的骨干實現(xiàn)，從而最大限度地減少了實現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲（如鏈接列表）支持的此接口所需的工作。從某種意義上說，此類與在列表的列表迭代器上實現(xiàn)“隨機訪問”方法。
LinkedList：List 接口的鏈接列表實現(xiàn)。它實現(xiàn)所有可選的列表操作。
ArrayList：List 接口的大小可變數(shù)組的實現(xiàn)。它實現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素。除了實現(xiàn) List 接口外，此類還提供一些方法來操作內(nèi)部用來存儲列表的數(shù)組的大小。
Vector：實現(xiàn)可增長的對象數(shù)組。與數(shù)組一樣，它包含可以使用整數(shù)索引進行訪問的組件。
Stack：后進先出（LIFO）的對象堆棧。它通過五個操作對類 Vector 進行了擴展 ，允許將向量視為堆棧。
Enumeration：枚舉，實現(xiàn)了該接口的對象，它生成一系列元素，一次生成一個。連續(xù)調(diào)用 nextElement 方法將返回一系列的連續(xù)元素。
http://wiki.jikexueyuan.com/project/java-enhancement/images/32-2.png" alt="fig.2" />
學習知識的根本目的就是使用它。每個知識點都有它的使用范圍。集合也是如此，在 Java 中集合的家族非常龐大，每個成員都有最適合的使用場景。在剛剛接觸 List 時，LZ 就說過如果涉及到“?！?、“隊列”、“鏈表”等操作，請優(yōu)先考慮用 List。至于是那個 List 則分如下：
1、對于需要快速插入、刪除元素，則需使用 LinkedList。
2、對于需要快速訪問元素，則需使用 ArrayList。
3、對于“單線程環(huán)境”或者“多線程環(huán)境，但是 List 僅被一個線程操作”，需要考慮使用非同步的類，如果是“多線程環(huán)境，切 List 可能同時被多個線程操作”，考慮使用同步的類（如Vector）。
在 List 中我們使用最普遍的就是 LinkedList 和 ArrayList，同時我們也了解了他們兩者之間的使用場景和區(qū)別。
public class ListTest {
private static final int COUNT = 100000;
private static ArrayList arrayList = new ArrayList<>();
private static LinkedList linkedList = new LinkedList<>();
private static Vector vector = new Vector<>();
public static void insertToList(List list){
long startTime = System.currentTimeMillis();
for(int i = 0 ; i < COUNT ; i++){
list.add(0,i);
}
long endTime = System.currentTimeMillis();
System.out.println("插入 " + COUNT + "元素" + getName(list) + "花費 " + (endTime - startTime) + " 毫秒");
}
public static void deleteFromList(List list){
long startTime = System.currentTimeMillis();
for(int i = 0 ; i < COUNT ; i++){
list.remove(0);
}
long endTime = System.currentTimeMillis();
System.out.println("刪除" + COUNT + "元素" + getName(list) + "花費 " + (endTime - startTime) + " 毫秒");
}
public static void readList(List list){
long startTime = System.currentTimeMillis();
for(int i = 0 ; i < COUNT ; i++){
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("讀取" + COUNT + "元素" + getName(list) + "花費 " + (endTime - startTime) + " 毫秒");
}
private static String getName(List list) {
String name = "";
if(list instanceof ArrayList){
name = "ArrayList";
}
else if(list instanceof LinkedList){
name = "LinkedList";
}
else if(list instanceof Vector){
name = "Vector";
}
return name;
}
public static void main(String[] args) {
insertToList(arrayList);
insertToList(linkedList);
insertToList(vector);
System.out.println("--------------------------------------");
readList(arrayList);
readList(linkedList);
readList(vector);
System.out.println("--------------------------------------");
deleteFromList(arrayList);
deleteFromList(linkedList);
deleteFromList(vector);
}
}
運行結果:
插入 100000元素ArrayList花費 3900 毫秒
插入 100000元素LinkedList花費 15 毫秒
插入 100000元素Vector花費 3933 毫秒
--------------------------------------
讀取100000元素ArrayList花費 0 毫秒
讀取100000元素LinkedList花費 8877 毫秒
讀取100000元素Vector花費 16 毫秒
--------------------------------------
刪除100000元素ArrayList花費 4618 毫秒
刪除100000元素LinkedList花費 16 毫秒
刪除100000元素Vector花費 4759 毫秒
從上面的運行結果我們可以清晰的看出 ArrayList、LinkedList、Vector 增加、刪除、遍歷的效率問題。下面我就插入方法 add(int index, E element),delete、get 方法各位如有興趣可以研究研究。
首先我們先看三者之間的源碼：
ArrayList
public void add(int index, E element) {
rangeCheckForAdd(index); //檢查是否index是否合法
ensureCapacityInternal(size + 1); //擴容操作
System.arraycopy(elementData, index, elementData, index + 1, size - index); //數(shù)組拷貝
elementData[index] = element; //插入
size++;
}
rangeCheckForAdd、ensureCapacityInternal 兩個方法沒有什么影響，真正產(chǎn)生影響的是 System.arraycopy 方法，該方法是個 JNI 函數(shù)，是在 JVM 中實現(xiàn)的。聲明如下：
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
目前 LZ 無法看到源碼，具體的實現(xiàn)不是很清楚，不過 System.arraycopy 源碼分析對其進行了比較清晰的分析。但事實上我們只需要了解該方法會移動 index 后面的所有元素即可，這就意味著 ArrayList 的 add(int index, E element) 方法會引起 index 位置之后所有元素的改變，這真是牽一處而動全身。
LinkedList
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) //插入位置在末尾
linkLast(element);
else
linkBefore(element, node(index));
}
該方法比較簡單，插入位置在末尾則調(diào)用 linkLast 方法，否則調(diào)用 linkBefore 方法，其實 linkLast、linkBefore 都是非常簡單的實現(xiàn)，就是在 index 位置插入元素，至于 index 具體為知則有 node 方法來解決，同時 node 對 index 位置檢索還有一個加速作用，如下：
Node<E> node(int index) {
if (index < (size >> 1)) { //如果index 小于 size/2 則從頭開始查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //如果index 大于 size/2 則從尾部開始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
所以 linkedList 的插入動作比 ArrayList 動作快就在于兩個方面。1：linkedList 不需要執(zhí)行元素拷貝動作，沒有牽一發(fā)而動全身的大動作。2:查找插入位置有加速動作即：若 index < 雙向鏈表長度的 1/2，則從前向后查找; 否則，從后向前查找。
Vector
Vector 的實現(xiàn)機制和 ArrayList 一樣，同樣是使用動態(tài)數(shù)組來實現(xiàn)的，所以他們兩者之間的效率差不多，add 的源碼也一樣，如下：
public void add(int index, E element) {
insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}
上面是針對 ArrayList、LinkedList、Vector 三者之間的 add（int index,E element) 方法的解釋，解釋了 LinkedList 的插入動作要比 ArrayList、Vector 的插入動作效率為什么要高出這么多！至于 delete、get 兩個方法 LZ 就不多解釋了。
同時 LZ 在寫上面那個例子時發(fā)現(xiàn)了一個非常有趣的現(xiàn)象，就是 linkedList 在某些時候執(zhí)行 add 方法時比 ArrayList 方法會更慢！至于在什么情況？為什么會慢 LZ 下篇博客解釋，當然不知道這個情況各位是否也遇到過？？
http://wiki.jikexueyuan.com/project/java-enhancement/images/32-3.png" alt="fig.3" />
掃碼關注鍍金池微信號
手機訂課，優(yōu)惠多多