ArrayList是以數(shù)組為基準的容器類，和LinkedList(鏈表)正好相反。因而ArrayList擁有更好的查找性能，增刪操作則差一些。ArrayList封裝了對于常規(guī)數(shù)組的操作，同時可以自動擴展容量。

下面對ArrayList的API進行歸類：

1、構造函數(shù)：

①ArrayList()　　以空數(shù)組進行構造　　

②ArrayList(int)　以指定大小的容量初始化數(shù)組

③ArrayList(Collection)　　以指定集合構造ArrayList的數(shù)組元素

2、增加元素：

①boolean add(E)　　在數(shù)組末尾加入指定元素

②void add(int,E)　　在第一個參數(shù)指定的索引處插入元素，后面所有元素后移一個位置

③boolean addAll(Collection)　　在數(shù)組末尾加入集合的所有元素

④boolean addAll(int,Collection) 在指定索引處加入集合所有元素

3、刪除元素：

①E remove(int)　　移除索引處元素，之后的所有元素前移一位

②boolean remove(Object)　　查找到指定元素，刪除之，未刪除成功false

③void removeRange(int,int)　刪除指定區(qū)間的所有元素，刪除第一個索引處，但不刪除最后一個索引處

④void clear()　　刪除所有元素

4、更改元素：

　set(int,Object)　　將指定索引處的值修改為指定的值

5、查找：

①E get(int)　　返回指定索引處的元素

②boolean contains(Object)　　確定是否包含該元素

③int indexOf(Object)　　從前往后查找指定元素的索引，找不到返回-1

④int lastIndexOf(Object)　　從后往前查找元素索引，找不到返回-1

⑤int size()　　返回包含的元素個數(shù)

⑥boolean isEmpty()　　確定數(shù)組是否為空

6、其他操作：

①Object[] toArray()　　返回Object數(shù)組，每個Object對應ArrayList的一個元素

②T[] toArray(T[])　　返回T類型數(shù)組，每個T對應ArrayList的一個實際類型的元素

③void trimToSize()　　刪除數(shù)組最后冗余的值為null的元素

④void ensureCapacity(int)　　使數(shù)組容量擴充為指定的容量

⑤Object clone()　　　　復制一個除了內存地址其他信息完全一樣的ArrayList

接下來進行源碼解析

一、ArrayList包含的成員變量和常量：

transient Object[] array;    //ArrayList的核心，所有操作都圍繞它展開，ArrayList類似于數(shù)組的包裝類int size;    //數(shù)組包含的實際元素個數(shù)，不是數(shù)組容量，為了滿足添加元素時數(shù)組不必多次擴容，必須預先將容量設定為某個略大些的值。這樣就不能用array.length得到元素個數(shù)了

二、構造函數(shù)3種

    //不給參數(shù)，用空數(shù)組初始    public ArrayList() {        array = EmptyArray.OBJECT;    }

　　//用一個已有的容器對象初始化數(shù)組　　public ArrayList(Collection<? extends E> collection) {        if (collection == null) {            throw new NullPointerException("collection == null");        }        Object[] a = collection.toArray();        if (a.getClass() != Object[].class) {//這個過程看不懂            Object[] newArray = new Object[a.length];            System.arraycopy(a, 0, newArray, 0, a.length);    //數(shù)組復制操作            a = newArray;        }        array = a;        size = a.length;    }

   //用指定初始容量初始化數(shù)組，當容量可以確定的時候用這個方法可以避免多次更改數(shù)組大小，提高性能    public ArrayList(int capacity) {        if (capacity < 0) {            throw new IllegalArgumentException("capacity < 0: " + capacity);        }        array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);    }

三、增加元素

