ArrayList源碼分析--jdk1.8

JDK1.8

ArrayList源碼分析--jdk1.8
LinkedList源碼分析--jdk1.8
HashMap源碼分析--jdk1.8
AQS源碼分析--jdk1.8
ReentrantLock源碼分析--jdk1.8

ArrayList概述

??1. ArrayList是可以動態擴容和動態刪除冗余容量的索引序列，基于數組實現的集合。
??2. ArrayList支持隨機訪問、克隆、序列化，元素有序且可以重復。
??3. ArrayList初始默認長度10，超出擴容1.5倍，使用Object[]存儲各種數據類型。

ArrayList數據結構

??數據結構是集合的精華所在，數據結構往往也限制了集合的作用和側重點，了解各種數據結構是我們分析源碼的必經之路。
??ArrayList的數據結構如下：

ArrayList源碼分析

/*
 * 用數組實現的集合，支持隨機訪問，元素有序且可以重復
 * RandomAccess(ArrayList) 支持快速隨機訪問，使用for循環更加快速
 * LinkedList 使用 iterator迭代器更加 快速
 * RandomAccess 這是一個標記接口，一般此標記接口用于 List 實現，以表明它們支持快速（通常是恒定時間）的隨機訪問。
 * 該接口的主要目的是允許通用算法改變其行為，以便在應用于隨機或順序訪問列表時提供良好的性能
 * 包含類中的基礎屬性和3個構造方法
 */
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
 /**
     * 默認長度  10
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 默認空的數組
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * ArrayList中的元素  是Object[]類型的數組
     */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * 動態數組的實際大小 ，默認為0
     * @serial
     */
    private int size;
     /**
     * 最大數組容量2147483639
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /**
     * 集合長度構造函數
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    /**
     * 無參構造函數，設置元素數組為空 注意此時初始容量是0，而不是大家以為的 10
     */
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
    /**
     * 集合參數構造函數
     */
    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) //是否成功轉化為Object類型數組
            elementData = Arrays.copyOf(elementData, size, Object[].class); //不為Object數組的話就進行復制
    }

ArrayList繼承和實現分析

?? ArrayList extends AbstractList
?? AbstractList extends AbstractCollection
??java中所有類都繼承Object，所以ArrayList的繼承結構如上圖。
?? 1. AbstractList是一個抽象類，實現了List<E>接口，List<E>定義了一些List通用方法，而AbstractList抽象類中可以有抽象方法，還可以有具體的實現方法，AbstractList實現接口中一些通用的方法，實現了基礎的add/get/indexOf/iterator/subList/RandomAccessSubList方法，ArrayList再繼承AbstractList，拿到通用基礎的方法，然后自己在實現一些自己特有的方法，這樣的好處是：讓代碼更簡潔，繼承結構最底層的類中通用的方法，減少重復代碼。
?? 2.ArrayList實現了List<E>、RandomAccess、Cloneable、Serializable接口
?? ??1)List<E>接口，ArrayList既然繼承自AbstractList抽象類，而AbstractList已 經實現了List接口，那么ArrayList類為何還要再實現List接口呢？我們帶著疑問往下看：

