ArrayList，LinkedList，Vector基本原理與實現

前言：這篇文章其實昨天整理好就了，但今天才貼出來兩個原因：一是最近在弄房子裝潢的事；二是Map集合看的頭大耗了很長時間〒〒（不過還是整理好了後面再貼）。關於List這塊大家把下面的看懂基本面試沒問題了。喜歡的話點贊就是對我最大的肯定哦ヾ(???)?"

先來首從你的全世界路過的ed吧

整體圖beginning：

ArrayList

ArrayList概述

ArrayList基於數組實現（動態數組），容量會自動在增長。

ArrayList不是線程安全的，只能在單線程下使用。

ArrayList實現了Serializable介面，支持序列化，能夠通過序列化傳輸；實現了RandomAccess介面，支持快速隨機訪問，實際上就是通過下標序號進行快速訪問；實現了Cloneable介面，能被克隆。

ArrayList的實現

對於ArrayList而言，它實現List介面、底層使用數組保存所有元素，實則對數組元素進行操作

（1）私有屬性

（注意：elementData存儲ArrayList內的元素，size表示它包含的元素的數量。）

transient關鍵字解釋：

Java的serialization提供了一種持久化對象實例的機制。當持久化對象時，可能有一個特殊的對象數據成員，我們不想用serialization機制來保存它。為了在一個特定對象的一個域上關閉serialization，可以在這個域前加上關鍵字transient（參考Java關鍵字transient）。ArrayList使用writeObject()實現手工序列化數組內的元素。

（2）構造方法

ArrayList提供了三種方式的構造器

（3）元素存儲add()

3.1、set(int index, E element)：用指定的元素替代此列表中指定位置上的元素，並返回以前位於該位置上的元素。

3.2、add(E e)：將指定的元素添加到此列表的尾部。

數組進行擴容時，會將老數組中的元素重新拷貝一份到新的數組中，每次數組容量的增長大約是其原容量的1.5倍。（這種操作的代價是很高的，因此在實際使用時，我們應該盡量避免數組容量的擴張，可以初始化ArrayList時預算大致的容量要求）。

• size的初始值為0

• 來看一下ensureCapacityInternal函數

注意：

A：第一次執行ensureCapacityInternal(int 1)函數，會把minCapacity修改為10傳入ensureExplicitCapacity函數，並進行數組擴容；第二次執行ensureCapacityInternal(int 2)，由於elementData不為{}，所以minCapacity不會變動；當minCapacity值大於elementData.length即add的值大於上一次擴容的的容量，此時需要grow進行第二次數組擴容

B： modCount 即為Iterator的基本原理與實現所提到的，每當對集合進行修改時，此值會遞增

• 進入grow函數

注意：

A：第一次進入grow()函數oldCapacity=0，所以newCapacity=0

B：Arrays.copyOf(elementData, newCapacity)：返回一個新的數組，函數中第二個變數指要建立的新的數組長度，如果新數組的長度超過原數組的長度，不足位補0。如果數據量很大，這條語句會經常被執行，會影響到效率。

3.3、add(int index, E element) ：將指定的元素插入此列表中的指定位置。如果當前位置有元素，則向右移動當前位於該位置的元素以及所有後續元素（將其索引加1）。

