基于ArrayList源碼解析(基于JDK1.8)

更新時間：2023年03月13日 10:09:01 作者：Lframe

這篇文章主要介紹了關(guān)于ArrayList源碼解析(基于JDK1.8)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

下圖是ArrayList的UML圖

這里寫圖片描述

從圖中我們可以看出

1：實(shí)現(xiàn)了RandomAccess接口：表面ArrayList支持快速（通常是常量時間）的隨機(jī)訪問。官方源碼也給出了解釋：（因?yàn)榈讓訉?shí)現(xiàn)是一個數(shù)組，所以get()方法要比迭代器快，后面還會更有更加詳細(xì)的源碼解析）

這里寫圖片描述

2：實(shí)現(xiàn)了Cloneable接口，表明它支持克隆?？梢哉{(diào)用clone（）進(jìn)行淺拷貝。

3：實(shí)現(xiàn)了Serializable接口，表明它支持序列化。

4：它還實(shí)現(xiàn)了List接口，并且繼承自AbstractList抽象類。

代碼分析部分太多了，我直接把總結(jié)弄到最上面了，可以方便查看。

總結(jié)：

① ArrayList在我們?nèi)粘ｉ_發(fā)中隨處可見，所以建議大家可以自己手動實(shí)現(xiàn)一個ArrayList，實(shí)在寫不出來可以模仿一下ArrayList么。
② 由于ArryList隨機(jī)存儲，底層是用的一個數(shù)組作為存放元素的，所以在遍歷ArrayList的時候，使用get（）方法的效率要比使用迭代器的效率高。
③在ArrayList中經(jīng)常使用的一個變量modCount，它是在ArrayList的父類AbstractList中定義的一個protected變量，該變量主要在多線程的環(huán)境下，如果使用迭代器進(jìn)行刪除或其他操作的時候，需要保證此刻只有該迭代器進(jìn)行修改操作，一旦出現(xiàn)其他線程調(diào)用了修改modCount的值的方法，迭代器的方法中就會拋出異常。究其原因還是因?yàn)锳rrayList是線程不安全的。
④ 在ArrayList底層實(shí)現(xiàn)中，很多數(shù)組中元素的移動，都是通過本地方法System.arraycopy實(shí)現(xiàn)的，該方法是由native修飾的。
⑤ 在學(xué)習(xí)源碼的過程中，如果有看不懂的方法，可以自己寫一個小例子調(diào)用一下這個方法，然后通過debug的方式輔助理解代碼的含義。當(dāng)然啦，有能力的最好自己實(shí)現(xiàn)一下。（不過有些方法確實(shí)設(shè)計的超級精巧，直接讀代碼還看不懂，只能通過debug輔助學(xué)習(xí)源代碼，更別提寫這些方法了。。。。）
⑥ 不過我們在操作集合的過程中，盡量使用使用基于Stream的操作，這樣能夠不僅寫起來爽，看起來更爽！真的是誰用誰知道。簡直不要太爽！

下面是源碼解析的部分

①首先我們先看一下JDK中ArrayList的屬性有哪些：

   private static final long serialVersionUID = 8683452581122892189L;
	
	//默認(rèn)的容量
	private static final int DEFAULT_CAPACITY = 10;
    
    //定義了一個空的數(shù)組，用于在用戶初始化代碼的時候傳入的容量為0時使用。
    private static final Object[] EMPTY_ELEMENTDATA = {};
	
	//同樣是一個空的數(shù)組，用于默認(rèn)構(gòu)造器中，賦值給頂層數(shù)組elementData。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
	
	//底層數(shù)組，ArrayList中真正存儲元素的地方。
    transient Object[] elementData;
     
    //用來表示集合中含有元素的個數(shù)
    private int size;

②看看我們的JDK中提供的構(gòu)造器：（提供了三種構(gòu)造器，分別是：需要提供一個初始容量、默認(rèn)構(gòu)造器、需要提供一個Collection集合。）