public class Demo1 extends ArrayList {
    public static void main(String[] args) {
                //返回[]
        System.out.println(Arrays.toString(Demo1.class.getInterfaces()));
    }
public class Demo2 implements Serializable {
    public static void main(String[] args) {
                //返回[interface java.io.Serializable]
        System.out.println(Arrays.toString(Demo2.class.getInterfaces()));
    }
public class Test{
    public static void main(String[] args) {
                Serializable c1 = new Demo1();//未顯示實現接口
                Serializable c2 = new Demo2();//顯示實現接口
                Serializable proxy2 = createProxy(c2);
                proxy2.foo();
                Serializable proxy1 = createProxy(c1);
                proxy1.foo();
 }

private static <T> T createProxy(final T obj) {
        final InvocationHandler handler = new InvocationHandler() {
            @Override
            public Object invoke(Object proxy, Method method, Object[] args)
                    throws Throwable {
                return method.invoke(obj, args);
            }
        };
                //實現接口代理，Demo1報錯，Demo2成功
                //java.lang.ClassCastException: $Proxy1 cannot be cast to
                //example.Test$Serializable
        return (T) Proxy.newProxyInstance(obj.getClass().getClassLoader(), obj
                .getClass().getInterfaces(), handler);
    }

可以看出這樣這樣設計是有道理的，因此，這并不是一個錯誤，很可能是作者Josh Bloch為了便于實現代理而精心設計的。
參考與：開發collection 的作者Josh說
?? ??2)RandomAccess接口，這是一個標記接口，一般此標記接口用于 List 實現，以表明它們支持快速（通常是恒定時間）的隨機訪問，該接口的主要目的是允許通用算法改變其行為，以便在應用于隨機或順序訪問列表時提供良好的性能，實現了該接口的話使用普通的for循環來遍歷，性能更高，而沒有實現該接口的話，使用Iterator來迭代，這樣性能更高，例如linkedList。所以這個標記性只是為了讓我們知道我們用什么樣的方式去獲取數據性能更好
?? ??3)Cloneable接口，可以使用Object.Clone()方法。
?? ??4)Serializable接口，序列化接口，表明該類可以被序列化，什么是序列化？簡單的說，就是能夠從類變成字節流傳輸，反序列化，就是從字節流變成原來的類

ArrayList核心方法分析

1. add方法(4種重載實現)--增?? ?

?? ??1)add(E)；//默認直接在末尾添加元素

/**
 * 新增元素
 */
public boolean add(E e) {
    //賦值初始長度  或者擴容,新增元素，當前實際size+1的長度
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //添加元素
        elementData[size++] = e;
        return true;
}
    /**
     * 確保elemenData數組有合適的大小
     * 如果元素為空，則復制長度默認為10 或者更大
    * @author jiaxiaoxian
    * @date 2019年2月12日 
     */
    private void ensureCapacityInternal(int minCapacity) {
            if (elementData == EMPTY_ELEMENTDATA) {//如果數組為空，則從size+1的值和默認值10中取最大的
                    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            ensureExplicitCapacity(minCapacity);
    }
/**
* 確保elemenData數組有合適的大小
* @author jiaxiaoxian
* @date 2019年2月12日 
* 如果長度大于元素長度則擴容
 */
private void ensureExplicitCapacity(int minCapacity) {
    //記錄修改次數，迭代中不一致會觸發fail-fast機制,因此在遍歷中刪除元素的正確做法應該是使用Iterator.remove()
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); //擴容
}
/**
 * 擴容
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length; // 舊容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量為舊容量的1.5倍
    if (newCapacity - minCapacity < 0) // 新容量小于參數指定容量，修改新容量
        newCapacity = minCapacity;
    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);
}
    //如果小于0 就報錯，如果大于最大值 則取最大值
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

?? ??2)add(int index, E element)；//給指定下標，添加元素

/**
 * 給指定下標，添加元素
 */
public void add(int index, E element) {
    //判斷下標是否越界
    rangeCheckForAdd(index);
    //賦值初始長度  或者擴容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //將源數組中從index位置開始后的size-index個元素統一后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //賦值
    elementData[index] = element;
    size++;
}
/**
 * 判斷下標是否越界
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 *     src:源數組
 * 　　srcPos:源數組要復制的起始位置
 * 　　dest:目的數組
 * 　　destPos:目的數組放置的起始位置
 * 　　length:復制的長度
 * 　　注意：src 和 dest都必須是同類型或者可以進行轉換類型的數組
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

?? ??3)addAll(Collection<? extends E> c)；//添加Collection類型元素

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

?? ??4)addAll(int index, Collection<? extends E> c)；//指定位置，添加Collection類型元素

/**
 * 從指定的位置開始，將指定collection中的所有元素插入到此列表中，新元素的順序為指定collection的迭代器所返回的元素順序
 */
public boolean addAll(int index, Collection<? extends E> c) {
    //判斷下標是否越界
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    int numMoved = size - index;
    //先將數組elementData[index,...,index+numMoved-1]復制到elementData[index+numMoved,...,index+2*numMoved-1]
    //即，將源數組中從index位置開始的后numMoved個元素統一后移numNew位
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

總結：
? ?正常情況下會擴容1.5倍，特殊情況下（新擴展數組大小已經達到了最大值）則只取最大值。
? ?

2.remove方法(4種重載實現)--刪

?? ??1)remove(int index); //根據指定下標 刪除元素?? ??