3.4、addAll(Collection

3.5、addAll(int index, Collection

（源碼省略）

（4）元素讀取get()

（5）元素讀取刪除remove()

ArrayList提供了根據下標或者指定對象兩種方式的刪除功能。如下：

1、remove(int index)：首先是檢查範圍，修改modCount，保留將要被移除的元素，將移除位置之後的元素向前挪動一個位置，將list末尾元素置空（null），返回被移除的元素。

2、remove(Object o) ：移除此列表中首次出現的指定元素（如果存在）。ArrayList中允許存放重複的元素

注意：

A：remove(Object o)中通過遍歷element尋找是否存在傳入對象，一旦找到就調用fastRemove移除對象。fastRemove跳過了判斷邊界的處理，因為找到元素就相當於確定了index不會超過邊界，而且fastRemove並不返回被移除的元素，原理與remove類似。

（6）調整數組容量ensureCapacity(int minCapacity)

ArrayList中存儲元素的代碼中，我們看到，每當向數組中添加元素時，都要去檢查添加後元素的個數是否會超出當前數組的長度，如果超出，數組將會進行擴容，以滿足添加數據的需求。數組擴容通過一個公開的方法ensureCapacity(int minCapacity)來實現。

在實際添加元素前，我們可以通過ensureCapacity定製其容量，減少擴容次數（數組進行擴容時，會將老數組中的元素重新拷貝一份到新的數組中，每次數組容量的增長大約是其原容量的1.5倍，代價很高），減少容量開銷。

（7）Fail-Fast機制

ArrayList也採用了快速失敗的機制，通過記錄modCount參數來實現。在面對並發的修改時，迭代器很快就會完全失敗。

（8）總結

重點：

• 注意三種構造方法，無參構造方法構造的ArrayList的容量默認為10，帶有Collection參數的構造方法，將Collection轉化為數組賦給ArrayList的實現數組elementData。

• 注意擴充方法ensureCapacity，ArrayList在每次增加元素（可能是1個，也可能是一組）時，都要調用該方法來確保足夠的容量。當容量不足以容納當前的元素個數時，就設置新的容量為舊的容量的1.5倍加1，如果設置後的新容量還不夠，則直接新容量設置為傳入的參數（也就是所需的容量）。而後用Arrays.copyof()方法將元素拷貝到新的數組。很耗時，所以一般在知道元素個數情況下使用ArrayList,否則推薦LinkedList。

• ArrayList的實現中大量地調用了Arrays.copyof()和System.arraycopy()方法，需深入。

• ArrayList基於數組實現，可以通過下標索引直接查找到指定位置的元素，因此查找效率高，但每次插入或刪除元素，就要大量地移動元素，插入刪除元素的效率低。

• 在查找給定元素索引值等的方法中，源碼都將該元素的值分為null和不為null兩種情況處理，ArrayList中允許元素為null。

LinkedList

LinkedList概述

LinkedList繼承於AbstractSequentialList的雙向鏈表，它也可以被當作堆棧、隊列或雙端隊列進行操作。

LinkedList實現 List 介面，可進行隊列操作。

LinkedList實現Deque 介面，可進行雙端隊列操作。

LinkedList實現Cloneable介面，能克隆。

LinkedList實現Serializable介面，可進行序列化操作。

LinkedList的實現

LinkedList底層的數據結構是基於雙向循環鏈表的，且頭結點中不存放數據（下兩圖均為網上截圖）

雙向循環鏈表由節點構成，節點實例保存業務數據，前一個節點的位置信息和後一個節點位置信息

（1）私有屬性

Node結點的代碼

（2）構造方法

（3）元素存儲add()

先看一個複雜的，承接上面的addAll(c)

3.1、addAll(Collection

跳轉到public boolean addAll(int index, Collection

核心演算法，其他的都大同小異，見下圖：

• 上圖中checkPositionIndex(index); 函數體：

• 上圖中node(index);函數體：

分析：

succ ：保存index處的節點。插入位置如果是size，則在頭結點前面插入，否則在獲取index處（index之前）的節點插入

pred： 獲取前一個節點，插入時需要修改這個節點的next引用

通過對succ，pred兩種情況的設置，我們分開來探討（注意此處pred！=null情況,因為此時pred==head，為第一次插入情況）

第一種情況：當index==size時

1.Node newNode = new Node(pred, e, null);

2.pred.next = newNode;

3.pred = newNode;

4.last = pred;

第二種情況：當index!=size時

1.Node newNode = new Node(pred, e, null);

2.pred.next = newNode;

3.pred = newNode;

4.pred.next = succ;

5.succ.prev = pred;

3.2、add(E e)：鏈表後面增加元素

在linkLast()方法中，首先會生成一個新的Node節點，然後將這個新的末尾節點賦值給last節點，如果l為null，說明是第一次加入數據，就將這個節點置為first節點，代表鏈表中第一個有數據的節點，否則將上一個節點的next指向這個節點。

（4）元素讀取get()

（5）元素刪除remove()

remove(int index)根據下標刪除，返回刪除的元素（其它一些刪除方法原理類似）

Vector

Vector概述

與ArrayList對比，這裡就不說那麼詳細了

Vector的實現

（1）私有屬性

發現底層也是數組。注意capacityIncrement為擴容時增長數量，如果擴容則為2倍（區別ArrayList的1.5倍）

（2）構造方法

有四種，其中一個無參的設置默認容量DEFAULT_SIZE=10

（3）增加元素等一系列方法

注意細節，每種方法前都有同步鎖 synchronized

（4）總結

• Vector底層和ArrayList相同，都是數組。

• Vector擴容是2倍，而ArrayList是1.5倍+1。

• Vector屬於線程安全的，但實用較少，因為開銷很大。

文中小部分蚊子參考博客，取其精華；感謝

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！