List接口源碼詳解以及選型：ArrayList、LinkedList、Vector

List接口

List 是一個接口，繼承自 Collection 接口，其下方還有 ArrayList 、 LinkedList 、 Vertor 的實作類。

類圖可參考：文章《Collection》

本文将記錄 List 下實作類的源碼 debug 流程，以及源碼分析。

一、ArrayList

1. 簡介

在源碼的頭部注釋中寫道：實作自 List 接口，是一個可調整數組的實作，允許所有元素包括 null 的添加，除了實作 List 接口内的方法之外，還包含一些方法用于操作内部數組的大小。這個類是類似于 Vertor 的，但它是非同步的。當向内部添加元素的時候，它的容量可以自動增加。由于是非同步(非線程安全)的類，是以如果有多線程并發操作 ArrayList 執行個體，則可能會抛出 ConcurrentModificationException (并發修改異常)異常。

從以上内容中可以得知 ArrayList 有幾個特點：

Object
null
Vector
           

2. 類核心屬性

• elementData 存放資料的
• transient Object[] elementData; 複制代碼
• transient 修飾，代表不可以被序列化
• EMPTY_ELEMENTDATA
• private static final Object[] EMPTY_ELEMENTDATA = {}; 複制代碼
• 用空執行個體的共享空數組執行個體。
• DEFAULT_CAPACITY 初始化大小
• private static final int DEFAULT_CAPACITY = 10; 複制代碼
• 預設初始容量
• DEFAULTCAPACITY_EMPTY_ELEMENTDATA 用作初始化的空數組
• private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 複制代碼
• elementData 預設值
• size 目前集合長度
• private int size; 複制代碼
• 集合長度
• modCount 用于記錄被修改的次數，來自父類： AbstractList
• protected transient int modCount = 0; 複制代碼
• MAX_ARRAY_SIZE 允許的集合最大長度
• private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 複制代碼
• 因為在數組類型屬于特殊的資料類型，在 JVM 中可能需要8個空間存儲 _length 資訊，不同的 JVM 平台可能不一樣，為了保險起見，才将最大長度進行 -8 處理。

3. 構造方法

ArrayList 有3個構造方法，分别為：

