1 概述

1. ArrayList實現了List介面，是 順序容器，允許放入null元素
2. 有一個容量(capacity)，表示底層陣列的實際大小。如果容量不足，容器會 自動增大底層陣列的大小
3. 支援泛型，泛型擦除後，容器的元素都是 Object型別
4. ArrayList沒有實現同步(synchronized)，因此它是 執行緒不安全的。（vector執行緒安全）
5. 關於陣列：一旦陣列初始化完成，則長度不可改變 因此ArrayList擴容時會涉及陣列的拷貝

2 底層資料結構

兩個重要成員變數

1. Object[] elementData：

儲存列表元素的陣列；該陣列的長度就是列表的容量
列表的容量是指它所能儲存元素的最大個數

2. size：

列表的大小。指當前列表包含的元素個數，跟容量不是一個概念

size 跟 elementData陣列長度是不一樣的。elementData 允許長度大於元素的個數

    transient Object[] elementData; //儲存列表元素的陣列
    private int size;//元素的數量
    protected transient int modCount = 0; //list的修改次數

3 建構函式

有三個建構函式：

• 指定初始容量大小時，建立一個容量為引數的Object陣列，並賦值給資料陣列
• 不指定初始容量大小時，資料陣列賦值為一個無限容量的空陣列
• 構造引數為集合型別，將引數轉換成Object型別陣列，並賦值給資料陣列
• 注意，只有當第一次add元素時，才會指定陣列的長度

參照原始碼：

    //指定初始容量大小時，建立一個容量為引數的Object陣列，並賦值給資料陣列
    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);
        }
    }
// 不指定初始容量大小時，資料陣列賦值為一個無限容量的空陣列
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
// 構造引數為集合型別，將引數轉換成Object型別陣列，並賦值給資料陣列
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

4 自動擴容

1. 新增元素時，會判斷新增後是否超出當前陣列長度，超出則會執行陣列擴容；
2. 陣列擴容時，會將老陣列中的元素重新 拷貝一份到新的陣列中。（因為陣列長度不可變，因此需要建立新陣列）
3. 陣列執行擴容，擴容後的容量為擴容前的 1.5倍
4. 儘可能評估所需要容量的大小，避免擴容。（因為擴容佔用更多的記憶體）

參考原始碼:

重點！！！！！：新增前，都判斷是否需要擴容：（如果size+1後，超過elementData的長度，則執行擴容，擴容為原來的1.5倍）

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // size 初始化時是0，
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//計算所需容量:第一次新增時，容量為10；反則，容量為當前長度+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10,即第一次新增時，陣列長度變為10
    }
    return minCapacity;//如果陣列不為空時，最小長度是當前長度+1
}

//再次計算陣列所需容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//列表修改次數遞增
    //所需容量大於陣列的長度,則執行擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//擴容，陣列的記憶體狀態已經發生變化了
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//  新的長度為舊長度的1.5倍  【右移1位（除以2）】
    if (newCapacity - minCapacity < 0)  // 如果擴容後的長度小於所需要的最小長度，則使用最小長度(基本不會發生)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)  //這裡是極限的情況，即逼近陣列分配的最大記憶體空間
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);  // 執行陣列拷貝
}

5 set() get() remove()

• set()方法也就變得非常簡單，直接對陣列的指定位置賦值即可。

public E set(int index, E element) {
    rangeCheck(index);//下標越界檢查
    E oldValue = elementData(index);
    elementData[index] = element;//賦值到指定位置，複製的僅僅是參照
    return oldValue;//返回原先位置上的元素
}

• get()方法同樣很簡單，唯一要注意的是由於底層陣列是Object[]，得到元素後需要進行型別轉換。

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意型別轉換
}

• remove()方法也有兩個版本，一個是remove(int index)刪除指定位置的元素，另一個是remove(Object o)刪除第一個滿足o.equals(elementData[index])的元素。刪除操作是add()操作的逆過程，需要將刪除點之後的元素向前移動一個位置。需要注意的是為了讓GC起作用，必須顯式的為最後一個位置賦null值。

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);
    elementData[--size] = null; //清除該位置的參照，讓GC起作用
    return oldValue;
}

6 Fail-Fast機制

ArrayList也採用了快速失敗的機制，通過記錄 modCount 引數來實現。在面對並行的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發生任意不確定行為的風險。