//  如果我們給定的容量等于零，它就會調(diào)用上面的空數(shù)組EMPTY_ELEMENTDATA。
//	如果大于零的話，就把底層的elementData進(jìn)行初始化為指定容量的數(shù)組。
//	當(dāng)然啦，如果小于零的話，就拋出了違法參數(shù)異常（IllegalArgumentException）。
 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);
        }
    }


    /**
     * 默認(rèn)的情況下，底層的elementData使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA數(shù)組。
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     *
     * 傳入一個集合，首先把集合轉(zhuǎn)化為數(shù)組，然后把集合的底層數(shù)組elementData指向該數(shù)組，
     * 此時，底層數(shù)組有元素了，而size屬性表示ArrayList內(nèi)部元素的個數(shù)，所以需要把底層數(shù)組
     * element的大小賦值給size屬性，然后在它不等于0 的情況
     * 下（也就是傳進(jìn)來的集合不為空），再通過判斷保證此刻底層數(shù)組elementData數(shù)組的類型
     * 和Object[]類型相同，如果不同，則拷貝一個Object[]類型的數(shù)組給elementData數(shù)組。
     * 如果參數(shù)collection為null的話，將會報空指針異常。
     *
     * @param 一個Collection集合。
     * @throws 如果參數(shù)collection為null的話，將會報異常（NullPointerException）
     */
    public ArrayList(Collection<? extends E> c) {
        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;
        }
    }

③縮至“最簡潔”的容量：把ArrayList的底層elementData數(shù)組大小調(diào)整為size（size是ArrayList集合中存儲的元素的個數(shù)）

那為什么會有這個方法呢？

因?yàn)槲覀冊贏rrayList中添加元素的時候，當(dāng)ArrayList容量不足的時候，ArrayList會自動擴(kuò)容，（調(diào)用的是ensureCapacityInternal()方法，這個方法后續(xù)會講解。），一般擴(kuò)充為原來容量的1.5倍，我們可能用不了那么多的空間，所以，有時需要這個來節(jié)省空間。

//modCount這個變量從字面意思看，它代表了修改的次數(shù)。實(shí)際上它就是這個意思。
//它是AbstractList中的 protected修飾的字段。
//我們首先解釋一下它的含義：顧名思義，修改的次數(shù)（好像有點(diǎn)廢話了）
//追根溯源還是由于ArrayList是一個線程不安全的類。這個變量主要是用來保證在多線程環(huán)境下使用
//迭代器的時候，同時在對集合做修改操作時，同一時刻只能有一個線程修改集合，如果多于一個
//線程進(jìn)行對集合改變的操作時，就會拋出ConcurrentModificationException。
//所以，這是為線程不安全的ArrayList設(shè)計的。
//
//接著判斷一下，如果ArrayList中元素的個數(shù)小于底層數(shù)組的長度，說明此時需要縮容。
//最后通過一個三位運(yùn)算符判斷，如果ArrayList中沒有元素，則把底層數(shù)組設(shè)置為空數(shù)組。
//否則的話，就使用數(shù)組拷貝把底層數(shù)組的空間大小縮為size（元素個數(shù)）的大小。
//
  public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

④增加ArrayList實(shí)例的容量，如果有需要的話，以確保它至少能容納元素的數(shù)量由傳入的參數(shù)決定。

//官方的JDK中首先：需要確定一個最小的預(yù)期容量（minCapacity）：
//它通過判斷底層數(shù)組是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA（也就是說是不是使用了
//默認(rèn)的構(gòu)造器，)，如果沒有使用默認(rèn)的構(gòu)造器的話，它的最小預(yù)期容量是0，如果使用了默認(rèn)
//構(gòu)造器，最小預(yù)期容量（minCapacity）為默認(rèn)容量（DEFAULT_CAPACITY：10），
//最后判斷一下，如果參數(shù)大于最小預(yù)期的話，則需要調(diào)用ensureExplicitCapacity()方法
//擴(kuò)容。該方法講解，請看下面。
   public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    //因?yàn)樾枰M(jìn)行擴(kuò)容，也就是ArrayList發(fā)生了變化，所以需要modCount++.
    //接著判斷一下，如果我們傳進(jìn)來的參數(shù)（需要擴(kuò)充的容量）大于底層數(shù)組的長度elemntData
    //的時候，就需要擴(kuò)容了。 擴(kuò)容見下面的grow（）方法。
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //首先是新建一個變量oldCapacity，把底層數(shù)組的長度保存起來，然后通過oldCapacity做
	//移位運(yùn)算，向右移移位，就變成了oldCapacity的1.5倍了（可能小于1.5倍，后面就當(dāng)做1.5倍
    //對移位運(yùn)算不懂的童鞋們可以上網(wǎng)查查移位運(yùn)算的資料)。
    //接著判斷一下，如果newCapacity（它是底層數(shù)組容量的1.5倍）的大小仍然小于我們
    //自定義傳進(jìn)來的參數(shù)minCapacity的大小，就把minCapacity的值賦值給newCapacity。
    //接著再判斷一下如果newCapacity的大小超過了最大數(shù)組容量（MAX_ARRAY_SIZE），
    //MAX_ARRAY_SIZE代表了要分配數(shù)組的最大大小，如果試圖分配更大的長度時，超出了虛擬機(jī)的限制?？赡軙?dǎo)致OutOfMemoryError。
    //該值是一個常量，源碼中是：private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //就調(diào)用hugeCapacity進(jìn)行擴(kuò)容。最后把底層數(shù)組的容量擴(kuò)充進(jìn)行擴(kuò)容為newCapacity的容量。
    private void grow(int minCapacity) {
   
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //如果超出MAX_ARRAY_SIZE,會調(diào)用該方法分配Integer.MAX_VALUE的空間。
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

⑤求ArrayList的大小。（一目了然的代碼就不解釋了。）

直接返回size即可，因?yàn)閷傩詓ize代表了ArrayList的大小。

    public int size() {
        return size;
    }