• ArrayList() 無參構造方法
• public ArrayList() { // 初始化一個空數組 就是将elementData初始化一下 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } 複制代碼
• ArrayList(int initialCapacity)
• public ArrayList(int initialCapacity) { // 如果傳入進來的初始化大小大于0，就建構一個指定長度的數組 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; // 如果長度等于0 就用預設的空數組 // EMPTY_ELEMENTDATA = {} } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; // else對應小于0 他看你不爽就抛個異常給你 告訴你值不合法 } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } 複制代碼
• ArrayList(Collection<? extends E> c)
• public ArrayList(Collection<? extends E> c) { // 先轉一下數組，如果傳了個null 他就給你個空指針 Object[] a = c.toArray(); // 有資料 if ((size = a.length) != 0) { // 是否是ArrayList類型的 if (c.getClass() == ArrayList.class) { // 是的話 直接指派 elementData = a; } else { // 不是的話 就複制 elementData = Arrays.copyOf(a, size, Object[].class); } } else { // replace with empty array. // 和無參構造方法一緻 初始化一個空數組 elementData = EMPTY_ELEMENTDATA; } } 複制代碼

4.add()方法

先說結論：當調用 ArrayList 的 add() 方法時

• 調用時，會首先調用判斷内部的 elementData 大小是否滿足目前元素的放入，如果不滿足的話，則會調用 grow() 方法進行數組的擴容，擴容時會計算新數組的長度，計算時分為兩種情況，第一次進入的時候原數組是個空的，是以會給一個預設的長度 10 ，第二次及以後進入，才會 * 1.5，來計算，得出新數組長度後會進行 Arrays.copyOf() 複制操作，将原數組指派給新數組，并初始化至 newCapacity 新的容量。

為什麼是 1.5 倍?

• 首先 1.5 是由( oldCapacity >> 1 計算得出)
• 因為 1.5 可以充分利用移位操作，減少浮點數或者運算時間和運算次數。
• 其次擴容 1.2 倍未免過于太小，而 2 倍又太大，在權衡之下就采用 1.5 倍的做法。

源碼：

第一步先看add(E e)方法

public boolean add(E e) {
  			// 确認内部大小是否可以滿足目前元素的放入，參數為目前數組長度+1(也就是存放目前元素後的數組長度)
        ensureCapacityInternal(size + 1); // Increments modCount!!
  			// 擴容完之後直接指派就好
        elementData[size++] = e;
  			// 傳回成功
        return true;
}
複制代碼           

第二步ensureCapacityInternal()方法

• 確定内部大小足夠
• 參數 minCapacity 為期望的最小容量

// minCapacity 為期望的最小容量
private void ensureCapacityInternal(int minCapacity) {
  			// 確定内部大小，會進行數組的擴容
  			// calculateCapacity() 方法，確定第一次進入是有長度的
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 計算最小容量，確定第一次進入是有長度的
// elementData 目前數組，minCapacity 最小期望容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  			// 如果數組等于空的， 備注：DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          	// 就給個預設大小  DEFAULT_CAPACITY = 10 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
  			// 如果不是空的，就傳回最小大小
        return minCapacity;
 }
複制代碼           

第三步ensureExplicitCapacity()方法

• 確定内部大小是足夠的，并會執行擴容操作

private void ensureExplicitCapacity(int minCapacity) {
   			// 記錄操作次數
        modCount++;

   			// 如果期望的最小容量 - 數組目前長度 > 0
   			// 翻譯一下就是我最少需要11個容量，數組現在有10個容量，那麼是不滿足我的需求的，是以需要執行grow()方法執行擴容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
 }
複制代碼           

第四步grow()方法

• 數組擴容,確定至少可以容納 minCapacity 個元素

private void grow(int minCapacity) {
        // 記錄目前容量
        int oldCapacity = elementData.length;
  			// 将目前容量位移1，相當于 oldCapacity / 2
  			// 使用位移操作，減少浮點和加減運算，使用位移操作更快
  			// 擷取新的容量，公式：目前容量 * 1.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
  			// 如果計算的最新容量 - 期望的容量小于0
  			// 檢查新的容量是否大于期望的最小容量，如果小于就是用最小容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
  			// 檢查新容量是否超出數組允許的最大容量
  			// MAX_ARRAY_SIZE = Integer.MAX_VALUE -8 
  			// 因為在不同平台的JVM虛拟機中，可能會有8個容量用于儲存頭部資訊(用于存儲__length字段)，為了相容是以規定為int最大值 - 8，以保證不會出現oom 
        if (newCapacity - MAX_ARRAY_SIZE > 0)
          	// 如果超出了允許的最大容量，就執行最大用量計算
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
  			// 最後将原有的資料，指派到新數組中去，在将指派好的數組指派給自身的elementData
        elementData = Arrays.copyOf(elementData, newCapacity);
}

// 在執行第一步的 elementData[size++] = e; 即可完成添加操作

複制代碼           

第四步的->hugeCapacity()方法

此處可能會抛出 OOM 異常

在方法 hugeCapacity(minCapacity) 内會判斷， minCapacity 是否小于0，但是一步一步的往上查找，發現， minCapacity 的值是 size + 1 ，那麼正常情況下了解，這個參數應該是不會小于0的，那為什麼要加這個判斷呢?

private static int hugeCapacity(int minCapacity) {
  			// 為什麼會小于0呢 ? 
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
  			// 如果期望的最小容量大于允許的最大容量，就傳回int最大值，否則傳回允許的最大容量
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}
複制代碼           

這個地方有兩個問題

• 1.為什麼最小容量會小于0
• 這個地方我思考了很久，剛開始我也不了解是為什麼，因為 size + 1 我覺得不可能是小于0的。
• 直到我在 stackoverflow 上找到了一篇文章這裡邊寫道，當有兩個超大長度的 ArrayList 執行 addAll() 方法時，會導緻 int 尺寸超出，進而導緻 minCapacity < 0 。
• int 溢出： int 型資料在二進制裡面是有固定位數的，當數字超過 int 資料時，二進制的最前面的位數也就是符号位會發生變化，是以就變成負數了。
• 參考文章位址：
• int 溢出：位址
• minCapacity < 1 解釋：位址
• **2. **為什麼明明最大容量是 Integer.MAX_VALUE - 8 ，這裡還要傳回 Integer.MAX_VALUE 呢？
• 我覺得吧：因為期望的最小容量已經大于允許的容量了，是以這個規則就已經被打破了，是以此時别無選擇了，隻能指定為是 Integer.MAX_VALUE ，總不能超過 Integer.MAX_VALUE 吧。

二、LinkedList

1. 簡介

LinkedList 是一個使用了雙向連結清單實作的一個資料結構，和 ArrayList 有着很大的差別，同時它也是一個線程不安全的集合，可能會抛出 ConcurrentModificationException 。

null
           

2. 類的核心屬性

• first 指向雙向連表的頭部節點
• transient Node<E> first; 複制代碼
• transient 修飾不需要被序列化
• last 指向雙向連表的尾部節點
• transient Node<E> last; 複制代碼
• transient 修飾不需要被序列化
• Node<E> 内部結構
• /** * 雙向連結清單的内部結構 */ private static class Node<E> { // 真正用于存儲資料的節點 E item; // 下一個結點的指針 // 如果該Node==last 則next==null Node<E> next; // 上一個節點的指針 // 如果該Node==first 則prev==null Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 複制代碼

3. 構造方法

LinkedList 共有2個構造方法

• LinkedList() 無參構造
• public LinkedList() { } 複制代碼
• LinkedList(Collection<? extends E> c) 指派構造
• 從指定的集合類中将值賦給自身的雙向連結清單中
• public LinkedList(Collection<? extends E> c) { this(); addAll(c); } 複制代碼

4. add() 方法

先說結論：當調用 LinkedList 的 add() 方法時：

預設會往雙向連結清單的尾部添加一個元素，等價于 addLast() 方法。如果 last 屬性等于 null 的話，則代表是第一次添加，此時将會把 first 屬性指派為添加的元素，否則就建立一個新節點，将 last 節點的 next 屬性指向這個建立的新節點，完成雙向連表的指派和連接配接操作。

源碼：

public boolean add(E e) {
  // 實際調用了linkLast()進行添加元素
  linkLast(e);
  return true;
}
複制代碼           

linkLast() 方法

• 意思為連接配接尾部的意思，将新節點連接配接到當時尾部的 next 屬性下

void linkLast(E e) {
  			// 先記錄一下目前尾部指針
        final Node<E> l = last;
  			// 建立一個新的節點，prev屬性為目前的尾部節點，這樣做的話就可以使連結清單連接配接起來了
        final Node<E> newNode = new Node<>(l, e, null);
  			// 将尾部指派給新節點
        last = newNode;
  			// 第一次調用add()方法 last肯定是空的
        if (l == null)
          	// 就将新節點指派給頭部節點
            first = newNode;
  			// 不是第一次添加
  			else
          	// 就将原有的last屬性内的下一個節點指向目前的新元素
            l.next = newNode;
  			// 修改長度 +1
        size++;
  			// 修改操作次數 +1 
        modCount++;
}
複制代碼           

注：看到這個方法有沒有想到，如果我添加一個null進來，頭部節點會被覆寫掉嗎？

答：并不會:x:，因為 null 隻是 Node 中 item 屬性的值，是以 l == null 并不成立，是以并不會被覆寫。:stuck_out_tongue_winking_eye:

5. add(index) 方法

• 将元素插入到指定 index 的位置，如果該位置有元素的話就将其右移。

源碼：

public void add(int index, E element) {
  			// 判斷一下有沒有這個下标，如果沒有的話就抛出IndexOutOfBoundsException異常
        checkPositionIndex(index);
				
  			// 如果插入的索引==元素長度的話(就相當于尾插)，就在尾部添加一個元素
        if (index == size)
            linkLast(element);
        else
          	// 就在指定元素的頭部添加目前元素
            linkBefore(element, node(index));
}

/**
 * 查找指定下标的元素，并傳回該元素的指針
 */
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;
   }
 }

複制代碼           

6. linkBefore() 方法

• 意思為往頭部插入元素，将内部 first 屬性指派給傳入元素
• 方法備注：将元素 e 插入到，一定不為空的元素 succ 之前

源碼：

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
  			// succ肯定不為空，記錄一下succ元素的前一個元素
        final Node<E> pred = succ.prev;
  			// 建立一個新元素，将succ的prev指派到新元素的prev，并将succ作為新元素的next
        final Node<E> newNode = new Node<>(pred, e, succ);
  			// 将succ的上一個元素指向 目前的新元素
        succ.prev = newNode;
  			// 如果是第一次添加
        if (pred == null)
          	// 直接将頭部指派給新元素
            first = newNode;
        else
            // 将前一個元素的next指向新元素
            pred.next = newNode;
   			// 修改長度 +1
        size++;
  			// 修改更新次數  +1 
        modCount++;
}
複制代碼           

7. 備注

在調用 iterator() 方法時，會首先去校驗，調用時記錄的 modCount 是否等于自身目前的 modCount ，如果不等于的話則會抛出并發修改異常 ConcurrentModificationException()

三、Vector

1. 簡介

Vector 是一個線程安全的集合類，你可以在使用 iterator() 方法時，調用其他修改的方法(會等待鎖釋放)，不會産生線程安全的問題，因為在 Vector 的實作方法内，基本的都被加上了 synchronzied 關鍵字修飾， iterator() 方法在執行的時候更是會鎖住類，其他方法執行的時候都會等待鎖的釋放。

• 線程安全的集合類
• 效率沒有 ArrayList 高，因為加了 synchronzied 關鍵字，會使線程同步，是以會影響效率。
• 底層使用 Object 數組進行實作

2. 和ArrayList的差別

• 底層的擴容機制不一樣， ArrayList 是擴容至自身的1.5倍，而 Vector 直接擴容至自身的2倍。
• 這麼做的原因可能是因為：本身就添加了 synchronzied ，導緻效率低，是以擴容的大一些，避免了多次擴容。提升一點性能。

3. add()方法

• 可以參考 ArrayList 的 add() 方法，除了擴容機制不一樣，其它基本一緻。

四、集合類選型

三種集合特性對比

• ArrayList (90%的應用場景，推薦指數：:star::star::star::star::star:)
• 随機查詢，随機修改快，可以通過索引下标直接選中
• 線程不安全，并發場景不同時修改同一對象
• 添加效率低，需要進行擴容，效率較低
• LinkedList (根據業務需求，進行靈活使用 推薦指數：:star::star::star:)
• 随機查詢，随機修改效率低，需要循環比對找到對應的 Node 才可以操作
• 增加删除較快，使用雙向連表實作，無需考慮擴容。
• 線程不安全，并發場景不同時修改同一對象
• Vector (多線程并發場景使用，并發場景推薦指數：:star::star::star::star::star:，其餘場景不推薦使用)
• synchronzied