在上一章《初探java集合框架圖》中，我相信大部分朋友對java容器整體架構都有了初步的瞭解，那麼本章主要是想詳細的介紹以下List接口實現類之間的區別！
01、List簡介
List 的數據結構就是一個序列，存儲內容時直接在內存中開闢一塊連續的空間，然後將空間地址與索引對應。
以下是List集合簡易架構圖
由圖中的繼承關係，可以知道，ArrayList、LinkedList、Vector、Stack都是List的四個實現類。
- AbstractCollection 是一個抽象類，它唯一實現Collection接口的類。AbstractCollection主要實現了toArray()、toArray(T[] a)、remove()等方法。
- AbstractList 也是一個抽象類，它繼承於AbstractCollection。AbstractList實現List接口中除size()、get(int location)之外的函數，比如特定迭代器ListIterator。
- AbstractSequentialList 是一個抽象類，它繼承於AbstractList。AbstractSequentialList 實現了“鏈表中，根據index索引值操作鏈表的全部函數”。
- ArrayList 是一個動態數組，它由數組實現。隨機訪問效率高，隨機插入、隨機刪除效率低。
- LinkedList 是一個雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率高。
- Vector 也是一個動態數組，和ArrayList一樣，也是由數組實現。但是ArrayList是非線程安全的，而Vector是線程安全的。
- Stack 是棧，它繼承於Vector。它的特性是：先進後出(FILO, First In Last Out)。
下面對各個實現類進行方法剖析！
02、ArrayList
ArrayList實現了List接口，也是順序容器，即元素存放的數據與放進去的順序相同，允許放入null元素，底層通過數組實現。 除該類未實現同步外，其餘跟Vector大致相同。
在Java1.5之後，集合還提供了泛型，泛型只是編譯器提供的語法糖，方便編程，對程序不會有實質的影響。因為所有的類都默認繼承至Object，所以這裡的數組是一個Object數組，以便能夠容納任何類型的對象。
常用方法介紹
2.1、get方法
get()方法同樣很簡單，先判斷傳入的下標是否越界，再獲取指定元素。
public E get(int index) { rangeCheck(index); return elementData(index);}/** * 檢查傳入的index是否越界 */private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}2.2、set方法
set()方法也非常簡單，直接對數組的指定位置賦值即可。
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue;}2.3、add方法
ArrayList添加元素有兩個方法，一個是add(E e)，另一個是add(int index, E e)。 這兩個方法都是向容器中添加新元素，可能會出現容量（capacity）不足，因此在添加元素之前，都需要進行剩餘空間檢查，如果需要則自動擴容。擴容操作最終是通過grow()方法完成的。
grow方法實現
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1);//原來的1.5倍 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);}添加元素還有另外一個addAll()方法，addAll()方法能夠一次添加多個元素，根據位置不同也有兩個方法，一個是在末尾添加的addAll(Collection extends E> c)方法，一個是從指定位置開始插入的addAll(int index, Collection extends E> c)方法。
不同點：addAll()的時間複雜度不僅跟插入元素的多少有關，也跟插入的位置相關，時間複雜度是線性增長！
2.4、remove方法
remove()方法也有兩個版本，一個是remove(int index)刪除指定位置的元素；另一個是remove(Object o)，通過o.equals(elementData[index])來刪除第一個滿足的元素。
需要將刪除點之後的元素向前移動一個位置。需要注意的是為了讓GC起作用，必須顯式的為最後一個位置賦null值。
- remove(int index)方法
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; //賦null值，方便GC回收 return oldValue;} - remove(Object o)方法
public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false;}03、LinkedList
在上篇文章中，我們知道LinkedList同時實現了List接口和Deque接口，也就是說它既可以看作一個順序容器，又可以看作一個隊列（Queue），同時又可以看作一個棧（Stack）。
LinkedList底層通過雙向鏈表實現，通過first和last引用分別指向鏈表的第一個和最後一個元素，注意這裡沒有所謂的啞元（某個參數如果在子程序或函數中沒有用到，那就被稱為啞元），當鏈表為空的時候first和last都指向null。
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable{ /**容量*/ transient int size = 0; /**鏈表第一個元素*/ transient Node first; /**鏈表最後一個元素*/ transient Node last;......} /** * 內部類Node */private static class Node { E item;//元素 Node next;//後繼 Node prev;//前驅 Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; }} 常用方法介紹
3.1、get方法
get()方法同樣很簡單，先判斷傳入的下標是否越界，再獲取指定元素。
public E get(int index) { checkElementIndex(index); return node(index).item;}/** * 檢查傳入的index是否越界 */private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));} 3.2、set方法
set(int index, E element)方法將指定下標處的元素修改成指定值，也是先通過node(int index)找到對應下表元素的引用，然後修改Node中item的值。
public E set(int index, E element) { checkElementIndex(index); Node x = node(index); E oldVal = x.item; x.item = element; return oldVal;} 3.3、add方法
同樣的，add()方法有兩方法，一個是add(E e)，另一個是add(int index, E element)。
- add(E e)方法
該方法在LinkedList的末尾插入元素，因為有last指向鏈表末尾，在末尾插入元素的花費是常數時間，只需要簡單修改幾個相關引用即可。
public boolean add(E e) { linkLast(e); return true;}/** * 添加元素 */void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null)//原來鏈表為空，這是插入的第一個元素 first = newNode; else l.next = newNode; size++; modCount++;} - add(int index, E element)方法
該方法是在指定下表處插入元素，需要先通過線性查找找到具體位置，然後修改相關引用完成插入操作。
具體分成兩步，1.先根據index找到要插入的位置；2.修改引用，完成插入操作。
public void add(int index, E element) { checkPositionIndex(index); if (index == size)//調用add方法，直接在末尾添加元素 linkLast(element); else//根據index找到要插入的位置 linkBefore(element, node(index));}/** * 插入位置 */void linkBefore(E e, Node succ) { // assert succ != null; final Node pred = succ.prev; final Node newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++;} 同樣的，添加元素還有另外一個addAll()方法，addAll()方法能夠一次添加多個元素，根據位置不同也有兩個方法，一個是在末尾添加的addAll(Collection extends E> c)方法，另一個是從指定位置開始插入的addAll(int index, Collection extends E> c)方法。
裡面也for循環添加元素，addAll()的時間複雜度不僅跟插入元素的多少有關，也跟插入的位置相關，時間複雜度是線性增長！
3.4、remove方法
同樣的，remove()方法也有兩個方法，一個是刪除指定下標處的元素remove(int index)，另一個是刪除跟指定元素相等的第一個元素remove(Object o)。
兩個刪除操作都是，1.先找到要刪除元素的引用；2.修改相關引用，完成刪除操作。
- remove(int index)方法
通過下表，找到對應的節點，然後將其刪除
public E remove(int index) { checkElementIndex(index); return unlink(node(index));}- remove(Object o)方法
通過equals判斷找到對應的節點，然後將其刪除
public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false;} 刪除操作都是通過unlink(Node
/** * 刪除一個Node節點方法 */E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node prev = x.prev;//刪除的是第一個元素 if (prev == null) { first = next; } else { prev.next = next; x.prev = null; }//刪除的是最後一個元素 if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element;} 04、Vector
Vector類屬於一個挽救的子類，早在jdk1.0的時候，就已經存在此類，但是到了jdk1.2之後重點強調了集合的概念，所以，先後定義了很多新的接口，比如ArrayList、LinkedList，但考慮到早期大部分已經習慣使用Vector類，所以，為了兼容性，java的設計者，就讓Vector多實現了一個List接口，這才將其保留下來。
在使用方面，Vector的get、set、add、remove方法實現，與ArrayList基本相同，不同的是Vector在方法上加了線程同步鎖synchronized，所以，執行效率方面，會比較慢！
4.1、get方法
public synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index);}4.2、set方法
public synchronized E set(int index, E element) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); elementData[index] = element; return oldValue;}4.3、add方法
public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true;}4.4、remove方法
public synchronized boolean removeElement(Object obj) { modCount++; int i = indexOf(obj); if (i >= 0) { removeElementAt(i); return true; } return false;}05、Stack
在 Java 中 Stack 類表示後進先出（LIFO）的對象堆棧。棧是一種非常常見的數據結構，它採用典型的先進後出的操作方式完成的；在現實生活中，手槍彈夾的子彈就是一個典型的後進先出的結構。
在使用方面，主要方法有push 、peek 、pop 。
5.1、push方法
push方法表示，向棧中添加元素
public E push(E item) { addElement(item); return item;}5.2、peek方法
peek方法表示，查看棧頂部的對象，但不從棧中移除它
public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1);}5.3、pop方法
pop方法表示，移除元素，並將要移除的元素方法
public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj;} 關於 Java 中 Stack 類，有很多的質疑聲，棧更適合用隊列結構來實現，這使得Stack在設計上不嚴謹，因此，官方推薦使用Deque下的類來是實現棧！
06、總結
- ArrayList(動態數組結構)，查詢快（隨意訪問或順序訪問），增刪慢，但在末尾插入，速度與LinkedList相差無幾！
- LinkedList（雙向鏈表結構），查詢慢，增刪快！
- Vector（動態數組結構），相比ArrayList都慢，被ArrayList替代，基本不在使用。優勢是線程安全（函數都是synchronized），如果需要在多線程下使用，推薦使用併發容器中的工具類來操作，效率高！
- Stack（棧結構）繼承於Vector，數據是先進後出，基本不在使用，如果要實現棧，推薦使用Deque下的ArrayDeque，效率比Stack高！
07、參考
1、JDK1.7&JDK1.8 源碼
2、CarpenterLee - Java集合分析
3、博客園 - 朽木 - ArrayList、LinkedList、Vector、Stack的比較
閱讀更多 科技伍小黑 的文章