⑥判斷ArrayList是否為空：

public boolean isEmpty() {
        return size == 0;
    }

⑦判斷某一元素在ArrayList中的位置（從前向后遍歷）：

源碼通過兩次for循環(huán)遍歷ArrayList，第一次用于判斷當(dāng)參數(shù)是空的時候，判斷其位置，第二次用于不為空的時候，判斷其位置，這兩次循環(huán)中，如果找到了就返回元素在集合中的位置，如果沒有找到則返回-1。可以看出，都是判斷位置時都是通過底層數(shù)組elementData的遍歷進(jìn)行判斷。

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

⑧判斷是否包含某個元素：

通過調(diào)用上面的indexof（）方法，如果該方法返回大于0，則存在該元素。

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

⑨判斷某一元素在ArrayList中的位置（從后向前遍歷）：

和indexOf（）方法差不多，就不解釋了。（只不過這次是從后向前遍歷）

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

⑩克隆方法。（實(shí)現(xiàn)了Cloneable接口）

直接調(diào)用超類Object的clone方法，然后強(qiáng)制轉(zhuǎn)化一下類型，然后把底層數(shù)組拷貝一下，切記要將modCount設(shè)置為0，最后返回即可。（當(dāng)拋出不支持克隆的異常的時候，將派出一個系你的內(nèi)部錯誤的異常。）

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

11：轉(zhuǎn)化為數(shù)組。（無參的方法）

這里調(diào)用了Arrays中的方法，不屬于ArrayList的范疇，所以不細(xì)剖析內(nèi)部的實(shí)現(xiàn)。后續(xù)的Arrays將會講解。

（其實(shí)最頂層是調(diào)用的本地方法（本地方法是指用native修飾的方法，即是用其他語言實(shí)現(xiàn)的邏輯），這里數(shù)組拷貝使用的是System.arraycopy（）方法。）

（其實(shí)，你看ArrayList的源碼實(shí)現(xiàn)的時候，會發(fā)現(xiàn)很多涉及數(shù)組移動、數(shù)組復(fù)制的操作都是用System.arraycopy（）處理的。）

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

12:轉(zhuǎn)化為數(shù)組（傳入一個和該方法返回值類型相同的數(shù)組）

前半段代碼含義很清晰：首先判斷一下傳進(jìn)來的數(shù)組a的大小是否小于需要轉(zhuǎn)化為數(shù)組的ArrayList的數(shù)組元素的個數(shù)，如果小于的話，返回原來ArrayList底層存儲元素的數(shù)組elementData，并且它的大小設(shè)置為ArrayList中元素的個數(shù)，且類型為傳進(jìn)來的類型參數(shù)a。（傳進(jìn)來的參數(shù)和返回值類型必須一致）

如果傳進(jìn)來數(shù)組a的帶下不小于ArrayList中元素的個數(shù)的話，則先把底層數(shù)組elementData中的元素全部復(fù)制到a中。

接下來比較奇怪的一點(diǎn)是：如果a的長度大于size的話，則把a(bǔ)[size]設(shè)置為空。

我通過代碼測試和查看官方解釋得出如下結(jié)論：

