摘要：實現接口通過源碼可以看到繼承自實現了接口接口接口接口。因此也說明類是線程不安全的類。插入指定位置插入元素，其邏輯如下校驗是否有效范圍，否則拋出數組越界異常擴容確保能有效插入。雙指針的思路，一個讀指針，一個寫指針。

ArrayList是最常用的一種集合類型。今天通過閱讀源碼的方式來加深對它的學習和理解。 ##實現接口

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

通過源碼可以看到ArrayList繼承自AbstractList,實現了List接口、RandomAccess接口、Cloneable接口、Serializable接口。 說明它具備以下特點：

淺拷貝

序列化

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

DEFAULT_CAPACITY 表示默認的容量是10個元素。

transient Object[] elementData;
private int size;

elementData為實際存儲元素的數組，這里可以看到ArrayList的底層實際是一個數組。因此它具有數組的特點，隨機讀寫快，插入刪除慢。 transient關鍵字說明底層數組不能被序列化。 ？？

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

無參構造函數，構造一個空的數組。

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(Collection<); {
        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;
        }
    }

通過另外一個集合來構造。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

這里可以看到add方法是線程不安全的，因為size++操作并非原子操作。因此也說明ArrayList類是線程不安全的類。 ensureCapacityInternal()方法保證數組容量可以容納新增的這個元素，不會出現數組越界的情況。

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

指定index位置插入元素，其邏輯如下：

校驗index是否有效范圍，否則拋出數組越界異常.

擴容確保能有效插入。

將原數組index位置之后的元素全部后移一個位置。

將index位置設置為待插入元素。

public boolean addAll(Collection<); {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

和追加單個元素的原理類似，不同之處在于追加方式在于使用System.arraycopy方法。

public boolean addAll(int index, Collection<); {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(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;
    }

和插入單個元素的原理類似，不同之處在于index之后的元素往后移的位置為插入集合的長度。

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; // clear to let GC do its work

        return oldValue;
    }

邏輯如下：

校驗index是否合法，否則拋出數組越界異常

將index+1及以后的元素往前移一個位置

將最后一個元素置為null，同時size減一

返回刪除的元素值。

 public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

原理簡單，就是通過遍歷的方式。但是需要注意的是，只會移除第一個找到的元素。 fastRemove方法和remove(index) 方法作用相同，只是去掉了邊界校驗和返回值。

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

原理就是通過數組獲取指定index的元素。

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;
    }

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

并集就是addAll方法

 public boolean retainAll(Collection<); {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

public boolean removeAll(Collection<); {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

交集和差集都調用了batchRemove方法，通過一個boolean標記來表示要留下的是相同的一部分還是不同的一部分。 batchRemove方法的寫法還是值得學習。

private boolean batchRemove(Collection<);boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

雙指針的思路，一個讀指針，一個寫指針。讀指針每次往前增加一個位置，寫指針遇到要保留的元素時，再往前移動一個位置。 最后，如果讀指針沒走到最后就異常了，那把剩下讀指針剩下的元素拷貝到寫指針之后。 如果寫指針沒到最后，說明寫指針后面的元素都需要剔除，手動置為null，否則會內存泄露。 如果寫指針走到了最后，說明一個元素都沒有移除掉，所以返回false。