摘要：表明該類具有序列化功能。關(guān)鍵屬性默認(rèn)初始容量大小指定該容量為時，返回該空數(shù)組。構(gòu)造一個包含指定的元素的列表，這些元素是按照該的迭代器返回它們的順序排列的。對擴(kuò)容后的容量進(jìn)行判斷，如果大于允許的最大容量，則將容量再次調(diào)整為。

底層：ArrayList底層是一個數(shù)組，可以擴(kuò)容，正因為它擴(kuò)容，所以它能夠?qū)崿F(xiàn)“動態(tài)”增長

允許null元素

時間復(fù)雜度：size、isEmpty、get、set、iterator和listIterator方法都以固定時間運行，時間復(fù)雜度為O(1)。add和remove方法需要O(n)時間。與用于LinkedList實現(xiàn)的常數(shù)因子相比，此實現(xiàn)的常數(shù)因子較低。

容量：ArrayList的容量可以自動增長。

是否同步：ArrayList不同步的。

迭代器：ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的。

public class ArrayList extends AbstractList 
implements List, RandomAccess, Cloneable, java.io.Serializable

ArrayList：說明ArrayList支持泛型。

extends AbstractList：繼承了AbstractList。AbstractList提供List接口的骨干實現(xiàn)，以最大限度地減少“隨機訪問”數(shù)據(jù)存儲（如ArrayList）實現(xiàn)Llist所需的工作。

implements

List：實現(xiàn)了List。實現(xiàn)了所有可選列表操作。

RandomAccess：RandomAccess 是一個標(biāo)志接口，表明實現(xiàn)這個這個接口的 List 集合是支持快速隨機訪問的。在 ArrayList 中，我們即可以通過元素的序號快速獲取元素對象，這就是快速隨機訪問。

Cloneable：表明其可以調(diào)用clone()方法來返回實例的field-for-field拷貝。

java.io.Serializable：表明該類具有序列化功能。

    /**
     * 默認(rèn)初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 指定該ArrayList容量為0時，返回該空數(shù)組。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 當(dāng)調(diào)用無參構(gòu)造方法，返回的是該數(shù)組。剛創(chuàng)建一個ArrayList 時，其內(nèi)數(shù)據(jù)量為0。
     * 它與EMPTY_ELEMENTDATA的區(qū)別就是：該數(shù)組是默認(rèn)返回的，而后者是在用戶指定容量為0時返回。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 保存ArrayList數(shù)據(jù)的數(shù)組
     * 該值為DEFAULTCAPACITY_EMPTY_ELEMENTDATA 時，當(dāng)?shù)谝淮翁砑釉剡M(jìn)入ArrayList中時，數(shù)組將擴(kuò)容值DEFAULT_CAPACITY。
     */
    transient Object[] elementData; 

    /**
     * ArrayList 所包含的元素個數(shù)
     */
    private int size;

問：elementData被標(biāo)記為transient，那么它的序列化和反序列化是如何實現(xiàn)的呢？
答：ArrayList自定義了它的序列化和反序列化方式。詳情請查看writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectOutputStream s)方法。

ArrayList提供了三種構(gòu)造方法。

ArrayList(int initialCapacity)：構(gòu)造一個指定容量為capacity的空ArrayList。

ArrayList()：構(gòu)造一個初始容量為 10 的空列表。