/**
 * 根據指定下標 刪除元素
 */
public E remove(int index) {
    //判斷索引是否越界
    rangeCheck(index);
    modCount++;
    //獲取舊元素
    E oldValue = elementData(index);
    //將數組elementData中index位置之后的所有元素向前移一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //將原數組最后一個位置置為null，由GC清理
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}   ?  ?

?? ??2)remove(Object o); //根據指定元素 刪除元素?

 /**
 * 移除ArrayList中首次出現的指定元素(如果存在)，ArrayList中允許存放重復的元素
 */
public boolean remove(Object o) {
    // 由于ArrayList中允許存放null，因此下面通過兩種情況來分別處理。
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //私有的移除方法，跳過index參數的邊界檢查以及不返回任何值
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}?  
/*
 * 根據下標快速刪除元素
 */
private void fastRemove(int index) {
    modCount++;
    //將數組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
}
 /**
 * 清空ArrayList，將全部的元素設為null，等待垃圾回收將這個給回收掉，所以叫clear
 */
public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}

?

?? ??3)removeAll(Collection<?> c); //刪除包含在指定容器c中的所有元素?

/**
 * 刪除ArrayList中包含在指定容器c中的所有元素
 */
public boolean removeAll(Collection<?> c) {
    //檢查指定的對象c是否為空
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
 /**
 * 刪除全部
* @author jiaxiaoxian
* @date 2019年2月12日 
 */
private boolean batchRemove(Collection<?> c, 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) //判斷指定容器c中是否含有elementData[r]元素
                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;
}

?? ??4)removeIf(Predicate<? super E> filter); //按照一定規則過濾(刪除)集合中的元素?

/**
 * 按照一定規則過濾(刪除)集合中的元素
 * 如：idList.removeIf(id -> id == nul);
    *   去掉 List idList 集合中id 為 null 的
 * @param filter
 * @return
 */
@Override
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

    // shift surviving elements left over the spaces left by removed elements
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            i = removeSet.nextClearBit(i);
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let gc do its work
        }
        this.size = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}

總結：
? ?remove函數用戶移除指定下標的元素，此時會把指定下標到數組末尾的元素向前移動一個單位，并且會把數組最后一個元素設置為null，這樣是為了方便之后將整個數組不被使用時，會被GC，可以作為小的技巧使用。

3.set方法--改

/**
 * 覆蓋指定下標元素
 */
public E set(int index, E element) {
    //判斷索引是否越界
    rangeCheck(index);
    //獲取舊元素
    E oldValue = elementData(index);
    //覆蓋為新元素
    elementData[index] = element;
    //返回舊元素
    return oldValue;
}
/**
 * 判斷下標是否越界
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4.get方法--查

 /**
 * 返回指定索引的值
 */
public E get(int index) {
    //判斷索引是否越界
    rangeCheck(index);
    return elementData(index);
}
/**
* @author jiaxiaoxian
* @date 2019年2月12日 
* 返回下標元素的 值
 */
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

5.indexOf方法--查找下標

/**
 * 查找下標， 如果為null,直接和null比較，返回下標
 */
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;
}

6.clone方法--克隆

 /**
 * 復制，返回此ArrayList 的淺拷貝
 */
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

7.trimToSize方法--刪除冗余容量

/**
 * 判斷數據實際容量大小，刪除自動增長后冗余的容量
 * 該方法用于回收多余的內存。也就是說一旦我們確定集合不在添加多余的元素之后，調用 trimToSize() 方法會將實現集合的數組大小剛好調整為集合元素的大小。
 * 　　注意：該方法會花時間來復制數組元素，所以應該在確定不會添加元素之后在調用
 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = Arrays.copyOf(elementData, size);
    }
}

8.Itr內部類--類似Iterator，可以幫我們對List進行遍歷，增刪改查等

/**
 * 實例化一個Itr對象，并返回
 */
public Iterator<E> iterator() {
    return new Itr();
}

