通過源碼，分析了ArrayList類的繼承實現結構，主要對ArrayList動態數組數據結構的具體實現細節進行分析 ...
一、基本概念
ArrayList是一個可以添加對象元素，併進行元素的修改查詢刪除等操作的容器類。ArrayList底層是由數組實現的，所以和數組一樣可以根據索引對容器對象所包含的元素進行快速隨機的查詢操作，其時間複雜度為O(1)。但是和數組不同的是，數組對象創建後數組長度是不變的，ArrayList對象創建後其長度是可變的，所以ArrayList也稱為動態數組，那麼ArrayList的動態數組數據結構又是如何實現的呢?接下來打開ArrayList源碼看看。
二、源碼分析
2.1、ArrayList類的繼承與實現
圖2.1 ArrayList類的繼承與實現（不包括繼承ArrayList的類）
- 從繼承介面可以發現，ArrayList繼承了AbstractCollection抽象類，實現了List介面，並且實現還實現了RandomAccess，Cloneable和Serializable三個標記介面，所以ArrayList的的對象具有能根據索引對元素進行快速隨機訪問、可以調用Object的clone()方法、可以進行序列化的特性。有關Java的標記介面是什麼，在上一篇文章
《Java的四個標記介面Serializable、Cloneable、RandomAccess和Remote介面》 進行了總結
2.2、ArrayList的屬性
- 通過源碼可以知道ArrayList主要有以下屬性
private static final long serialVersionUID = 8683452581122892189L;//用於ArrayList對象序列化的版本ID
private static final int DEFAULT_CAPACITY = 10;//ArrayList對象的預設容量大小
private static final Object[] EMPTY_ELEMENTDATA = {};//用於Null的ArrayList對象
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//用於創建一個預設容量大小的ArrayList對象
transient Object[] elementData; //用於創建動態大小的ArrayList對象，這個實例變數引用的數組可以說就是ArrayList容器
private int size;//ArrayList對象的尺寸
2.3、ArrayList類的三個構造函數
一個無參構造函數，一個傳入一個int 量指定容量的構造函數和一個傳入一個容器對象來進行初始化的構造函數
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
//指定ArrayList初始容量的構造器
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//一個預設容量的ArrayList無參構造器
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
//一個參數為一個容器對象的構造器，將該容器對象轉化為一個數組對象後，將ArrayList對象內的數組引用elementData初始化為這個數組對象（Object[]）
2.4、ArrayList動態數組的具體實現細節
ArrayList對象創建後，是怎麼改變這個對象的容量實現動態數組的呢，來看看動態數組實現的幾個重要方法
- grow方法。實現了ArrayList對象容量增加的方式，一般ArrayList新的容量為原容量的1.5倍大小，源碼如下
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//int整型的最大值減8
private void grow(int minCapacity) {
int oldCapacity = elementData.length;//原ArrayList對象的容量
int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量變為原容量+原容量/2,也就是新的容量增大為原來的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//新的容量如果還是小於指定容量，則新容量的值更新為指定容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//如果新容量大於int整數的最大值減8的值，則調用hugeCapacity(minCapacity)，新的容量為Interger.MAX_VALUE,即最大的Int整數
elementData = Arrays.copyOf(elementData, newCapacity);
//創建一個數組長度為newCapacity，包含所有原ArrayList內elementData所有元素的新的elementDate數組
- hugeCapacity方法，在grow方法中被調用
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }View Code
- trimToSize方法。將ArrayList對象內的elementData對象的長度變為size，size變數保存了ArrayList對象所含元素個數。使用這個方法可以使ArrayList對象內的elementData數組長度為元素個數，以避免不必要的記憶體占用。
-
public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size); }
//當size小於elementData，如果size=0，令elementData為一個空數組；size>0,使elementDate數組變數指向包含原elememtData所有元素，且長度為元素個數size的新數組 }
- ensureExplicitCapacity方法，在參數minCapacity大於elementDate引用的數組的長度時，調用grow方法來增加容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
- ensureCapacity方法，如果構造ArrayList對象時調用的是無參構造器，此時elementDate數組還沒創建，這個方法調用後可以確保ArrayList對象容量至少為10（預設值），且不小於minCapacity參數指定的值
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
- ensureCapacityInternal方法，在調用add方法增加元素時，調用這個方法來確保元素個數+1(size+1)小於或等於elementDate數組的長度，若size+1大於element.length，在ensureExplicitCapacity方法中會調用grow方法對ArrayList對象進行擴容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
/*Arraylist類調用無參構造器初始化後，elementData數組初始化為DEFAULTCAPACITY_EMPTY_ELEMENTDATA（一個空對象數組Object{}），若elementDate為初始化的值這裡返回的是預設容量和minCapacity中的較大值*/
}
return minCapacity;//若elementDate不是初始化的值，這個方法直接返回minCapacity的值
}
- add(int index)方法，實現了在指定的索引處添加元素，時間複雜度為O(n)
public void add(int index, E element) {
rangeCheckForAdd(index);//先檢測索引是否越界
ensureCapacityInternal(size + 1); //確保ArrayList的容量，即elementData數組的長度，在添加元素前大於size+1
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//將從index處以及後面的元素的都向後移動一位，索引+1。所以調用這個方法的時間複雜度為O(n)
elementData[index] = element;
//將元素element添加到索引為index的位置
size++;//元素個數加一
}
- remove(int index)方法，實現了在指定的位置刪除元素，時間複雜度為O(n)
public E remove(int index) {
rangeCheck(index);//檢查索引是否越界
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;//這個元素後面的元素個數
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//將這個元素後面的元素的前移一位，索引減一，原來index處的元素（要被刪除的元素）被後面一位的元素覆蓋。所以這個方法的時間複雜度為O(n)
elementData[--size] = null;
//數組索引為size處沒有元素，使其為空，元素個數size-1
return oldValue;
//將刪除的元素作為方法的返回值
}
（ArrayList還有很多其他的方法，以上是ArrayList實現動態數組的主要方法，ArrayList類其他的方法在這裡就不一一贅述了）
（小官原創，若有謬誤，望各位大佬批評指正）
（轉載請註明出處）