　　這應該是ArrayList中最復雜的操作了，因為涉及到容量擴充的操作，也是ArrayList和數(shù)組最大的區(qū)別——自動擴容。但是因為涉及到重新分配內存空間和數(shù)組整個復制，多次擴容會影響性能

    @Override     public boolean add(E object) {        Object[] a = array;        //用一個代表，減少書寫量        int s = size;        if (s == a.length) {    //數(shù)組已滿，必須先擴容        //注意這邊的擴容策略，必須先開辟一片更大的內存空間，再執(zhí)行數(shù)組復制操作       //具體新數(shù)組取多大，如果當前容量小于最小容量增長值的一半，則按這個值增長；否則即原來容量足夠大，在原來容量基礎上增加一半            Object[] newArray = new Object[s +                    (s < (MIN_CAPACITY_INCREMENT / 2) ?                     MIN_CAPACITY_INCREMENT : s >> 1)];            System.arraycopy(a, 0, newArray, 0, s);  //數(shù)組復制操作            array = a = newArray;        }        a[s] = object;    //現(xiàn)在容量足夠了，在新數(shù)組末尾直接加上這個新元素        size = s + 1;    //別忘了現(xiàn)在元素個數(shù)加了一個，必須保持同步        modCount++;  //修改次數(shù)加1        return true;    }

    //對上面的擴容操作進行了抽象，可能因為上面的操作更頻繁，所以直接把擴容操作寫在代碼里面以提高性能吧    PRivate static int newCapacity(int currentCapacity) {        int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?                MIN_CAPACITY_INCREMENT : currentCapacity >> 1);        return currentCapacity + increment;    }        //在指定位置插入，除了數(shù)組復制操作的范圍不同，其他都一樣    @Override     public void add(int index, E object) {        Object[] a = array;        int s = size;        if (index > s || index < 0) {            throwIndexOutOfBoundsException(index, s);        }        if (s < a.length) {            System.arraycopy(a, index, a, index + 1, s - index);        } else {            // assert s == a.length;            Object[] newArray = new Object[newCapacity(s)];            System.arraycopy(a, 0, newArray, 0, index);            System.arraycopy(a, index, newArray, index + 1, s - index);            array = a = newArray;        }        a[index] = object;        size = s + 1;        modCount++;    }

四、刪除元素

    //這里數(shù)組相比鏈表的劣勢就很明顯了，刪除指定位置的值很簡單，但是為了保持后面操作的穩(wěn)定性，必須將之后的所有值前移一個位置，需要O(n)的時間，而鏈表只要O(1)。    //這里得到一個很重要的啟示：如果要移除多個連續(xù)的元素，用for循環(huán)配合這個方法會非常損耗性能，應該用下面的removeRange方法    @Override     public E remove(int index) {        Object[] a = array;        int s = size;        if (index >= s) {            throwIndexOutOfBoundsException(index, s);        }        @SuppressWarnings("unchecked")        E result = (E) a[index];   //因為每個元素都是Object類型，必須強轉        System.arraycopy(a, index + 1, a, index, --s - index);        a[s] = null;  // 防止內存占用過多，不用的值置為null，給系統(tǒng)及時回收        size = s;        modCount++;        return result;    }   //移除連續(xù)區(qū)間的元素，只需執(zhí)行一次arrayCopy操作   @Override protected void removeRange(int fromIndex, int toIndex) {        if (fromIndex == toIndex) {            return;        }        Object[] a = array;        int s = size;        if (fromIndex >= s) {            throw new IndexOutOfBoundsException("fromIndex " + fromIndex                    + " >= size " + size);        }        if (toIndex > s) {            throw new IndexOutOfBoundsException("toIndex " + toIndex                    + " > size " + size);        }        if (fromIndex > toIndex) {            throw new IndexOutOfBoundsException("fromIndex " + fromIndex                    + " > toIndex " + toIndex);        }        System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);        int rangeSize = toIndex - fromIndex;        Arrays.fill(a, s - rangeSize, s, null);   //不用的索引處全部置null        size = s - rangeSize;        modCount++;    }    //需要依次對每一個元素進行比較，性能也不好    //可以看出這個方法只會刪除第一個出現(xiàn)的元素，如果存在equals比較后相同的元素，還有遺留    @Override     public boolean remove(Object object) {        Object[] a = array;        int s = size;        if (object != null) {            for (int i = 0; i < s; i++) {                if (object.equals(a[i])) {                    System.arraycopy(a, i + 1, a, i, --s - i);                    a[s] = null;  // Prevent memory leak                    size = s;                    modCount++;                    return true;                }            }        } else {            for (int i = 0; i < s; i++) {                if (a[i] == null) {                    System.arraycopy(a, i + 1, a, i, --s - i);                    a[s] = null;  // Prevent memory leak                    size = s;                    modCount++;                    return true;                }            }        }        return false;    }  

    //這里可以看出是通過將每個元素依次置為null，也需要O(n)時間；并不改變數(shù)組容量    @Override     public void clear() {        if (size != 0) {            Arrays.fill(array, 0, size, null);            size = 0;            modCount++;        }    }

五、修改元素值

    //修改元素值很簡單，跟數(shù)組操作一樣，只要O(1)時間就能完成，同時返回被修改的舊值    @Override     public E set(int index, E object) {        Object[] a = array;        if (index >= size) {            throwIndexOutOfBoundsException(index, size);        }        @SuppressWarnings("unchecked")         E result = (E) a[index];        a[index] = object;        return result;    }    

六、查找操作

    //查找操作是ArrayList最大的優(yōu)勢，因為數(shù)組在內存中占用連續(xù)的存儲區(qū)域，只要O(1)時間就能找到指定索引所對應的值    @SuppressWarnings("unchecked")     @Override     public E get(int index) {        if (index >= size) {            throwIndexOutOfBoundsException(index, size);        }        return (E) array[index];    }

七、其他操作

　　關于ArrayList向數(shù)組轉換（其實是返回ArrayList的成員數(shù)組的拷貝）

    /*這兩個方法經常會搞混，包括我初學的時候也不知道是怎么回事。第一種方法貌似很簡單，但是因為返回的是Object數(shù)組，后續(xù)如果要對這個返回的數(shù)組操作一般要轉換為具體的類型，就還要對該數(shù)組的每個元素都強轉一次。而第二個方法傳入一個給定的數(shù)組，這個數(shù)組是指定了具體的類型的，因而返回后這個數(shù)組可以直接用。通常傳入一個空數(shù)組 new T[]{}即可。    */    @Override     public Object[] toArray() {        int s = size;        Object[] result = new Object[s];        System.arraycopy(array, 0, result, 0, s);        return result;    }    /*這里有一點讓我不明白，為什么泛型要選擇T而不是E？如果T和E不一致，arraycopy操作會成功嗎？*/    @Override     public <T> T[] toArray(T[] contents) {        int s = size;        if (contents.length < s) {  //如果提供的數(shù)組不夠放，重新開辟內存            @SuppressWarnings("unchecked")             T[] newArray                = (T[]) Array.newInstance(contents.getClass().getComponentType(), s);            contents = newArray;        }        System.arraycopy(this.array, 0, contents, 0, s);        if (contents.length > s) {            contents[s] = null;    //這里也讓我不明白，為什么只把s處置為null，s以后的不也應該置為null嗎？        }        return contents;    }