如果數(shù)組a的length大于ArrayList中元素的個數(shù)size，則把a(bǔ)[size]置為空，從結(jié)果目的是為了區(qū)分ArrayList和轉(zhuǎn)化后的數(shù)組的大小以及內(nèi)容有哪些區(qū)別。
如果是等于的話，它和小于的結(jié)果顯示一樣。都是輸出了轉(zhuǎn)化后的數(shù)組，且元素和元素的個數(shù)與ArrayList中元素和元素個數(shù)完全一致。

 public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

13：查看底層elementData數(shù)組的某個元素：（直接通過數(shù)組訪問）

 E elementData(int index) {
        return (E) elementData[index];
    }

14：檢查底層數(shù)組是否越界：

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

15：獲取某個位置上的元素：（直接通過數(shù)組操作）

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

        return elementData(index);
    }

16：設(shè)置某一位置上的元素，并且返回該位置的舊值：（都是很簡單，一目了然，不解釋了）

public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

17：添加一個元素：（這里和擴(kuò)容用的是同樣的輔助方法（輔助方法就是指private修飾的方法）。最后一次分析這些輔助方法。）

首先調(diào)用ensureCapacityInternal()方法，傳入當(dāng)前ArrayList中元素的個數(shù)+1；

進(jìn)入該方法后，調(diào)用 ensureExplicitCapacity();在該方法的參數(shù)中調(diào)用calculateCapacity(elementData, minCapacity)進(jìn)行容量的計算，如果我們的ArrayList是通過默認(rèn)的構(gòu)造器創(chuàng)建的話（就是代碼中的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA），則把minCapacity（也就是我們的size+1）和DEFAULT_CAPACITY（默認(rèn)容量是10）比較，取較大者返回，否則的話，就返回minCapacity，接著調(diào)用ensureExplicitCapacity(int minCapacity）方法，如果minCapacity大于底層數(shù)組的長度，則需要調(diào)用grow(minCapacity)進(jìn)行擴(kuò)容，否則的話，add（）方法中的ensureCapacityInternal(size + 1)什么也不做。（其實(shí)ensureCapacityInternal(size + 1)方法就是為了判斷數(shù)組用不用擴(kuò)容。）

如果需要擴(kuò)容的話，則調(diào)用grow（）方法：

下面解釋一下grow（）方法：

此時先定義一個變量oldCapacity，先把elementData數(shù)組的長度存儲起來，然后定義一個新的變量newCapacity，用來存儲擴(kuò)容后的容量，即oldCapacity + (oldCapacity >> 1)（大概是oldCapacity）的1.5倍。接著判斷一下，如果新容量小于我們設(shè)置的minCapacity的話，就把minCapacity賦值給newCapacity，

接著繼續(xù)判斷一下newCapacity是否大于MAX_ARRAY_SIZE，（這個MAX_ARRAY_SIZE代表了所能設(shè)置的數(shù)組的最大容量，如果超過這個值，可能導(dǎo)致內(nèi)存溢出的錯誤（OutOfMemoryError），當(dāng)然啦，如果超過的話，會將數(shù)組的容量設(shè)置為INTEGER.MAX_VALUE）。

總結(jié)：

添加一個元素之前，需要先判斷一下容量（底層elementData數(shù)組的大小是否滿足條件），如果容量不足，足需要擴(kuò)容，然后擴(kuò)大后的容量取決于size+1，最后給elementData[size++]賦值就可以了，最后返回true。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
    }
    
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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);
    }

18：為進(jìn)行增加操作的方法添加范圍檢查。

如果index大于size或者小于0，則拋出IndexOutOfBoundsException。

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

19：在指定位置的地方添加新的元素：

先檢查一下參數(shù)是否符合要求。

然后和上面通過ensureCapacityInternal(size + 1)判斷是否需要增加容量，如果需要則擴(kuò)容，如果不需要則什么也不做。

然后進(jìn)行數(shù)組拷貝（其實(shí)就是移動底層數(shù)組elementData的元素），最后把要添加的元素添加到指定的位置，然后size++（size代表了ArrayList中元素的個數(shù)）。

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

20：移出指定位置上的元素：

老規(guī)矩，但凡是改變添加或者刪除元素，都需要先檢查參數(shù)是否合法，因?yàn)榇朔椒ㄐ枰祷鼐偷闹?，所以需要先定義一個oldValue來存儲舊的值。

重要的學(xué)習(xí)點(diǎn)：