ArrayList(Collection c)：構(gòu)造一個包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。

    /**
     * 帶初始容量參數(shù)的構(gòu)造函數(shù)。（用戶自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        //初始容量大于0
        if (initialCapacity > 0) {
            //創(chuàng)建initialCapacity大小的數(shù)組
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //創(chuàng)建空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 默認(rèn)構(gòu)造函數(shù)，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 為0.初始化為10，
     * 也就是說初始其實是空數(shù)組 當(dāng)添加第一個元素的時候數(shù)組容量才變成10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 構(gòu)造一個包含指定集合的元素的列表，按照它們由集合的迭代器返回的順序。
     * 如果指定的集合為null，throws NullPointerException。
     */
    public ArrayList(Collection c) {
        elementData = c.toArray();
        //如果指定集合元素個數(shù)不為0
        if ((size = elementData.length) != 0) {
            // c.toArray 可能返回的不是Object類型的數(shù)組所以加上下面的語句用于判斷，
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
            //【2】Arrays包含用來操作數(shù)組（比如排序和搜索）的各種方法。
            //copyOf(U[] original, int newLength, Class newType)
            // 復(fù)制指定的數(shù)組，截取或用 null 填充（如有必要），以使副本具有指定的長度。
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

步驟：

檢查角標(biāo)

返回元素

    /**
     * 返回此列表中指定位置的元素。
     * 
     * @param  index 需要返回的元素的索引
     * @return list中索引為index的元素
     * @throws IndexOutOfBoundsException 如果索引超出size
     */
    public E get(int index) {
        //越界檢查
        rangeCheck(index);

        return elementData(index);
    }
    
    /**
     * 檢查給定的索引是否在范圍內(nèi)。
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    /**
     * 返回IndexOutOfBoundsException細(xì)節(jié)信息
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    
    /**
     * 返回索引為index的元素
     */
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

步驟：

檢查是否需要擴(kuò)容

插入元素

整個擴(kuò)容過程：

首先去檢查一下數(shù)組的容量是否足夠

足夠：直接添加

不足夠：擴(kuò)容

擴(kuò)容到原來的1.5倍

第一次擴(kuò)容后，如果容量還是小于minCapacity，就將容量擴(kuò)充為minCapacity。

    /**
     * 將指定的元素追加到此列表的末尾。
     */
    public boolean add(E e) {
        //確認(rèn)list容量，如果不夠，容量加1。注意：只加1，保證資源不被浪費
        ensureCapacityInternal(size + 1);
        //這里看到ArrayList添加元素的實質(zhì)就相當(dāng)于為數(shù)組賦值
        elementData[size++] = e;
        return true;
    }

擴(kuò)容

/**
     * ArrayList的擴(kuò)容機制
     * ArrayList的擴(kuò)容機制提高了性能，如果每次只擴(kuò)充一個，
     * 那么頻繁的插入會導(dǎo)致頻繁的拷貝，降低性能，而ArrayList的擴(kuò)容機制避免了這種情況。
     * 如有必要，增加此ArrayList實例的容量，以確保它至少能容納元素的數(shù)量
     * @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        // 如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，最小擴(kuò)容量為DEFAULT_CAPACITY，否則為0
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    /**
     * 數(shù)組容量檢查，不夠時則進(jìn)行擴(kuò)容。
     *
     * @param minCapacity    想要的最小容量
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
            // 則取minCapacity為DEFAULT_CAPACITY和參數(shù)minCapacity之間的最大值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    //得到最小擴(kuò)容量
    private void ensureCapacityInternal(int minCapacity) {
        // 獲取默認(rèn)的容量和傳入?yún)?shù)的較大值
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    //判斷是否需要擴(kuò)容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 確保指定的最小容量 > 數(shù)組緩沖區(qū)當(dāng)前的長度
        if (minCapacity - elementData.length > 0)
            //擴(kuò)容
            grow(minCapacity);
    }

    /**
     * 要分配的最大數(shù)組大小
     * 為什么要減去8呢？
     * 因為某些VM會在數(shù)組中保留一些頭字，嘗試分配這個最大存儲容量，可能會導(dǎo)致array容量大于VM的limit，最終導(dǎo)致OutOfMemoryError。
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList擴(kuò)容的核心方法
     *
     * 第一次擴(kuò)容，邏輯為newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基礎(chǔ)上增加一半。
     * 第一次擴(kuò)容后，如果容量還是小于minCapacity，就將容量擴(kuò)充為minCapacity。
     */
    private void grow(int minCapacity) {
        // oldCapacity為舊容量，newCapacity為新容量
        int oldCapacity = elementData.length;
        //將oldCapacity 右移一位，其效果相當(dāng)于oldCapacity /2，
        //我們知道位運算的速度遠(yuǎn)遠(yuǎn)快于整除運算，整句運算式的結(jié)果就是將新容量更新為舊容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后檢查新容量是否大于最小需要容量，若還是小于最小需要容量，那么就把最小需要容量當(dāng)作數(shù)組的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再檢查新容量是否超出了ArrayList所定義的最大容量，
        //若超出了，則調(diào)用hugeCapacity()來比較minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，則新容量則為Interger.MAX_VALUE，否則，新容量大小則為 MAX_ARRAY_SIZE。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    //比較minCapacity和 MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) 
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

看完了代碼，可以對擴(kuò)容方法總結(jié)如下：

進(jìn)行空間檢查，決定是否進(jìn)行擴(kuò)容，以及確定最少需要的容量

如果確定擴(kuò)容，就執(zhí)行g(shù)row(int minCapacity)，minCapacity為最少需要的容量

第一次擴(kuò)容，邏輯為newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基礎(chǔ)上增加一半。

第一次擴(kuò)容后，如果容量還是小于minCapacity，就將容量擴(kuò)充為minCapacity。

對擴(kuò)容后的容量進(jìn)行判斷，如果大于允許的最大容量MAX_ARRAY_SIZE，則將容量再次調(diào)整為MAX_ARRAY_SIZE。至此擴(kuò)容操作結(jié)束。

步驟：

越界檢查

空間檢查，如果有需要進(jìn)行擴(kuò)容

插入元素

    /**
     * 在此列表中的指定位置插入指定的元素。
     * 先調(diào)用 rangeCheckForAdd 對index進(jìn)行界限檢查；然后調(diào)用 ensureCapacityInternal 方法保證capacity足夠大；
     * 再將從index開始之后的所有成員后移一個位置；將element插入index位置；最后size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1); 
        //arraycopy()這個實現(xiàn)數(shù)組之間復(fù)制的方法一定要看一下，下面就用到了arraycopy()方法實現(xiàn)數(shù)組自己復(fù)制自己
        //實現(xiàn)讓index開始之后的所有元素后移一個位置:
        //elementData:源數(shù)組;index:源數(shù)組中的起始位置;elementData：目標(biāo)數(shù)組；index + 1：目標(biāo)數(shù)組中的起始位置； size - index：要復(fù)制的數(shù)組元素的數(shù)量；
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

add(int index, E e)需要先對元素進(jìn)行移動，然后完成插入操作，也就意味著該方法有著線性的時間復(fù)雜度，即O(n)

步驟：

檢查角標(biāo)

刪除元素

計算出需要移動的個數(shù)，將索引大于index的元素左移一位（左移后，該刪除的元素就被覆蓋了，相當(dāng)于被刪除了）

設(shè)置為null（size-1處），讓Gc回收

    /**
     * 刪除該列表中指定位置的元素。 將任何后續(xù)元素移動到左側(cè)（從其索引中減去一個元素）。
     */
    public E remove(int index) {
        //檢查索引是否越界
        rangeCheck(index);
        //結(jié)構(gòu)性修改次數(shù)+1【1】
        modCount++;
        E oldValue = elementData(index);
        // 刪除指定元素后，需要左移的元素個數(shù)
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // size減一，然后將索引為size-1處的元素置為null。為了讓GC起作用，必須顯式的為最后一個位置賦null值
        elementData[--size] = null; 
        //從列表中刪除的元素
        return oldValue;
    }

注意：為了讓GC起作用，必須顯式的為最后一個位置賦null值。上面代碼中如果不手動賦null值，除非對應(yīng)的位置被其他元素覆蓋，否則原來的對象就一直不會被回收。

步驟：

檢查角標(biāo)

替代元素

返回舊值

    /**
     * 用指定的元素替換此列表中指定索引的元素。
     */
    public E set(int index, E element) {
        //對index進(jìn)行界限檢查
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        //返回原來在這個位置的元素
        return oldValue;
    }

細(xì)節(jié)：

ArrayList是基于動態(tài)數(shù)組實現(xiàn)的，在增刪時候，需要數(shù)組的拷貝復(fù)制。

ArrayList的默認(rèn)初始化容量是10，每次擴(kuò)容時候增加原先容量的一半，也就是變?yōu)樵瓉淼?.5倍

刪除元素時不會減少容量，若希望減少容量則調(diào)用trimToSize()

它能存放null值。

和 Vector 不同，ArrayList 中的操作不是線程安全的！所以，建議在單線程中才使用 ArrayList，而在多線程中可以選擇 Vector 或者 CopyOnWriteArrayList。

移位運算符 　　
簡介：移位運算符就是在二進(jìn)制的基礎(chǔ)上對數(shù)字進(jìn)行平移。按照平移的方向和填充數(shù)字的規(guī)則分為三種:<<(左移)、>>(帶符號右移)和>>>(無符號右移)。 　　
作用：對于大數(shù)據(jù)的2進(jìn)制運算,位移運算符比那些普通運算符的運算要快很多,因為程序僅僅移動一下而已,不去計算,這樣提高了效率,節(jié)省了資源 　　
比如這里：int newCapacity = oldCapacity + (oldCapacity >> 1); 右移一位相當(dāng)于除2，右移n位相當(dāng)于除以 2 的 n 次方。這里 oldCapacity 明顯右移了1位所以相當(dāng)于oldCapacity /2。
另外需要注意的是：

java 中的length 屬性是針對數(shù)組說的，比如說你聲明了一個數(shù)組，想知道這個數(shù)組的長度則用到了 length 這個屬性.

java 中的length()方法是針對字符串String說的，如果想看這個字符串的長度則用到 length()這個方法.

java 中的size()方法是針對泛型集合說的，如果想看這個泛型有多少個元素，就調(diào)用此方法來查看!

內(nèi)部類：

(1)private class Itr implements Iterator  
(2)private class ListItr extends Itr implements ListIterator  
(3)private class SubList extends AbstractList implements RandomAccess  
(4)static final class ArrayListSpliterator implements Spliterator  

Itr是實現(xiàn)了Iterator接口，同時重寫了里面的hasNext()，next()，remove()等方法；

ListItr繼承Itr，實現(xiàn)了ListIterator接口，同時重寫了hasPrevious()，nextIndex()，previousIndex()，previous()，set(E e)，add(E e)等方法，

所以這也可以看出了 Iterator和ListIterator的區(qū)別：ListIterator在Iterator的基礎(chǔ)上增加了添加對象，修改對象，逆向遍歷等方法，這些是Iterator不能實現(xiàn)的。

參考資料：
https://blog.csdn.net/panweiw...
https://segmentfault.com/a/11...
https://github.com/Snailclimb...