java.util.List接口是Java Collections Framework的一個重要組成部分，List接口的架構圖如下：
本文將通過剖析List接口的三個實現類——ArrayList、LinkedList和Vector的源碼，帶你走近List的世界。
ArrayList是List接口可調整數組大小的實現。實現所有可選列表操作，并允許放入包括空值在內的所有元素。每個ArrayList都有一個容量（capacity,區別于size），表示底層數組的實際大小，容器內存儲元素的個數不能多于當前容量。
java.util.ArrayList類的繼承關系如下：
public?class?ArrayList<E>?extends?AbstractList<E>?implements?List<E>,?RandomAccess,?Cloneable,?java.io.Serializable
其中需要注意的是RandomAccess接口，這是一個標記接口，沒有定義任何具體的內容，該接口的意義是隨機存取數據。在該接口的注釋中有這樣一段話：
/**?for?(int?i=0,?n=list.size();?i?<?n;?i++)?{?list.get(i);?}?runs?faster?than?this?loop:?for?(Iterator?i=list.iterator();?i.hasNext();?)?{?i.next();?}?**/這說明在數據量很大的情況下，采用迭代器遍歷實現了該接口的集合，速度比較慢。
實現了RandomAccess接口的集合有：ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList,?Stack,?Vector等。
ArrayList一些重要的字段如下：
????private?static?final?int?DEFAULT_CAPACITY?=?10;
????private?static?final?Object[]?EMPTY_ELEMENTDATA?=?{};
????private?static?final?Object[]?DEFAULTCAPACITY_EMPTY_ELEMENTDATA?=?{};
????transient?Object[]?elementData;?//?non-private?to?simplify?nested?class?access????private?int?size;//底層數組中實際元素個數，區別于capacity可以看到，默認第一次插入元素時創建數組的大小為10。當向容器中添加元素時，如果容量不足，容器會自動增加50%的容量。增加容量的函數grow()源碼如下：
private?void?grow(int?minCapacity)?{
????????//?overflow-conscious?code????????int?oldCapacity?=?elementData.length;
????????int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1);//右移一位代表增加50%????????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);
????}
?private?static?int?hugeCapacity(int?minCapacity)?{
????????if?(minCapacity?<?0)?//?overflow????????????throw?new?OutOfMemoryError();
????????return?(minCapacity?>?MAX_ARRAY_SIZE)??
????????????Integer.MAX_VALUE?:
????????????MAX_ARRAY_SIZE;
????}值得注意的是，由于集合框架用到了編譯器提供的語法糖——泛型，而Java泛型的內在實現是通過類型擦除和類型強制轉換來進行的，其實存儲的數據類型都是Raw Type，因此集合框架的底層數組都是Object數組，可以容納任何對象。
ArrayList的實現中大量地調用了Arrays.copyof()和System.arraycopy()方法。在此介紹一下這兩個方法。
System.arraycopy()方法是一個native方法，調用了系統的C/C++代碼，在openJDK中可以看到其源碼。該方法最終調用了C語言的memmove()函數，因此它可以保證同一個數組內元素的正確復制和移動，比一般的復制方法的實現效率要高很多，很適合用來批量處理數組。Java強烈推薦在復制大量數組元素時使用該方法，以取得更高的效率。
Arrays.copyOf()方法有很多重載版本，但實現思路都是一樣的，其泛型版本源碼如下：
public?static?<T>?T[]?copyOf(T[]?original,?int?newLength)?{?return?(T[])?copyOf(original,?newLength,?original.getClass());?}其調用了copyof()方法：
public?static?<T,U>?T[]?copyOf(U[]?original,?int?newLength,?Class<??extends?T[]>?newType)?{??
????T[]?copy?=?((Object)newType?==?(Object)Object[].class)??
??????????(T[])?new?Object[newLength]??
????????:?(T[])?Array.newInstance(newType.getComponentType(),?newLength);??
????System.arraycopy(original,?0,?copy,?0,??
?????????????????????Math.min(original.length,?newLength));??
????return?copy;??}該方法實際上是在其內部創建了一個類型為newType、長度為newLength的新數組，調用System.arraycopy()方法，將原來數組中的元素復制到新的數組中。
ArrayList的實現是不同步的，如果多個線程同時訪問ArrayList實例，并且至少有一個線程修改list的結構，那么它就必須在外部進行同步。如果沒有這些對象， 這個list應該用Collections.synchronizedList()方法進行包裝。 最好在list的創建時就完成包裝，防止意外地非同步地訪問list:
List?list?=?Collections.synchronizedList(new?ArrayList(...));
除了未實現同步之外，ArrayList大致相當于Vector。
size(),?isEmpty(),?get(),set()方法均能在常數時間內完成，add()方法的時間開銷跟插入位置有關(adding n elements requires O(n) time)，addAll()方法的時間開銷跟添加元素的個數成正比。其余方法大都是線性時間。
ArrayList常用的size(),?isEmpty(),?get(),set()方法實現都比較簡單，讀者可自行翻閱源碼，它們均能在常數時間內完成，性能很高，這也是數組實現的優勢所在。add()方法的時間開銷跟插入位置有關(adding n elements requires O(n) time)，addAll()方法的時間開銷跟添加元素的個數成正比。其余方法大都是線性時間。
public?boolean?add(E?e)?{
????????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!????????elementData[size++]?=?e;
????????return?true;}public?void?add(int?index,?E?element)?{
????????rangeCheckForAdd(index);
????????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!????????System.arraycopy(elementData,?index,?elementData,?index?+?1,
?????????????????????????size?-?index);
????????elementData[index]?=?element;
????????size++;}前者是在ArrayList尾部插入一個元素，后者是在指定位置插入元素。值得注意的是，將元素的索引賦給elementData[size]時可能會出現數組越界，這里的關鍵就在于ensureCapacity(size+1)的調用，這個方法的作用是確保數組的容量，它的源碼如下：
ensureCapacity()和ensureExplicitCapacity()方法：
public?void?ensureCapacity(int?minCapacity)?{
????????int?minExpand?=?(elementData?!=?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
????????????//?any?size?if?not?default?element?table??????????????0
????????????//?larger?than?default?for?default?empty?table.?It's?already????????????//?supposed?to?be?at?default?size.????????????:?DEFAULT_CAPACITY;
????????if?(minCapacity?>?minExpand)?{
????????????ensureExplicitCapacity(minCapacity);
????????}}private?void?ensureExplicitCapacity(int?minCapacity)?{
????????modCount++;
????????//?overflow-conscious?code????????if?(minCapacity?-?elementData.length?>?0)
????????????grow(minCapacity);}其中有一個重要的實例變量modCount，它是在AbstractList類中定義的，在使用迭代器遍歷的時候，用modCount來檢查列表中的元素是否發生結構性變化（列表元素數量發生改變）了，如果modCount值改變，則代表列表中元素發生了結構性變化。
前面說過，ArrayList是非線程安全的，modCount主要在多線程環境下進行安全檢查，防止一個線程正在迭代遍歷，另一個線程修改了這個列表的結構。如果在使用迭代器進行遍歷ArrayList的時候modCount值改變，則會報ConcurrentModificationException異常。
可以看出，直接在數組后面插入一個元素add(e)效率也很高，但是如果要按下標來插入元素，則需要調用System.arraycopy()方法來移動部分受影響的元素，這會導致性能低下，這也是使用數組實現的ArrayList的劣勢。
同理，remove()方法也會改變modCount的值，效率與按下標插入元素相似，在此不加贅述。
public?boolean?addAll(Collection<??extends?E>?c)?{
????????Object[]?a?=?c.toArray();
????????int?numNew?=?a.length;
????????ensureCapacityInternal(size?+?numNew);??//?Increments?modCount????????System.arraycopy(a,?0,?elementData,?size,?numNew);
????????size?+=?numNew;
????????return?numNew?!=?0;}public?boolean?addAll(int?index,?Collection<??extends?E>?c)?{
????????rangeCheckForAdd(index);
????????Object[]?a?=?c.toArray();
????????int?numNew?=?a.length;
????????ensureCapacityInternal(size?+?numNew);??//?Increments?modCount
????????int?numMoved?=?size?-?index;
????????if?(numMoved?>?0)
????????????System.arraycopy(elementData,?index,?elementData,?index?+?numNew,
?????????????????????????????numMoved);
????????System.arraycopy(a,?0,?elementData,?index,?numNew);
????????size?+=?numNew;
????????return?numNew?!=?0;}addAll方法也分在末尾插入和在指定位置插入，先將入參中的集合c轉換成數組，根據轉換后數組的程度和ArrayList的size拓展容量，之后調用System.arraycopy()方法復制元素到相應位置，調整size。根據返回的內容分析，只要集合c的大小不為空，即轉換后的數組長度不為0則返回true。
容易看出，addAll()方法的時間開銷是跟添加元素的個數成正比的。
下面來看一個簡單但是很有用的方法trimToSize()。
public?void?trimToSize()?{
????????modCount++;
????????if?(size?<?elementData.length)?{
????????????elementData?=?(size?==?0)
????????????????EMPTY_ELEMENTDATA
??????????????:?Arrays.copyOf(elementData,?size);
????????}}由于elementData的長度會被拓展，size標記的是其中包含的元素的個數。所以會出現size很小但elementData.length很大的情況，將出現空間的浪費。trimToSize()將返回一個新的數組給elementData，元素內容保持不變，length和size相同，節省空間。
在實際應用中，考慮這樣一種情形，當某個應用需要，一個ArrayList擴容到比如size=10000，之后經過一系列remove操作size=15，在后面的很長一段時間內這個ArrayList的size一直保持在<100以內，那么就造成了很大的空間浪費，這時候建議顯式調用一下trimToSize()方法，以優化一下內存空間。 或者在一個ArrayList中的容量已經固定，但是由于之前每次擴容都擴充50%，所以有一定的空間浪費，可以調用trimToSize()消除這些空間上的浪費。
LinkedList與ArrayList一樣也實現了List接口，LinkedList使用雙向鏈表實現，允許存儲元素重復，鏈表與ArrayList的數組實現相比，在進行插入和刪除操作時效率更高，但查找操作效率更低，因此在實際使用中應根據自己的程序計算需求來從二者中取舍。
與ArrayList一樣，LinkedList也是非線程安全的。
java.util.LinkedList的繼承關系如下：
publicclassLinkedList<E>extendsAbstractSequentialList<E>implementsList<E>,Deque<E>,Cloneable,java.io.Serializable
LinkedList繼承自抽象類AbstractSequenceList，其實AbstractSequenceList已經實現了List接口，這里標注出List只是更加清晰而已。AbstractSequenceList提供了List接口骨干性的實現以減少從而減少了實現受“連續訪問”數據存儲（如鏈表）支持的此接口所需的工作。對于隨機訪問數據（如數組），則應該優先使用抽象類AbstractList。
可以看到，LinkedList除了實現了List接口外，還實現了Deque接口，Deque即“Double Ended Queue”，是可以在兩端插入和移動數據的線性數據結構，我們熟知的棧和隊列皆可以通過實現Deque接口來實現。因此在LinkedList的實現中，除了提供了列表相關的方法如add()、remove()等，還提供了棧和隊列的pop()、peek()、poll()、offer()等相關方法。這些方法中有些彼此之間只是名稱的區別，內部實現完全相同，以使得這些名字在特定的上下文中顯得更加的合適。
LinkedList定義的字段如下：
transientintsize=0;transientNode<E>first;transientNode<E>last;
Size代表的是鏈表中存儲的元素個數，而first和last分別代表鏈表的頭節點和尾節點。 其中Node是LinkedList定義的靜態內部類：
private?static?class?Node<E>?{
????E?item;
????Node<E>?next
????Node<E>?prev;
????Node(Node<E>?prev,?E?element,?Node<E>?next)?{
????????this.item?=?element;
????????this.next?=?next;
????????this.prev?=?prev;
????}}Node是鏈表的節點類，其中的三個屬性item、next、prev分別代表了節點的存儲屬性值、前繼節點和后繼節點。
public?boolean?add(E?e)?{
????????linkLast(e);
????????return?true;}void?linkLast(E?e)?{
????final?Node<E>?l?=?last;
????final?Node<E>?newNode?=?new?Node<>(l,?e,?null);
????last?=?newNode;
????if?(l?==?null)
????????first?=?newNode;
????else
????????l.next?=?newNode;
????size++;
????????modCount++;}由上述代碼可見，LinkedList在表尾添加元素，只要直接修改相關節點的前后繼節點信息，而無需移動其他元素的位置，因此執行添加操作時效率很高。此外，LinkedList也是非線程安全的
public?boolean?remove(Object?o)?{
????if?(o?==?null)?{
????????for?(Node<E>?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????if?(x.item?==?null)?{
????????????????unlink(x);
????????????????return?true;
????????????}
????????}
????}?else?{
????????for?(Node<E>?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????if?(o.equals(x.item))?{
????????????????unlink(x);
????????????????return?true;
????????????}
????????}
????}
????return?false;}E?unlink(Node<E>?x)?{
????//?assert?x?!=?null;????final?E?element?=?x.item;
????final?Node<E>?next?=?x.next;
????final?Node<E>?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;}與add方法一樣，remove方法的底層實現也無需移動列表里其他元素的位置，而只需要修改被刪除節點及其前后節點的prev與next屬性即可。
該方法可以返回指定位置的元素，下面來看一看代碼
public?E?get(int?index)?{
????checkElementIndex(index);
????return?node(index).item;}Node<E>?node(int?index)?{
????//?assert?isElementIndex(index);
????if?(index?<?(size?>>?1))?{
????????Node<E>?x?=?first;
????????for?(int?i?=?0;?i?<?index;?i++)
????????????x?=?x.next;
????????return?x;
????}?else?{
????????Node<E>?x?=?last;
????????for?(int?i?=?size?-?1;?i?>?index;?i--)
????????????x?=?x.prev;
????????return?x;
????}}可以看到，LinkedList要想找到index對應位置的元素，必須要遍歷整個列表，在源碼實現中已經使用了二分查找（size >> 1即是除以2）的方法來進行優化，但查找元素的開銷依然很大，并且與查找的位置有關。相比較ArrayList的常數級時間的消耗而言，差距很大。
public?void?clear()?{
????//?Clearing?all?of?the?links?between?nodes?is?"unnecessary",?but:????//?-?helps?a?generational?GC?if?the?discarded?nodes?inhabit????//?more?than?one?generation????//?-?is?sure?to?free?memory?even?if?there?is?a?reachable?Iterator????for?(Node<E>?x?=?first;?x?!=?null;?)?{
????????Node<E>?next?=?x.next;
????????x.item?=?null;
????????x.next?=?null;
????????x.prev?=?null;
????????x?=?next;
????}
????first?=?last?=?null;
????size?=?0;
????modCount++;}該方法并不復雜，作用只是遍歷列表，清空表中的元素和節點連接而已。之所以單獨拿出來講，是基于GC方面的考慮，源碼注釋中講道，該方法中將所有節點之間的“連接”都斷開并不是必要的，但是由于鏈表中的不同節點可能位于分代GC的不同年代中，如果它們互相引用會給GC帶來一些額外的麻煩，因此執行此方法斷開節點間的相互引用，可以幫助分代GC在這種情況下提高性能。
作為伴隨JDK早期誕生的容器，Vector現在基本已經被棄用，不過依然有一些老版本的代碼使用到它，因此也有必要做一些了解。Vector與ArrayList的實現基本相同，它們底層都是基于Object數組實現的，兩者最大的區別在于ArrayList是非線程安全的，而Vector是線程安全的。由于Vector與ArrayList的實現非常相近，前面對于ArrayList已經進行過詳細介紹了，這里很多東西就不在贅述，重點介紹Vector與ArrayList的不同之處。
Vector與ArrayList還有一處細節上的不同，那就是Vector進行添加操作時，如果列表容量不夠需要擴容，每次增加的大小是原來的100%，而前面已經講過，ArrayList一次只增加原有容量的50%。具體代碼如下：
private?void?grow(int?minCapacity)?{
????//?overflow-conscious?code????int?oldCapacity?=?elementData.length;
????int?newCapacity?=?oldCapacity?+?((capacityIncrement?>?0)??
?capacityIncrement?:?oldCapacity);
????if?(newCapacity?-?minCapacity?<?0)
????????newCapacity?=?minCapacity;
????if?(newCapacity?-?MAX_ARRAY_SIZE?>?0)
????????newCapacity?=?hugeCapacity(minCapacity);
????elementData?=?Arrays.copyOf(elementData,?newCapacity);}Vector類內部的大部分方法與ArrayList均相同，區別僅在于加上了synchronized關鍵字，比如：
public?synchronized?void?trimToSize()?{
????modCount++;
????int?oldCapacity?=?elementData.length;
????if?(elementCount?<?oldCapacity)?{
????????elementData?=?Arrays.copyOf(elementData,?elementCount);
????}}這也保證了同一時刻只有一個線程能夠寫Vector，避免多線程同時寫而引起的不一致性，但實現同步需要很高的花費，因此，訪問Vector比訪問ArrayList要慢。
前面說過，由于性能和一些設計問題，Vector現在基本已被棄用，當涉及到線程安全時，可以如前文介紹ArrayList時所說的，對ArrayList進行簡單包裝，即可實現同步。
Vector還有一個子類叫Stack，其實現了棧的基本操作。這也是在JDK早期出現的容器，很多設計不夠規范，現在已經過時，使用Queue接口的相關實現可以完全取代它。
ArrayList是最常用的List實現類，內部是通過數組實現的，它允許對元素進行快速隨機訪問。數組的缺點是每個元素之間不能有間隔，當數組大小不滿足時需要增加存儲能力，就要講已經有數組的數據復制到新的存儲空間中。當從ArrayList的中間位置插入或者刪除元素時，需要對數組進行復制、移動、代價比較高。因此，它適合隨機查找和遍歷，不適合插入和刪除。
LinkedList是用鏈表結構存儲數據的，很適合數據的動態插入和刪除，隨機訪問和遍歷速度比較慢。另外，他還提供了List接口中沒有定義的方法，專門用于操作表頭和表尾元素，可以當作堆棧、隊列和雙向隊列使用。
Vector與ArrayList一樣，也是通過數組實現的，不同的是它支持線程的同步，即某一時刻只有一個線程能夠寫Vector，避免多線程同時寫而引起的不一致性，但實現同步需要很高的花費，因此，訪問它比訪問ArrayList慢，現在基本已棄用。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
