前話：本次解析基于JDK1.8.0，SDK26。

一、數(shù)據(jù)結(jié)構(gòu)

ArrayList 是Java提供的一個存儲數(shù)據(jù)的工具類，其內(nèi)部使用 一個Object[] （數(shù)組）來存儲我們的數(shù)據(jù)。后續(xù)的添加、刪除、查詢等操作實際上都是對數(shù)組進行操作。

transient Object[]elementData; //transient是序列化和反序列化的知識點

二、構(gòu)造方法

使用ArrayList的前提就是定義ArrayList對象，先來看一下ArrayList類中的幾個重要的成員變量：

//實際存儲數(shù)據(jù)的數(shù)組
transient Object[] elementData;
//數(shù)組中實際數(shù)據(jù)的個數(shù)，注意并不是數(shù)組的長度（這塊要特別注意，后邊會用到）。默認為0
private int size;
//數(shù)組的默認容量或長度
private static final int DEFAULT_CAPACITY = 10;
//靜態(tài)的空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//靜態(tài)的默認的空數(shù)組，在后邊的構(gòu)造函數(shù)會看到和EMPTY_ELEMENTDATA的不同
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

1、首先分析最簡單的一種定義方式：

ArrayList list = new ArrayList();
其內(nèi)部實現(xiàn)：

public ArrayList() {
        //直接把默認的靜態(tài)的空數(shù)組賦值給elementData
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2、帶有初始化容量的構(gòu)造方法：

ArrayList list = new ArrayList(20);
其內(nèi)部實現(xiàn)：

//指定創(chuàng)建一個長度為initialCapacity的數(shù)組
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //要求的長度>0，則直接創(chuàng)建一個該長度的數(shù)組
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //賦值為空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //如果長度小于零，直接拋出異常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

三、add方法

對add方法的總結(jié)就是：當向ArrayList中添加一個元素時，先判斷當前數(shù)組中是否還有剩余空間，如果有剩余空間則直接將該元素添加至數(shù)組中元素的末尾，如果沒有剩余空間，先將數(shù)組擴容（擴容的算法簡單說就是將當前的數(shù)組容量擴大1.5倍），再將元素添加至數(shù)組中元素的末尾。

public boolean add(E e) {
        //每次add一個元素之前，先判斷size+1之后數(shù)組是否還有空余空間,
        //如果沒有剩余空間，對elementData進行擴容，如果有剩余空間則直接進行下一步。
        // 注意：size并不是數(shù)組的長度，而是數(shù)組中實際存儲對象的長度
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //注意size++，每次添加一個素，size增加1.
        elementData[size++] = e;
        return true;
    }

來重點看下ensureCapacityInternal方法：

private void ensureCapacityInternal(int minCapacity) {
        // elementData就是實際存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)：Object[]
        // 如果當前數(shù)組為空數(shù)組
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //DEFAULT_CAPACITY 為 10，是默認數(shù)組的長度
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //繼續(xù)調(diào)用方法
        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //等價于：minCapacity > elementData.length
        if (minCapacity - elementData.length > 0)
            // 第一次add的時候，elementData.length=0，數(shù)組為空數(shù)組，所以肯定要把當前數(shù)組擴容
            // 如果是第N次add，此時minCapacity > elementData.length,也就是數(shù)組需要更大的空間
            //所以也需要擴容。
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        //當前數(shù)組的長度(擴容之前的長度)
        int oldCapacity = elementData.length;
        //oldCapacity >> 1：位運算符，相當于oldCapacity/2,
        //新的容量等于：原來的容量 + 原來的容量的一半
        //所以每次擴容都是將數(shù)組的長度擴大為原來的1.5倍。
        int newCapacity = oldCapacity + (oldCapacity >> 1);

        //如果新的擴大1.5倍后，數(shù)組的空間仍然不夠
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果需要的空間比 MAX_ARRAY_SIZE 還要大，
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //hugeCapacity:申請最大的空間
            newCapacity = hugeCapacity(minCapacity);

        //最后根據(jù)需要的空間和原來的數(shù)組中的數(shù)據(jù)，將elementData重新賦值為擁有更大空間的數(shù)組
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

三、get方法

根據(jù)元素的坐標獲取元素，先判斷index是否合法，如果合法直接返回元素。

public E get(int index) {
        if (index >= size)
            //size是當前數(shù)組中元素的個數(shù)，并不是數(shù)組的長度，如果查詢的index超過size，拋異常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        
        //直接返回index對應的元素
        return (E) elementData[index];
    }

四、set方法

set(int index, E element）方法是將原數(shù)組中的下標為index的元素替換為新的數(shù)據(jù)。

public E set(int index, E element) {
        if (index >= size)
            //老規(guī)矩，還是先判斷size的長度
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        
        //將老的元素替換為新的元素，并把老元素返回
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

五、remove方法

public E remove(int index) {
        if (index >= size)
            //老規(guī)矩，先判斷size合法
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        //獲取要刪除的元素
        E oldValue = (E) elementData[index];

        //  假設一個數(shù)組有3個元素，現(xiàn)在刪除第二個元素（下標為1），numMoved= 3-1-1=1
        //numMoved表示在數(shù)組中刪除一個元素后，需要將該元素后邊的元素全部向前挪一位，那么一共要挪動的元素的個數(shù)即為numMoved
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
        //最后將刪除的元素返回
        return oldValue;
    }

六、indexOf 方法

indexOf 可以接受為Null的數(shù)據(jù)，如果數(shù)據(jù)為null，則返回整個數(shù)組中第一個為null的元素的下標。如果不為null，則遍歷整個數(shù)組中的元素，找到相等的元素并返回下標。
需要注意的是：indexOf(E e) 方法的平均時間復雜度為O(n)，因為它內(nèi)部是一個循環(huán)，所以在使用indexOf方法的時候，盡量不要再一個for循環(huán)中再使用indexOf，因為這樣的時間復雜度為O(n*n)，在內(nèi)存充足的情況下可以考慮使用“空間換時間”的方法，使用HashSet或者HashMap代替ArrayList。

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

七、size()方法

public int size() {
        //前邊已經(jīng)提到多次，ArrayList的size方法返回的是數(shù)組中元素的個數(shù)，不是整個數(shù)組的長度。
        return size;
    }

總結(jié)

其實ArrayList內(nèi)部還有幾個操作方法，但是總體的思路都是針對于數(shù)組進行操作，另外，在寫代碼的時候一定要注意indexOf的使用，這句代碼的時間復雜度為O(n)。