在移動元素的時候，仍然選擇進(jìn)行數(shù)組的拷貝。但是，這里涉及到一個數(shù)組邊界的問題：我們在計算出要移動的元素的個數(shù)后（這里可能有的童鞋看不懂為什么移動的個數(shù)是size-index-1，你可以畫個圖一下子就出來了，其實(shí)就是因?yàn)槲覀兊膇ndex指代的是數(shù)組的下標(biāo)，所以index位置處的元素以及它前面的元素的和是index+1，所以剩下的元素就是size-index-1，而剩下的元素，也就是index位置后的所有元素都需要向前移動，所以numMoved=size-index-1），移動的元素的個數(shù)大于0，我們下面數(shù)組拷貝（其實(shí)就是起到了移動元素的功能）才有意義，否則的話直接在elementData[–size]處設(shè)置為空就可以了。記住最后需要返回移除了的值。

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; 

        return oldValue;
    }

21：移除具體的元素：

提供兩種方法，一種是應(yīng)對參數(shù)為空的情況，另一種是應(yīng)對參數(shù)不為空的情況。

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

22：快速刪除指定位置上的元素：（這是一個輔助方法）（不提供給用戶使用。）

這個是JDK提供的刪除指定位置上元素的更快的方法。（從它的名字就看出來了。）

它直接跳過范圍檢查，并且不返回值。

private void fastRemove(int index) {
        modCount++;
        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
    }

23：清空ArrayList：

從代碼中看，非常簡單，通過for循環(huán)把底層數(shù)組中的元素全部置為null，然后把size設(shè)置為0就可以了。

  public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

24：把一個集合中的所有元素添加到ArrayList中：

首先把Collection參數(shù)轉(zhuǎn)化為一個數(shù)組，該toArray（）方法調(diào)用了Arrays類的copyOf（）方法，最底層調(diào)用的System.arraycopy（）方法。

然后把它的容量加上ArrayList的大小，然后和上面添加元素的方式一樣，繼續(xù)判斷一下容量夠不夠。最后進(jìn)行數(shù)組的拷貝，把參數(shù)中的所有元素添加到底層數(shù)組elementData中，然后把代表ArrayList中元素個數(shù)的size重新設(shè)置一下。最后如果參數(shù)的元素不為空，則返回true，表明把元素添加了進(jìn)去，如果為空的話，說明沒有添加元素，則返回false。

public boolean addAll(Collection<? extends E> c) {
        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;
    }

25：在ArrayList的指定位置上添加一個新的集合：

上面的一個方法同樣是添加一個集合到ArrayList中，為什么不需要進(jìn)行邊界檢查？這里就需要呢？

因?yàn)檫@個方法多傳了一個參數(shù)index，它用來指代插入ArrayList中的位置，如果index是一個負(fù)值或其他不合法的值時，就無法進(jìn)行后面的操作，而上面那個方法，默認(rèn)直接插入ArrayLisr底層數(shù)組的后面，所以不需要檢查。

numMoved=size-index;表示除了index位置前面的元素，Index位置上的元素以及index后面的元素都需要移動，如果size-index小于或等于0，則說明添加的位置在ArrayList中所有元素的后面，所以就無需第一個數(shù)組拷貝了（System.arraycopy(elementData, index, elementData, index + numNew,numMoved);）只需要進(jìn)行第二個數(shù)組拷貝，通過System.arraycopy(a, 0, elementData, index, numNew);數(shù)組拷貝即可，最后返回numNew!=0，和上面的套路一樣，不解釋了。

    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;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

26：移除某一個范圍的元素：

進(jìn)行修改操作還是得考慮為迭代器服務(wù)的modCount。

這個方法是protected修飾的，所以只有它的子類或者同一個包下才可以使用，所以，一般我們也用不到，但還是分析一下吧：

先給個結(jié)論吧：它刪除下標(biāo)從fromIndez到toIndex的元素，但是不刪除下標(biāo)為toIndex的元素。

首先求出要移動的元素，也就是說，toIndex位置的元素以及它后面的元素都要移動，然后通過System.arraycopy（）把toIndex位置的元素以及它后面的元素移動到了fromIndex的位置上。最后把新的底層數(shù)組elementData的對應(yīng)的原來的底層數(shù)組的最后一個位置的元素的后面所有元素都設(shè)置為null，然后調(diào)整數(shù)組的大小。

protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

27：移除集合中包含的所有元素：

首先需要調(diào)用Objects類保證參數(shù)不為空，然后調(diào)用battchRemove（）方法。

