我的博客地址
概述：

• ArrayList總的來說是實現(xiàn)List接口的可變數(shù)組，允許添加null元素

• 每個ArrayList實例都有一個容量（數(shù)組大小），它總是至少等于列表的大?。?strong>屬性size）。

• 隨著向ArrayList中不斷添加元素，如果size大于了容量會向一個新的數(shù)組中重新拷貝一遍。

• so（重要）：如果可預知數(shù)據(jù)量的多少，可在構造ArrayList時指定其容量。在添加大量元素前，應用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量，這可以減少遞增式再分配的數(shù)量。

• ArrayList不是線程安全的。

ArrayList的實現(xiàn)：

對于ArrayList而言，它實現(xiàn)List接口、底層使用數(shù)組保存所有元素。其操作基本上是對數(shù)組的操作。下面我們來分析ArrayList的源代碼：

• 底層使用數(shù)組實現(xiàn)：

private transient Object[] elementData;

2. 構造方法：
   ArrayList提供了三種方式的構造器，一是可以構造一個默認初始容量為10的空列表。二是構造一個指定初始容量的空列表。三是構造一個包含指定collection的元素的列表，這些元素按照該collection的迭代器返回它們的順序排列的。

public ArrayList() {   
    this(10);   
}   
  
public ArrayList(int initialCapacity) {   
    super();   
    if (initialCapacity < 0)   
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);   
    this.elementData = new Object[initialCapacity];   
}   
  
public ArrayList(Collection<? extends E> c) {   
    elementData = c.toArray();   
    size = elementData.length;   
    // c.toArray might (incorrectly) not return Object[] (see 6260652)   
    if (elementData.getClass() != Object[].class)   
        elementData = Arrays.copyOf(elementData, size, Object[].class);   
}  

• 存儲：
  ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)這些添加元素的方法。下面我們一一講解：

// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于該位置上的元素。   
public E set(int index, E element) {   
    RangeCheck(index);   
  
    E oldValue = (E) elementData[index];   
    elementData[index] = element;   
    return oldValue;   
}  

// 將指定的元素添加到此列表的尾部。   
public boolean add(E e) {   
    ensureCapacity(size + 1);    
    elementData[size++] = e;   
    return true;   
}  

// 將指定的元素插入此列表中的指定位置。   
// 如果當前位置有元素，則向右移動當前位于該位置的元素以及所有后續(xù)元素（將其索引加1）。   
public void add(int index, E element) {   
    if (index > size || index < 0)   
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);   
    // 如果數(shù)組長度不足，將進行擴容。   
    ensureCapacity(size+1);  // Increments modCount!!   
    // 將 elementData中從Index位置開始、長度為size-index的元素，   
    // 拷貝到從下標為index+1位置開始的新的elementData數(shù)組中。   
    // 即將當前位于該位置的元素以及所有后續(xù)元素右移一個位置。   
    System.arraycopy(elementData, index, elementData, index + 1, size - index);   
    elementData[index] = element;   
    size++;   
}  

// 按照指定collection的迭代器所返回的元素順序，將該collection中的所有元素添加到此列表的尾部。   
public boolean addAll(Collection<? extends E> c) {   
    Object[] a = c.toArray();   
    int numNew = a.length;   
    ensureCapacity(size + numNew);  // Increments modCount   
    System.arraycopy(a, 0, elementData, size, numNew);   
    size += numNew;   
    return numNew != 0;   
}  

// 從指定的位置開始，將指定collection中的所有元素插入到此列表中。   
public boolean addAll(int index, Collection<? extends E> c) {   
    if (index > size || index < 0)   
        throw new IndexOutOfBoundsException(   
            "Index: " + index + ", Size: " + size);   
  
    Object[] a = c.toArray();   
    int numNew = a.length;   
    ensureCapacity(size + numNew);  // Increments modCount   
  
    int numMoved = size - index;   
    if (numMoved > 0)   
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);   
  
    System.arraycopy(a, 0, elementData, index, numNew);   
    size += numNew;   
    return numNew != 0;   
}  