/**
 * 內部類，類似Iterator，可以幫我們對List進行遍歷，增刪改查等
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return 下一個元素
    int lastRet = -1; // index of last element returned; -1 if no such 當前元素
    int expectedModCount = modCount; //modCount，就是為了判斷是否有多個線程訪問修改

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}   

9.ListItr內部類--繼承了內部類Itr，還在此基礎上增加了向前遍歷，增加元素，更改元素內容等功能

/**
 * 這個類繼承了內部類Itr
 * 除了擁有上一個類的功能，還增加了向前遍歷，增加元素，更改元素內容等功能
 */
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}   

10.SubList內部類--基于ArrayList建一個子集類

/**
 * 雖然這個類很長，其實里面的大部分方法調用都是ArrayList中的
 * ListIterator在這個類中采用匿名內部類做了一點更改，不過也很類似
 * 畢竟這個類就是根據ArrayList建一個子集類，就不贅述了
 */
private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

    public E set(int index, E e) {
         // 檢驗索引是否合法
        rangeCheck(index);
        //實現fail-fast機制  (迭代中不允許操作增刪改)
        checkForComodification();
        // 舊值
        E oldValue = ArrayList.this.elementData(offset + index);
        // 賦新值
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }

    public E get(int index) {
         // 檢驗索引是否合法
        rangeCheck(index);
        //實現fail-fast機制  (迭代中不允許操作增刪改)
        checkForComodification();
        return ArrayList.this.elementData(offset + index);
    }

    public int size() {
        checkForComodification();
        return this.size;
    }

    public void add(int index, E e) {
        rangeCheckForAdd(index);
        checkForComodification();
        parent.add(parentOffset + index, e);
        this.modCount = parent.modCount;
        this.size++;
    }

    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = parent.remove(parentOffset + index);
        this.modCount = parent.modCount;
        this.size--;
        return result;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        parent.removeRange(parentOffset + fromIndex,
                           parentOffset + toIndex);
        this.modCount = parent.modCount;
        this.size -= toIndex - fromIndex;
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(this.size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;

        checkForComodification();
        parent.addAll(parentOffset + index, c);
        this.modCount = parent.modCount;
        this.size += cSize;
        return true;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);
        final int offset = this.offset;

        return new ListIterator<E>() {
            int cursor = index;
            int lastRet = -1;
            int expectedModCount = ArrayList.this.modCount;

            public boolean hasNext() {
                return cursor != SubList.this.size;
            }

            @SuppressWarnings("unchecked")
            public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= SubList.this.size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[offset + (lastRet = i)];
            }

            public boolean hasPrevious() {
                return cursor != 0;
            }

            @SuppressWarnings("unchecked")
            public E previous() {
                checkForComodification();
                int i = cursor - 1;
                if (i < 0)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i;
                return (E) elementData[offset + (lastRet = i)];
            }

            @SuppressWarnings("unchecked")
            public void forEachRemaining(Consumer<? super E> consumer) {
                Objects.requireNonNull(consumer);
                final int size = SubList.this.size;
                int i = cursor;
                if (i >= size) {
                    return;
                }
                final Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length) {
                    throw new ConcurrentModificationException();
                }
                while (i != size && modCount == expectedModCount) {
                    consumer.accept((E) elementData[offset + (i++)]);
                }
                // update once at end of iteration to reduce heap write traffic
                lastRet = cursor = i;
                checkForComodification();
            }

            public int nextIndex() {
                return cursor;
            }

            public int previousIndex() {
                return cursor - 1;
            }

            public void remove() {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();

                try {
                    SubList.this.remove(lastRet);
                    cursor = lastRet;
                    lastRet = -1;
                    expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            public void set(E e) {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();

                try {
                    ArrayList.this.set(offset + lastRet, e);
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            public void add(E e) {
                checkForComodification();

                try {
                    int i = cursor;
                    SubList.this.add(i, e);
                    cursor = i + 1;
                    lastRet = -1;
                    expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            final void checkForComodification() {
                if (expectedModCount != ArrayList.this.modCount)
                    throw new ConcurrentModificationException();
            }
        };
    }

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, offset, fromIndex, toIndex);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= this.size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > this.size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+this.size;
    }

    /**
     * 實現fail-fast機制 
     * 線程不安全    迭代中不允許修改
    * @author jiaxiaoxian
    * @date 2019年2月12日 
     */
    private void checkForComodification() {
        if (ArrayList.this.modCount != this.modCount)
            throw new ConcurrentModificationException();
    }

    public Spliterator<E> spliterator() {
        checkForComodification();
        return new ArrayListSpliterator<E>(ArrayList.this, offset,
                                           offset + this.size, this.modCount);
    }
}

11.ArrayListSpliterator內部類--并行迭代，基于索引的二分裂，懶惰初始化的Spliterator

/**
 * @since 1.8
 * 實例化一個ArrayListSpliterator對象，并返回
 */
@Override
public Spliterator<E> spliterator() {
    return new ArrayListSpliterator<>(this, 0, -1, 0);
}

/**
 * Index-based split-by-two, lazily initialized Spliterator
 * 并行迭代
 * 基于索引的二分裂，懶惰初始化的Spliterator
 * */
static final class ArrayListSpliterator<E> implements Spliterator<E> {

    private final ArrayList<E> list;
    private int index; // current index, modified on advance/split
    private int fence; // -1 until used; then one past last index
    private int expectedModCount; // initialized when fence set

    /** Create new spliterator covering the given  range */
    ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                         int expectedModCount) {
        this.list = list; // OK if null unless traversed
        this.index = origin;
        this.fence = fence;
        this.expectedModCount = expectedModCount;
    }

    private int getFence() { // initialize fence to size on first use
        int hi; // (a specialized variant appears in method forEach)
        ArrayList<E> lst;
        if ((hi = fence) < 0) {
            if ((lst = list) == null)
                hi = fence = 0;
            else {
                expectedModCount = lst.modCount;
                hi = fence = lst.size;
            }
        }
        return hi;
    }

    public ArrayListSpliterator<E> trySplit() {
        int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
        return (lo >= mid) ? null : // divide range in half unless too small
            new ArrayListSpliterator<E>(list, lo, index = mid,
                                        expectedModCount);
    }

    public boolean tryAdvance(Consumer<? super E> action) {
        if (action == null)
            throw new NullPointerException();
        int hi = getFence(), i = index;
        if (i < hi) {
            index = i + 1;
            @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
            action.accept(e);
            if (list.modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return true;
        }
        return false;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        int i, hi, mc; // hoist accesses and checks from loop
        ArrayList<E> lst; Object[] a;
        if (action == null)
            throw new NullPointerException();
        if ((lst = list) != null && (a = lst.elementData) != null) {
            if ((hi = fence) < 0) {
                mc = lst.modCount;
                hi = lst.size;
            }
            else
                mc = expectedModCount;
            if ((i = index) >= 0 && (index = hi) <= a.length) {
                for (; i < hi; ++i) {
                    @SuppressWarnings("unchecked") E e = (E) a[i];
                    action.accept(e);
                }
                if (lst.modCount == mc)
                    return;
            }
        }
        throw new ConcurrentModificationException();
    }

    public long estimateSize() {
        return (long) (getFence() - index);
    }

    public int characteristics() {
        return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
    }
}

ArrayList總結

1）ArrayList可以存放null，本質是Object[]類型的數組。
2）ArrayList區別于數組的地方在于能夠自動擴展大小，其中關鍵的方法就是gorw()方法。
3）ArrayList由于本質是數組，所以它在數據的查詢方面會很快，而在插入刪除這些方面，性能下降很多，
有移動很多數據才能達到應有的效果，而LinkedList則相反。
4）ArrayList實現了RandomAccess，所以在遍歷它的時候推薦使用for循環。
5）初始化數組時推薦給初始長度，反復擴容會增加時耗，影響性能效率。
6)   Arrays工具類用來處理數組的工具類，Arrays.asList()方法返回的 ArrayList 數組是一個定長列表，
7)   我們只能對其進行查看或者修改，但是不能進行添加或者刪除操作，不能執行影響長度的操作，
8)   因為此ArrayList是Arrays中內部靜態類，只實現了部分查看修改方法，添加和刪除方法是
9)   繼承AbstractList父類的空方法，此ArrayList非彼ArrayList。