【Java集合】ArrayList源碼分析

ArrayList是日常開發中經常使用到的集合，其底層采用數組實作，是以元素按序存放。其優點是可以使用下标來通路元素，時間複雜度是O(1)。其缺點是删除和增加操作需要使用<code>System.arraycopy()</code>來移動部分受影響的元素，時間複雜度為O(N)。同時<code>ArrayList</code>由于是采用數組來存放資料，是以會有容量限制，在使用時需要擴容，當插入操作超出數組長度，就會進行擴容，擴容後數組的長度為原來的1.5倍，預設的數組長度是10。

為了更好的掌握ArrayList，是以閱讀并仿照ArrayList源代碼，實作一個具有增删改查以及自動擴容功能的簡易版MyArrayList（代碼幾乎與ArrayList源碼一緻）。

首先建立一個class，命名為<code>MyArrayList</code>。

由于ArrayList是通過數組來存儲元素的，是以我們定義一個Object類型的數組<code>elementData</code>來存儲資料，再定義一個變量<code>size</code>，用來記錄數組中的元素個數，其預設值為0。

接下來就是構造函數，有兩種，第一種是未指定初始容量的構造函數，預設容量為10；第二種是在構造函數中傳入指定容量。

先說第一種構造函數，ArrayList在預設情況下，其容量為10。是以我們定義一個常量DEFAULT_CAPACITY = 10作為預設容量。同時，還定義一個常量數組DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}用于對elementData進行初始指派。

需要注意的是這裡的預設容量10并不是在構造函數中直接使用，而是在第一次插入進行擴容時才會使用。

第二種構造函數，傳入指定的容量。根據傳入的容量參數，我們有以下三種結果：

①傳入的容量參數大于0：則以該參數為容量建立對象數組

②存入的容量參數等于0：則需要建立一個空的對象數組，是以定義一個常量數組EMPTY_ELEMENTDATA = {}用于傳入容量為0時的初始化。

③傳入的容量參數小于0：明顯這是非法的，是以抛出參數異常IllegalArgumentException()

好了，構造函數建構完畢，接下來就是增删改查功能的實作，實作的方法如下：

首先是add(E e)方法，由于數組容量有限制，是以我們新增一個元素，都有可能要進行擴容，是以我們需要編寫一個函數ensureCapacityInternal來判斷是否需要自動擴容，若需要則進行擴容。

在ensureCapacityInternal函數中，需要傳入目前需要的最小容量。同時我們還要判斷對象數組elementData是否為空數組，若是，則将傳入的目前需要的最小容量與預設容量10進行對比，取其中的最大值作為本次擴容的容量。

接下來，我們判斷是否需要進行擴容。如果目前需要的最小容量大于原數組的長度，才進行擴容，否則不進行擴容，該功能寫入函數ensureExplicitCapacity。

然後，若進行擴容，則執行擴容函數grow。在grow中，我們需要進行如下操作：

①擷取原數組的容量oldCapacity，然後計算出值為oldCapacity1.5倍的新容量newCapacity

②将擴容1.倍後的新容量newCapacity與目前需要的最小容量minCapacity進行對比，若新容量小于目前需要的最小容量，則新容量的值取目前需要的最小容量。

③将新容量newCapacity與所允許的數組的最大長度進行對比，數組最大長度定義為常量MAX_ARRAY_SIZE = Integer.MAX_VALUE，值為整數的最大值。如果新容量newCapacity大于數組最大長度MAX_ARRAY_SIZE ，則取目前需要的最小容量minCapacity與數組最大長度MAX_ARRAY_SIZE兩者中的最小值作為新容量newCapacity的值。

④使用Arrays.copyOf(原數組, 新長度)進行數組的複制，即實作數組擴容

完成擴容任務的函數<code>grow</code>如下：

至此，就完成了新增時，判斷是否需要擴容，并且完成擴容功能。接下來我們隻需要将新增元素插入數組元素末尾位置的下一個位置，并傳回true即可。

最終，新增add方法和自動擴容有關的函數編寫完成：

接下來，就是删除，remove方法。由于該方法傳入待删除元素的位置索引index，是以需要檢查index

的範圍是否符合要求。編寫一個函數rangeCheck來檢查下标。

若index沒有超出範圍，則接下來就是擷取索引對應的元素，擷取方式很簡單，就是elementData[index]即可。考慮到其他方法也會需要通過這樣方式來擷取對應位置的元素，是以我們将這個操作抽取出來，成為一個函數elementData(),用于擷取元素。

那麼，目前remove方法前面兩個操作我們已經完成

删除index元素，需要把該位置後面的所有元素都向前移動一個位置。是以接下來我們就需要将index後面的元素向前移動一個位置。

具體做法是，先計算出需要移動的元素個數numMoved，用數組中最後一個元素的下标減去index即可獲得需要移動的元素個數：size-1-index。

然後利用System.arraycopy(）來移動元素，該方法的用法如下：

System.arrayCopy(Object srcArray,int srcPos,Object destArray ,int destPos,int length)

①Object srcArray 原數組（要拷貝的數組）

②int srcPos 要複制的原數組的起始位置（數組從0位置開始）

③ Object destArray 目标數組

④ int destPos 目标數組的起始位置

⑤int length 要複制的長度

從原數組srcArray 取元素，範圍為下标srcPos到srcPos+length-1，取出共length個元素，存放到目标數組中，存放位置為下标destPos到destPos+length-1。

我們将原數組和目标數組都設為elementData，然後原數組的起始位置為index+1，目标數組的起始位置為index，要複制的長度設為元素個數numMoved。這樣就能做到将數組index位置後面的元素向前移動一位。

不過這樣做目标數組的最後一位元素依然是原來的數，是以我們需要将目标數組最後的元素置為null，并且由于是删除，是以元素個數size需要減一。至此，删除方法remove完成。

增删操作已完成，接下來就是改操作，set()方法。這個方法就比較簡單，具體的步驟如下：

①檢查index範圍

②擷取index位置的元素

③将index位置的元素，替換為傳入的元素

④傳回原先index位置的元素

最後，就是查操作，get方法。該方法更為簡單，隻需要先檢查index範圍，再擷取index位置的元素直接傳回即可。

到這裡，我們編寫的簡易版ArrayList的增删改查操作就全部完成了。點進JDK1.8中ArrayList源碼可以看到，我們的上面的代碼幾乎與ArrayList源碼一模一樣。

最終這個簡易版ArrayList所有代碼如下：

我們測試一下，這個簡易版<code>ArrayList</code>

測試結果如下：