• 讀?。?/li>

// 返回此列表中指定位置上的元素。   
public E get(int index) {   
    RangeCheck(index);   
  
    return (E) elementData[index];   
}  

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

// 移除此列表中指定位置上的元素。   
public E remove(int index) {   
    RangeCheck(index);   
  
    modCount++;   
    E oldValue = (E) elementData[index];   
  
    int numMoved = size - index - 1;   
    if (numMoved > 0)   
        System.arraycopy(elementData, index+1, elementData, index, numMoved);   
    elementData[--size] = null; // Let gc do its work   
  
    return oldValue;   
}  

// 移除此列表中首次出現(xiàn)的指定元素（如果存在）。這是應為ArrayList中允許存放重復的元素。   
public boolean remove(Object o) {   
    // 由于ArrayList中允許存放null，因此下面通過兩種情況來分別處理。   
    if (o == null) {   
        for (int index = 0; index < size; index++)   
            if (elementData[index] == null) {   
                // 類似remove(int index)，移除列表中指定位置上的元素。   
                fastRemove(index);   
                return true;   
            }   
} else {   
    for (int index = 0; index < size; index++)   
        if (o.equals(elementData[index])) {   
            fastRemove(index);   
            return true;   
        }   
    }   
    return false;   
}  

• 調(diào)整數(shù)組容量： 從上面介紹的向ArrayList中存儲元素的代碼中，我們看到，每當向數(shù)組中添加元素時，都要去檢查添加后元素的個數(shù)是否會超出當前數(shù)組的長度，如果超出，數(shù)組將會進行擴容，以滿足添加數(shù)據(jù)的需求。數(shù)組擴容通過一個公開的方法ensureCapacity(int minCapacity)來實現(xiàn)。在實際添加大量元素前，我也可以使用ensureCapacity來手動增加ArrayList實例的容量，以減少遞增式再分配的數(shù)量。

public void ensureCapacity(int minCapacity) {   
    modCount++;   
    int oldCapacity = elementData.length;   
    if (minCapacity > oldCapacity) {   
        Object oldData[] = elementData;   
        int newCapacity = (oldCapacity * 3)/2 + 1;   
            if (newCapacity < minCapacity)   
                newCapacity = minCapacity;   
      // minCapacity is usually close to size, so this is a win:   
      elementData = Arrays.copyOf(elementData, newCapacity);   
    }   
}  

從上述代碼中可以看出，數(shù)組進行擴容時，會將老數(shù)組中的元素重新拷貝一份到新的數(shù)組中，每次數(shù)組容量的增長大約是其原容量的1.5倍。這種操作的代價是很高的，因此在實際使用時，我們應該盡量避免數(shù)組容量的擴張。當我們可預知要保存的元素的多少時，要在構造ArrayList實例時，就指定其容量，以避免數(shù)組擴容的發(fā)生?；蛘吒鶕?jù)實際需求，通過調(diào)用ensureCapacity方法來手動增加ArrayList實例的容量。 ArrayList還給我們提供了將底層數(shù)組的容量調(diào)整為當前列表保存的實際元素的大小的功能。它可以通過trimToSize方法來實現(xiàn)。代碼如下：

public void trimToSize() {   
    modCount++;   
    int oldCapacity = elementData.length;   
    if (size < oldCapacity) {   
        elementData = Arrays.copyOf(elementData, size);   
    }   
}  

• Fail-Fast機制：ArrayList也采用了快速失敗的機制，通過記錄modCount參數(shù)來實現(xiàn)。在面對并發(fā)的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發(fā)生任意不確定行為的風險。

• 關于其他 的一些方法的實現(xiàn)都很簡單易懂，讀者可參照API文檔和源代碼，一看便知，這里就不再多說。

注意：從數(shù)組中移除元素的操作，也會導致被移除的元素以后的所有元素的向左移動一個位置。