在battchRemove方法中，首先把底層數(shù)組elementData賦值給一個Object數(shù)組。接著通過遍歷底層數(shù)組elementData和傳進(jìn)來的參數(shù)c，判斷一下如果集合中不包含依次遍歷的底層數(shù)組的元素，首先通過遍歷底層數(shù)組elementData，判斷參數(shù)集合c是否包含遍歷過程中的每個元素，如果集合c不包含遍歷的元素時，就把底層數(shù)組的該元素賦值給底層數(shù)組的前面的一個，如果包含，則什么也不做，最后底層數(shù)組變成了前面不包

含集合c中含有的元素。后面就是用來通過判斷進(jìn)行修改底層數(shù)組，最后返回即可。

這里的代碼比較細(xì)，童鞋們可以自行debug一下，學(xué)習(xí)起來就容易很多了，下面給的邏輯超清晰。

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

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

28：只保留參數(shù)中的元素和底層數(shù)組elementData中相同的元素，剩下的全部刪除。

這個實(shí)現(xiàn)和上面的removeAll（）差不多，調(diào)用的是同一個輔助方法。

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

29：把ArrayList的狀態(tài)保存為流。（序列化）writeObject(java.io.ObjectOutputStream s)。

30：從流中重新構(gòu)建為ArrayList。（反序列化）readObject(java.io.ObjectInputStream s)。

31：返回List的專有迭代器（這個方法有個參數(shù)：用來表示從哪個位置迭代）：

其中ListItr是ArrayList中的內(nèi)部類。

ArrayList共有4個內(nèi)部類，分別是：Itr、ListItr、SubList、ArrayListSpliterator。

    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

32：返回List的專有迭代器（這個方法沒有參數(shù)，直接從開始位置進(jìn)行迭代。）

public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

33：普通迭代器：

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

34：Itr內(nèi)部類的分析：（代碼中解釋）

cursor：代表了返回的下一個元素的下標(biāo)。
lastRet：代表了返回最后一個元素的下標(biāo)，如果沒有最后一個元素，則返回-1。
expectedModCount：期望的ArrayList修改的次數(shù)。

private class Itr implements Iterator<E> {
        int cursor;       
        int lastRet = -1; 
        int expectedModCount = modCount;

        Itr() {}
// 如果下一個元素的下標(biāo)和底層數(shù)組elementData的數(shù)組大小不相等，則返回true。
        public boolean hasNext() {
            return cursor != size;
        }
//首先調(diào)用checkForComodification()方法，檢查一下modCount是否等于內(nèi)部類定義的expectedModCount，如果不等于，則拋出ConcurrentModificationException。
//那個方法的作用是什么呢？
//由于ArrayList自身是線程不安全的，如果當(dāng)前線程使用迭代器迭代ArrayList的時候，其他線程如果調(diào)用改變ArrayList的方法時候，而這些方法中都會修改modCount這個值，而這個值是在AbstractList中定義的protected變量，所以這里驗(yàn)證如果expectedModCount不等于modeCount的時候，說明有其他線程在修改ArrayList，所以該方法是用來保證帶迭代的時候其他線程不能修改modeCount的值。
然后定義一個變量i保存下一個元素的下標(biāo)，如果i>size，則拋出NoSuchElementException異常。
接著定義一個Object數(shù)組的引用指向底層數(shù)組，接著判斷一下如果i>size就拋出異常，接著把讓cursor自增，并通過elementData返回當(dāng)前元素。

        @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];
        }
//在remove方法中，首先判斷l(xiāng)asrRest是否小于0，如果小于0，表面它沒有進(jìn)行next操作，就
//會拋出IllegalStateException。因此我們在迭代的時候，必須保證每次都要先進(jìn)行next（）
//方法，然后進(jìn)行刪除remove（）操作。
//接著繼續(xù)檢查一下是否有其他線程修改了ArrayList。
//接著再try語句中刪除lastRet位置上的元素。接著把lastRet賦值給cursor，以便下一個next()方法使用，然后expectedModCount = modCount。
        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();
        }
    }

35：對ArrayList中的元素進(jìn)行排序。

需要傳入一個比較器，以實(shí)現(xiàn)自定義排序規(guī)則。

因?yàn)锳rrayList底層是用數(shù)組實(shí)現(xiàn)的，所以ArrayList就直接使用了Arrays.sort（）方法進(jìn)行了ArrayList的排序。

@Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }