0. 概述
典型的資料結構中，對於“表”結構的定義是：在一維空間下元素按照某種邏輯結構進行線性連線排列的資料結構（一對一）。java中集合定義中所包括的陣列表（ArrayList）、連結串列（LinkedList）、各種佇列（Queue/Deque）、棧（Stack）等都滿足這樣的定義。本文及後續的幾篇文章中將介紹Java集合結構中關於List介面、Queue介面、Set介面下的重要實現類。注意，關於java.util.concurrent包下對於List介面、Queue介面和Set介面實現類的介紹，將在後續專門的文章進行介紹。
1. Java中List性質集合概述上圖中展示了Java中的java.util.List介面所涉及的部分重要介面和抽象類，以及java.util.List介面在java.util包中的具體實現類。其中以黃色表示的類就是本文將要介紹的java.util包中關於List介面的重要實現類，他們分別是java.util.ArrayList、java.util.LinkedList、java.util.Vector和java.util.Stack。其中Vector和Stack這兩個類是繼承關係（從上圖中就可以看出），他們從JDK1.0開始就被提供出來供開發人員使用，後來又被效能和設計都更好的其它類替換。例如從名字上就可以看出其功能特點是LIFO性質（後進先出）的Stack類，在其自身的文件中（JDK1.7+）已建議開發者優先使用效能更好的ArrayDeque作為替代方案（關於ArrayDeque本專題的後續文章中進行詳細介紹）。
但是本專題依然會介紹java.util.Vector類和java.util.Stack類，因為本專題主要是分析Java原始碼的設計思想，以便讀者將這些設計思想應用到實際的工作中，在本專題的後續文章中還會繼續討論java中的java.util.Set介面、java.util.Deque介面的構建體系。
2.java集合List定義中的重要介面意義要理解java.util包中關於java.util.List介面的重要實現類，就首先要搞清楚其上層和下層涉及的主要介面定義和它們定義的功能範圍，它們是：java.lang.Iterable介面、java.util.Collection介面、java.util.AbstractList抽象類和java.util.AbstractSequentialList抽象類：
2.1. java.lang.Iterable介面由上圖可知，本專題第一部分將介紹的List、Set、Queue性質的集合介面其上層都需要繼承java.lang.Iterable介面。根據該介面上自帶的註釋描述，實現該介面的類可以使用“for each”迴圈操作語句進行操作處理。但實際上該介面還提供了兩個操作方法（JDK 1.8+），forEach(Consumer<? super T> action) 方法和spliterator() 方法。forEach(Consumer<? super T> action) 方法的一般使用方式示例如下：
// 這裡建立一個LinkedList，並且使用forEach方法，“消費”其中每一個要素new LinkedList<>().forEach(item -> { // ...... 這裡對每個item元素進行消費});// 再舉一個例子，這裡的Lists是 google common工具包提供的一個List性質集合相關的處理包Lists.newArrayList("value1","value2","value3","value4").forEach(item -> { // ...... 這裡對每個item元素進行消費});123456789forEach中的Consumer介面定義在java.util.function包下，這個包是JDK1.8中提供的，裡面包括了大量函數語言程式設計功能，java.util.function.Consumer介面就是其中之一：表示消費某個物件。
2.2. java.util.Spliterator介面java.lang.Iterable介面中的另一個方法spliterator()，實際上它是“並行迭代器”的定義介面。要說明這個在JDK1.8中提供的“並行迭代器”介面，就要先大致介紹在JDK1.2版本中提供的一個“順序迭代器” java.util.Iterator（請注意Iterator介面和Iterable介面在字面上的區別）介面。
所謂“順序迭代器”是可以將集合中的元素基於一定的順序規則，一個接一個的進行遍歷處理。其處理過程基於單核單執行緒；而“並行迭代器”可以將集合中的元素進行拆解後把他們同時交給多個執行緒進行處理——也就是說基於多核多執行緒處理。實際上其內部處理原理涉及到Java同樣在JDK1.8開始提供的Fork/Join框架。
2.3. java.util.Collection介面該介面是一個非常關鍵的介面，如果讀者仔細觀察java.util包中的原始碼結構，就會發現該介面並沒有一個直接的實現類。凡是實現了該介面的下級類或者介面，都屬於Java Collections Framework（Java集合框架）的一部分。
凡是實現了java.util.Collection介面的操作類，代表著這個類中可以按照某種邏輯結構和物理結構，“線性關聯”的儲存著一組元素的集合。這種線性關聯的邏輯結構可能是連結串列（例如：LinkedList），也可能是固定長度的陣列（例如：Vector）；可能向外界的輸出的結果是有序的（例如：ArrayList），也可能是無序的（例如：HashSet）；可能是保證了多執行緒下的操作安全性的（例如：CopyOnWriteArrayList），也可能是不保證多執行緒下的操作安全性的（例如：ArrayDeque）；
2.4. java.util.AbstractList抽象類讀者一定要知道，在Java中根據List性質的集合在各個維度上表現出來的工作特點，這些List結合可以被分成三種類型：是否支援隨機訪問的特點進行分類、按照是否具有可修改許可權進行分類、按照大小是否可變進行分類
Java中List性質的集合，根據是否支援隨機訪問的特點進行分類的話，當然就包括兩種型別：支援隨機訪問（讀）的集合和不支援隨機訪問（讀）的集合。所謂支援隨機訪問集合，就是指集合提供相關功能可以對List集合中任意位置的元素進行時間複雜度不改變的定位操作。
請注意Java中為List定義的“隨機訪問”的意義和磁碟IO上的“隨機讀”是有區別的（也有相似性），雖然兩者都是在說“可以在某個指定的獨立位置讀取資料”這個事情，但是由於機械磁碟“旋轉”的定位方式或者由於固態磁碟的垃圾標記/回收機制，所以磁碟IO讀寫中的“隨機讀”效能是要顯著慢於磁碟IO讀寫中的“順序讀”的；List中定義的“隨機訪問”需要從演算法的“時間複雜度”層面考慮，例如使用陣列結構作為List集合基本結構時，其找到一個“指定”位置的時間複雜度為常量O(1)——因為可以直接定位到指定的記憶體起始位置，並透過偏移量進行最終定位。所以List性質的集合中定義的支援“隨機訪問”的集合結構，在資料讀取效能上遠遠優於那些不支援“隨機訪問”的List集合——後續內容介紹ArrayList和LinkedList時，還會詳細講解。
另外，如果將List集合按照是否具有可修改許可權進行分類，那麼List集合分為可修改集合和不可修改集合。所謂可修改集合是指操作者可以在集合指定的索引位置指定一個儲存值；所謂不可修改集合既是操作者只能獲取集合指定索引位置的儲存值，但是並不能對這個索引位置的值進行替換，使用者也可以獲取當前集合的大小，且這個大小的值一定是不可改變的。
最後，如果將List性質的集合按照大小是否可變進行分類，那麼List集合分為大小可變集合和大小不可變集合，所謂大小不可變集合，既是說一旦這個集合完成了例項化，那麼大小就一直固定下來不再變化，而大小可變集合的定義則剛好相反。
針對這三個維度的不同型別定義，開發人員就可以定義出不同操作特性的List集合。為了保證具有不同分類特點的List集合提供的操作方法符合規範性，也為了減少開發人員針對這些不同分類的List集合的開發工作量，還為了向使用者遮蔽這些分類定義的細節差異，Java為List性質的集合提供了java.util.AbstractList抽象類。
這樣保證了各種具體的List集合的實現類中只需要按照自身情況重寫java.util.AbstractList抽象類中的不同方法即可。例如，set(int) 方法其工作特點一定是替換指定索引位的元素值，如果當前List性質的集合不支援修改，則一定會丟擲UnsupportedOperationException異常；再例如，具有不可修改性質的List集合，開發人員只需要重寫java.util.AbstractList抽象類中的 get(int) 和 size() 方法即可；如果開發人員自行定義一個支援可變大小性質的集合，則只需要重寫對add(int , E) 方法和 remove(int) 方法的實現；最後再舉例，如果開發人員不需要實現支援隨機訪問的List集合，則可以優先繼承java.util.AbstractSequentialList抽象類。
2.5. java.util.RandomAccess介面java.util.RandomAccess介面是一個標識介面，所謂標識介面是Java中用來定義擁有某一種操作特性、功能特性的方式。Java中有很多標識介面，例如：java.lang.Cloneable介面、java.io.Serializable介面。
上文已經提到，List性質的集合中專門有一組集合實現類是支援“隨機訪問”特性的，包括java.util.ArrayList、java.util.Vector和java.util.concurrent.CopyOnWriteArrayList集合。java.util.RandomAccess標識介面就是為了向呼叫者表示這些List性質的集合實現類支援集合元素的隨機訪問。如下圖所示：
從上圖可以看出，List性質的集合java.util.ArrayList、java.util.Vector和java.util.concurrent.CopyOnWriteArrayList，都實現了這個java.util.RandomAccess標識介面，表示自己支援隨機訪問（讀）操作。實現java.util.RandomAccess標識介面的還有很多第三方類庫，例如上圖中舉例就是阿里巴巴開源的JSON分析元件中的JSONArray類。這些實現了java.util.RandomAccess標識介面的List集合在使用時也會被區別對待，如下所示：
/** * Replaces all of the elements of the specified list with the specified * element. <p> * This method runs in linear time. * @param <T> the class of the objects in the list * @param list the list to be filled with the specified element. * @param obj The element with which to fill the specified list. * @throws UnsupportedOperationException if the specified list or its * list-iterator does not support the <tt>set</tt> operation. */public static <T> void fill(List<? super T> list, T obj) { int size = list.size(); // 如果當前集合的大小規模小於FILL_THRESHOLD （25），或者當前List集合支援“隨機訪問” // 那麼優先使用索引定位的方式替換集合中的每個位置的物件引用 if (size < FILL_THRESHOLD || list instanceof RandomAccess) { for (int i=0; i<size; i++) list.set(i, obj); } // 否則使用 ListIterator順序迭代器一次尋找集合的每一個位置，並替換其中的物件引用 else { ListIterator<? super T> itr = list.listIterator(); for (int i=0; i<size; i++) { itr.next(); itr.set(obj); } }}123456789101112131415161718192021222324252627如上示例程式碼來源於java.util.Collections類的fill()方法，該方法主要用於向一個List性質集合填充預設的Object物件。在這個方法中如果當前給定的List性質的集合如果支援RandomAccess隨機訪問特性，則優先使用for()迴圈的方式定位並填充集合中的每一個位置；如果當前給定的List性質集合不支援“隨機訪問”，則是用ListIterator迭代器順序定位和填充集合中的每一個位置。
為什麼會出現這種處理邏輯呢？我們來看看在List集合預設的上層抽象類java.util.AbstractList中的list.listIterator()方法返回的ListIterator迭代器是如何實現next()方法的。
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { // ...... // Collections類的fill()方法，就是呼叫的該方法 public ListIterator<E> listIterator() { return listIterator(0); } public ListIterator<E> listIterator(final int index) { rangeCheckForAdd(index); return new ListItr(index); } // ...... // AbstractList類中並不會實現get()方法，而是將該方法的實現交給具體的實現類。 // 也就是說不同的實現類中會有不同的get()方法的實現過程。 abstract public E get(int index); // ...... // ListItr類是Itr的子類，next()方法就是在後者中進行定義的 private class Itr implements Iterator<E> { // ...... // next方法的呼叫過程在這裡 public E next() { checkForComodification(); try { // 關於cursor變數和lastRet 變數在迭代器中的意義 // 在後文會進行介紹，這裡我們主要關注本方法內容中的get()方法。 int i = cursor; E next = get(i); lastRet = i; cursor = i + 1; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } // ...... }}1234567891011121314151617181920212223242526272829303132333435363738在AbstractList.Itr類的next()方法中，我們主要關注其中的get()方法。並且在上面的程式碼片段上已經說明，不同實現原理下的具體List集合類對於get()方法的實現是不一樣的，那麼我們來看一下兩個典型的List集合ArrayList和LinkedList對於get()方法的實現。
首先來看一下LinkedList中對於get()方法的實現：public E get(int index) { // 後續文章會說明checkElementIndex()方法，在本文中的內容中，它並不重要 checkElementIndex(index); return node(index).item;}Node<E> node(int index) { // 如果給定的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; }}123456789101112131415161718192021由於LinkedList是一個雙向連結串列，要尋找連結串列中的某一個位置上的元素，就只能從頭部或者從尾部一個一個的找。如下圖所示：
這樣我們就可以覆盤java.util.Collections類的fill()方法中，如何進行LinkedList中的元素填充了，如下圖所示：
然後我們再來看一下ArrayList中對於get()方法的實現：// ArrayLit類中的elementData變數就是這個集合的陣列形式表示transient Object[] elementData;public E get(int index) { // rangeCheck方法後文會進行講解，但和這裡講解的內容關聯不大 rangeCheck(index); // 透過elementData方法，直接定位陣列中的元素 // 保證了對“隨機訪問”特性的支援，對演算法複雜度O(1)的支援 return elementData(index);}E elementData(int index) { return (E) elementData[index];}1234567891011121314由於ArrayList本質上是一個數組，要尋找到陣列中的某一個位置上的元素並不用挨個元素意義進行遍歷。JVM會根據物件在記憶體中的起始位置和陣列位置的偏移量直接找到這個元素。按照這樣的原理，我們同樣可以覆盤java.util.Collections類的fill()方法中，如何進行ArrayList中的元素填充了，如下圖所示：
以上示例的分析中，本文將支援“隨機訪問”和不支援“隨機訪問”的具體List集合在訪問效能上的工作差異做了詳細標識，實際上典型的ArrayList和LinkedList的效能差別還不僅僅在於此處，後續文章還會做更詳細說明。另外，在本文第1小節給出的List整合體系簡圖中，還出現了java.util.Queue介面和java.util.Deque介面，這兩個介面代表Java集合體系中另外一塊和List集合體系平行的集合體系，在後續文章中也將進行詳細介紹。