1、揭開ArrayList真面目

作者將在本文詳細(xì)贅述日常開發(fā)中最常用集合類-ArrayList，本次JCF源碼分析基于JDK1.7，主要從以下幾個(gè)方向分析：

• UML類圖關(guān)系
• 數(shù)據(jù)結(jié)構(gòu)
• 接口介紹
• 常用、重要方法的實(shí)現(xiàn)

1.1 UML類圖關(guān)系

從UML關(guān)系類圖，我們可以直觀的看出ArrayList的類結(jié)構(gòu)，圖中虛線表示實(shí)現(xiàn)(implements)關(guān)系，實(shí)線表示繼承(extends)關(guān)系，我們不必在還不熟悉的情況下對(duì)這種關(guān)系進(jìn)行“死記硬背”，因?yàn)樵诶斫庹麄€(gè)集合框架之后自然不用看都會(huì)比較清晰，辣么下面我們將對(duì)接口或類一一介紹：

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

1.2.1 JAVA常用數(shù)據(jù)結(jié)構(gòu)

在介紹Collection具體的實(shí)現(xiàn)類或者某一種抽象之前，筆者需要對(duì)JAVA最常用的數(shù)據(jù)結(jié)構(gòu)進(jìn)行簡(jiǎn)單贅述

• 線性結(jié)構(gòu)：線性結(jié)構(gòu)的元素在物理內(nèi)存上有序/連續(xù)的分布，使其可以使用下標(biāo)(Index)快速訪問，查找復(fù)雜度為O(1)，如：數(shù)組
• 鏈表結(jié)構(gòu)：鏈表結(jié)構(gòu)的元素在物理內(nèi)存上無序/隨機(jī)的分布，當(dāng)前元素保留上一個(gè)或下一個(gè)元素的引用叫單向鏈表，保留上一個(gè)且下一個(gè)元素的引用叫雙向鏈表 ，鏈表中第一個(gè)元素的上一個(gè)索引位置指向最后一個(gè)元素且最后一個(gè)元素的下一個(gè)索引位置指向第一個(gè)元素叫循環(huán)鏈表(簡(jiǎn)單理解成一根繩子頭尾相連成圓)，查詢復(fù)雜度為Ｏ(logn)，如：LinkedList、LinkedHashMap
• 散列結(jié)構(gòu)：

以上是筆者覺得最常見的一些數(shù)據(jù)結(jié)構(gòu)，筆者會(huì)在后續(xù)介紹Collection不同抽象的時(shí)候講解集合每一種API對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)是哪一種，理解這些數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)及優(yōu)缺點(diǎn)有助于讀者在根據(jù)具體的場(chǎng)景下選用是和數(shù)據(jù)結(jié)構(gòu)的API提高性能，當(dāng)然JDK里面還有一些跳表、樹、圖的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，因?yàn)槲恼率墙榻B常用的集合類，所以就不一一介紹了，如果讀者有興趣可以自行學(xué)習(xí)

1.3 接口介紹

1.3.1 接口的語義

在這之前筆者希望讀者對(duì)接口的理解可以上升到一個(gè)邏輯層次，而不是僅僅知道實(shí)現(xiàn)了接口就必須實(shí)現(xiàn)接口的方法，比如Iterable接口是可迭代的語義，那么子類就必須是具備可迭代需求才能實(shí)現(xiàn)該接口，否則就屬于一種錯(cuò)誤的設(shè)計(jì)，再看看JDK中沒有任何方法的Serializable、以及上圖中出現(xiàn)的RandomAccess這些接口的出現(xiàn)本身就是約束著一種邏輯定義，筆者在這里稱之為接口的語義

1.3.2 Iterable接口

集合頂層接口，接口的語義標(biāo)志實(shí)現(xiàn)類是可迭代的（循環(huán)），所有需要被for(String str : strs) 語法迭代的支持都必須實(shí)現(xiàn)此接口(數(shù)組除外)，接口方法就一個(gè)Iterator<T> iterator();此方法返回一個(gè)迭代器(Iterator接口)的實(shí)現(xiàn)類。

1.3.3 Collection接口

幾乎是JAVA所有數(shù)據(jù)結(jié)構(gòu)集合的接口(二元散列數(shù)據(jù)結(jié)構(gòu)除外，如：Map)，接口的語義標(biāo)志實(shí)現(xiàn)類必須為集合，集合的解釋也就是：“一堆東西”。集合里的“東西”，叫作元素(element)，既然是一堆東西而我們目的是要對(duì)這堆東西進(jìn)行操作，自然Collection的接口就需要約束每個(gè)集合都必須有以下方法：

• size(): 集合中元素的個(gè)數(shù)
• contains(Object element): 集合中是否包含某個(gè)元素
• iterator(): 集合的迭代器
• add(Object element):往集合里添加元素
• remove(Object elemnt):從集合里面移除元素

理論上一個(gè)簡(jiǎn)單的集合接口有以上方法就可以正常工作，但是為了操作方便JCF作者Josh Bloch增加了以下幾個(gè)方法的約束：

• isEmpty():集合是否為空
• toArray():轉(zhuǎn)換成數(shù)組
• containsAll(Collection collection):集合是否包含collection變量中的所有元素
• addAll(Collection collection):添加collection中所有元素到當(dāng)前集合
• removeAll(Collection collection):移除所有在collection中的元素
• retainAll(Collection collection):取兩個(gè)集合的交集
• clear():清除集合所有元素

有了以上方法的約束可以讓我們?cè)谑褂眉系臅r(shí)候操作更方便

1.3.4 List接口

介紹了常用數(shù)據(jù)結(jié)構(gòu)，接下來我們來看Collection的第一種集合抽象——有序List列表，List有以上兩種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)： 線性結(jié)構(gòu)(ArrayList)、鏈表結(jié)構(gòu)(LinkedList)，本文我們將贅述線性結(jié)構(gòu)的實(shí)現(xiàn)（ArrayList)，List接口在extends了Collection之后，增加了對(duì)有序列表操作的幾個(gè)方法約束：

• get(int i):獲取i位置的元素
• set(int i,Object element):替換集合中的i位置插入element元素，返回原位置的元素
• add(int i,Object element):集合i位置插入element，i位置以后的元素向后移一位
• remove(int i):移除集合中i位置的元素
• indexOf(Object element):查找element并返回元素在集合的下標(biāo)索引，如果沒有返回-1
• lastIndexOf(Object element):查找element元素最后一次在集合中的下標(biāo)索引，如果沒有返回-1
• listIterator():創(chuàng)建一個(gè)集合的迭代器
• listIterator(int i):從i位置創(chuàng)建一個(gè)List集合的迭代器
• subList(int star,int end):返回當(dāng)前集合的一個(gè)子集，從當(dāng)前集合的start位置到end位置，注意此子集并不是新new出來的對(duì)象，所以對(duì)子集的操作會(huì)影響到當(dāng)前集合。

以上方法都是針對(duì)有序集合的操作，根據(jù)有序集合的特性約束一系列依靠下標(biāo)索引(Index)的操作

1.3.5 RandomAccess接口

前面提到過該接口，此接口沒有任何方法，存在的意義僅僅是為了表示邏輯上的一種語義——實(shí)現(xiàn)了該接口的子類應(yīng)該具有一個(gè)特性：表明其支持快速（通常是固定復(fù)雜度）隨機(jī)訪問。此接口的主要目的是允許一般的算法(二分法、快速排序...)更改其行為，從而在將其應(yīng)用到隨機(jī)或連續(xù)訪問列表時(shí)能提供良好的性能，所以遵循了該接口語義的實(shí)現(xiàn)類使用for(int i=0;i<xx;i++)會(huì)比使用Iterator迭代器速度要快,如：ArrayList根據(jù)下標(biāo)索引直接訪問任何位置的元素。

1.3.6 Serializable接口

此接口沒有任何方法，存在的意義僅僅是為了表示邏輯上的一種語義——實(shí)現(xiàn)類可被序列化的。

1.3.7 Cloneable接口

此接口沒有任何方法，存在的意義僅僅是為了表示邏輯上的一種語義——實(shí)現(xiàn)類可被克隆的。

1.4 常用、重要方法的實(shí)現(xiàn)

介紹完接口之后，我們來看下UML類圖中AbstrctCollection、AbstractList、ArrayList的具體實(shí)現(xiàn)類，在講述過程中筆者會(huì)省去那些非重點(diǎn)的方法，比如toString()、isEmpty()等方法。

1.4.1 AbstractCollection抽象類

作為Collection的抽象類及幾乎所有集合類的父類來說(筆者說的是幾乎，比如Map就非其子類)，理應(yīng)實(shí)現(xiàn)所有Collection接口中約束的最基本方法，但有些約束是要在具體場(chǎng)景下才能根據(jù)具體需求進(jìn)行實(shí)現(xiàn)，如：add()需要把對(duì)象添加到具體的數(shù)據(jù)結(jié)構(gòu)中，可以是數(shù)組(線性)、Node(鏈表)，所以 AbstractCollection中主要實(shí)現(xiàn)了以下方法：

contains(Object var1)方法實(shí)現(xiàn)

 /**
*  方法作用：集合中是否包含var1元素
*  實(shí)現(xiàn)方式：使用迭代器進(jìn)行迭代比對(duì)，如果先相同返回
*/
public boolean contains(Object var1) {
    Iterator var2 = this.iterator();//抽象方法，具體在子類中會(huì)實(shí)現(xiàn)
    if(var1 == null) {
        while(var2.hasNext()) {
            if(var2.next() == null) {
            return true;
            }
        }
    } else {
        while(var2.hasNext()) {
            if(var1.equals(var2.next())) {
            return true;
           }
        }
    }
    return false;
}

toArray()方法實(shí)現(xiàn)

/**
* 方法作用：集合轉(zhuǎn)成數(shù)組
* 實(shí)現(xiàn)方式：new一個(gè)集合大小一致的數(shù)組，然后用集合迭代器迭代復(fù)制到新數(shù)組，這個(gè)地方的復(fù)制
*          使用的Arrays.copy()方法，這個(gè)方法在整個(gè)線性結(jié)構(gòu)的集合里面大量存在，幾乎所
*          所有的集合修改操作都使用到了它，而這個(gè)方法底層的實(shí)現(xiàn)來自于一個(gè)JNI方法，
*          System.arrayCopy(),由于是本地方法所以效率非常高
*/
public Object[] toArray() {
    Object[] var1 = new Object[this.size()];
    Iterator var2 = this.iterator();
    
    for(int var3 = 0; var3 < var1.length; ++var3) {
        if(!var2.hasNext()) {
            return Arrays.copyOf(var1, var3);//線性結(jié)構(gòu)的集合中大量使用的方法
        }
        var1[var3] = var2.next();
    }
    
    /* finishToArray(var1,va2)方法是當(dāng)new的這個(gè)數(shù)組大小不足集合大小時(shí)完成多余的賦值
     * 那么，明明是根據(jù)集合size new出來的數(shù)組為什么會(huì)放不下呢，因?yàn)楹芸赡茉趶?fù)制的過程
     * 中集合被修改了。
     */  
    return var2.hasNext()?finishToArray(var1, var2):var1;
}

add(E var1)方法實(shí)現(xiàn)，前面說過了不同子類有不同的實(shí)現(xiàn)

public boolean add(E var1) {
        throw new UnsupportedOperationException();
}

remove(Object var1)方法實(shí)現(xiàn)

/**
*  方法作用：從集合中移除var1元素
*  實(shí)現(xiàn)方式：獲取迭代器，使用迭代器中的remove刪除元素
*/
 public boolean remove(Object var1) {
    Iterator var2 = this.iterator();//抽象方法，具體在子類中會(huì)實(shí)現(xiàn)
    if(var1 == null) {
        while(var2.hasNext()) {
            if(var2.next() == null) {
                var2.remove();//調(diào)用迭代器的remove
                return true;
            }
        }
    } else {
        while(var2.hasNext()) {
            if(var1.equals(var2.next())) {
                var2.remove();
                return true;
            }
        }
    }
    return false;
}

containsAll(Collections<?> var1);

/**
*  方法作用：集合中是否包含所有var1集合中的元素
*  實(shí)現(xiàn)方式：寫法可以借鑒，如果是你會(huì)這樣寫嗎？是不是代碼整潔一些呢
*/
public boolean containsAll(Collection<?> var1) {
    Iterator var2 = var1.iterator();
    Object var3;
    do {
        if(!var2.hasNext()) {
            return true;
        }

        var3 = var2.next();
    } while(this.contains(var3));//調(diào)用上面的contains()方法，所以是兩層循環(huán)

    return false;
}

addAll(Collection<? extends E> var1)方法實(shí)現(xiàn)

/**
*  方法作用：把var1集合中的所有數(shù)據(jù)添加到集合
*  實(shí)現(xiàn)方式：沒什么好說的~~
*/
public boolean addAll(Collection<? extends E> var1) {
    boolean var2 = false;
    Iterator var3 = var1.iterator();

    while(var3.hasNext()) {
        Object var4 = var3.next();
        if(this.add(var4)) { //調(diào)用上面的add()方法，實(shí)際是子類中實(shí)現(xiàn)的add()方法
            var2 = true;
        }
    }

    return var2;
}

retainAll(Collection<?> var1)

/**
*  方法作用：刪除當(dāng)前集合在var1集合中存在的元素（集合交集，但是會(huì)把原集合數(shù)據(jù)從內(nèi)存刪除）
*  實(shí)現(xiàn)方式：代碼很好懂，不多說，只要?jiǎng)h除過一個(gè)元素 返回True，否則False
*/
public boolean retainAll(Collection<?> var1) {
    boolean var2 = false;
    Iterator var3 = this.iterator();

    while(var3.hasNext()) {
        if(!var1.contains(var3.next())) {
            var3.remove();
            var2 = true;
        }
    }

    return var2;
}

AbstractCollection總結(jié)：雖然抽象類中實(shí)現(xiàn)了很多方法，但實(shí)際還是基于抽象方法之上的，具體的業(yè)務(wù)邏輯都在子類實(shí)現(xiàn)的抽象方法中，而AbstractCollection中實(shí)現(xiàn)的是與業(yè)務(wù)沒關(guān)系的公共代碼，或者說最原始、最基本的實(shí)現(xiàn)，比如：所有查找都是使用的迭代器，實(shí)際上我們之前介紹過RandomAccess接口的語義，所以遵循了該接口語義的實(shí)現(xiàn)類使用for(int i=0;i<xx;i++)會(huì)比使用Iterator迭代器速度要快，后面我們會(huì)看到ArrayList對(duì)contains()方法進(jìn)行了重寫

1.4.2 AbstractList抽象類

indexOf(Object o)方法實(shí)現(xiàn)

/**
*  方法作用：查找元素o在集合中的位置，沒有則返回-1
*  實(shí)現(xiàn)方式：利用迭代器進(jìn)行查詢
*/
public int indexOf(Object o) {
    ListIterator<E> it = listIterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return it.previousIndex();
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return it.previousIndex();
    }
    return -1;
}

iterator()方法實(shí)現(xiàn)，生成按從前到后順序迭代的迭代器

public Iterator<E> iterator() {
    return new AbstractList.Itr();//生成迭代器，即下面的迭代器內(nèi)部類實(shí)現(xiàn)代碼
}

/**
 * 迭代器內(nèi)部類實(shí)現(xiàn)，此迭代器只有next()獲取下一個(gè)元素的方法，所以迭代的順序是從前到后
 */
private class Itr implements Iterator<E> {
    int cursor; //下一個(gè)元素索引
    int lastRet; //調(diào)用next()方法返回對(duì)象的下標(biāo)索引
    int expectedModCount; //模數(shù)：集合每次的修改都會(huì)+1，用來判斷在迭代過程中集合是否修改過，
                          //下面會(huì)會(huì)詳細(xì)介紹
    private Itr() {
        this.cursor = 0; //初始化迭代器的時(shí)候下一個(gè)元素索引從0開始
        this.lastRet = -1;//默認(rèn)-1
        this.expectedModCount = AbstractList.this.modCount;//賦值為集合的模數(shù)
    }

    public boolean hasNext() {
        //如果當(dāng)前索引 != 集合大小 說名還有下一個(gè)
        return this.cursor != AbstractList.this.size();
    }

    public E next() {
        //獲取下一個(gè)的時(shí)候，校驗(yàn)迭代器模數(shù)是否==集合模數(shù)，如果不等于則證明集合在迭代器
        //生成之后被修改過
        this.checkForComodification();
        try {
            int var1 = this.cursor;
            Object var2 = AbstractList.this.get(var1);
            this.lastRet = var1;//var2對(duì)象的下標(biāo)索引
            this.cursor = var1 + 1; //這部分代碼很好理解，返回下一個(gè) 當(dāng)前索引+1
            return var2;
        } catch (IndexOutOfBoundsException var3) {
            this.checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        if(this.lastRet < 0) {
            throw new IllegalStateException();
        } else {
            //校驗(yàn)迭代器模數(shù)是否==集合模數(shù)，如果不等于就說明集合在迭代器生成之后被修改過
            this.checkForComodification();

            try {
                AbstractList.this.remove(this.lastRet);//remove當(dāng)前index的元素
                if(this.lastRet < this.cursor) {
                    --this.cursor; //刪除成功后，下一個(gè)元素為-1
                }
                //重置-1
                this.lastRet = -1;
                //因?yàn)樽隽诵薷募洗笮〉牟僮?，所以重新給模數(shù)賦值
                this.expectedModCount = AbstractList.this.modCount;
            } catch (IndexOutOfBoundsException var2) {
                throw new ConcurrentModificationException();
            }
        }
    }
    
    /**
     * 校驗(yàn)迭代器模數(shù)是否==集合模數(shù)，如果不等于則證明集合在迭代器生成之后被修改過
     * 如果集合被修改過，說名迭代器失效，拋出異常
     */
    final void checkForComodification() {
        if(AbstractList.this.modCount != this.expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
}

listIterator()方法實(shí)現(xiàn)

public ListIterator<E> listIterator(int var1) {
    //校驗(yàn)索引var1是否在0到集合size以內(nèi)，否則IndexOutOfBoundsException
    this.rangeCheckForAdd(var1);
    return new AbstractList.ListItr(var1);
}

/**
 * 迭代器內(nèi)部類實(shí)現(xiàn)，迭代順序隨意的迭代器，并且在迭代過程中可以修改集合
 * 
 */
 private class ListItr extends AbstractList.Itr implements ListIterator<E> {
    ListItr(int var2) {
        super();
        this.cursor = var2;
    }

    public boolean hasPrevious() {
        return this.cursor != 0;//當(dāng)下一個(gè)索引 !=0 的時(shí)候說名還有上一個(gè)
    }
    
    public E previous() { //返回上一個(gè)元素
        this.checkForComodification();

        try {
            int var1 = this.cursor - 1;
            Object var2 = AbstractList.this.get(var1);
            this.lastRet = this.cursor = var1;
            return var2;
        } catch (IndexOutOfBoundsException var3) {
            this.checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public int nextIndex() {
        return this.cursor;//返回下一個(gè)元素的索引
    }

    public int previousIndex() {
        return this.cursor - 1;//返回上一個(gè)元素的索引
    }

    public void set(E var1) {
        if(this.lastRet < 0) {
            throw new IllegalStateException();
        } else {
            this.checkForComodification();

            try {
                AbstractList.this.set(this.lastRet, var1);//把元素var1替換當(dāng)前位置的值
                this.expectedModCount = AbstractList.this.modCount;
            } catch (IndexOutOfBoundsException var3) {
                throw new ConcurrentModificationException();
            }
        }
    }

    public void add(E var1) {
        this.checkForComodification();

        try {
            int var2 = this.cursor;
            AbstractList.this.add(var2, var1);//添加元素，并且把模數(shù)更新
            this.lastRet = -1;
            this.cursor = var2 + 1;
            this.expectedModCount = AbstractList.this.modCount;
        } catch (IndexOutOfBoundsException var3) {
            throw new ConcurrentModificationException();
        }
    }
}    

AbstractList總結(jié)：主要實(shí)現(xiàn)了List接口中的以上3個(gè)方法，注意此處indexOf()仍然使用的是迭代器遍歷的，因?yàn)長(zhǎng)ist的數(shù)據(jù)結(jié)構(gòu)分為線性和鏈表結(jié)構(gòu)，下面我們可以看到線性結(jié)構(gòu)的ArrayList實(shí)現(xiàn)RandomAccess接口后對(duì)indexOf()進(jìn)行了重寫

• Itr迭代器實(shí)現(xiàn)
  　　只能向后迭代，并且在迭代過程中不能對(duì)集合元素進(jìn)行add、set操作，但可以remove

• ListItr迭代器實(shí)現(xiàn)
  　　1.ListIterator和Iterator都有hasNext()和next()方法，可以實(shí)現(xiàn)順序向后遍歷，但是ListIterator有hasPrevious()和previous()方法，可以實(shí)現(xiàn)逆向（順序向前）遍歷。Iterator不可以。
  　　2.ListIterator可以定位當(dāng)前索引的位置，nextIndex()和previousIndex()可以實(shí)現(xiàn)。Iterator沒有此功能。
  　　3.都可實(shí)現(xiàn)刪除操作，但是ListIterator可以實(shí)現(xiàn)對(duì)象的修改，set()方法可以實(shí)現(xiàn)修改，add()可以實(shí)現(xiàn)添加，Iterator僅能遍歷，不能修改。

1.4.3 ArrayList實(shí)現(xiàn)類

private int size;//集合里總共包含多少個(gè)元素,應(yīng)該 <= elementData.length;
private transient Object[] elementData; //這行源碼表示ArrayList底層為數(shù)組實(shí)現(xiàn)，那么既然底層是數(shù)組，怎么實(shí)現(xiàn)擴(kuò)容的集合呢？請(qǐng)看下面這個(gè)grow()方法

 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);//前面提到讓讀者留意的工具類
}

/* 再看看Arrays.copy()方法實(shí)現(xiàn)，其實(shí)是System.arraycopy方法，這個(gè)方法是本地方法，效率會(huì)比較快 */
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends   T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));//底層System.arraycopy()實(shí)現(xiàn)
    return copy;
}

前面說過ArrayList會(huì)對(duì)contains()方法重寫，接下來我們?cè)敿?xì)看下

public boolean contains(Object o) {
    return indexOf(o) >= 0;//調(diào)用的indexOf()方法，我們還記得這個(gè)方法在AbstractList中
                           //使用迭代器實(shí)現(xiàn)過，但是ArrayList又對(duì)其重寫了
}

/* ArrayList已經(jīng)使用for(int i=0;i<size;i++)來實(shí)現(xiàn), 回想下前面我們說過的
 * RandomAccess接口的語義就明白這個(gè)的用意，不記得的童鞋可以回到上面看下
 */
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;
}

get()方法實(shí)現(xiàn)

public E get(int index) {
    rangeCheck(index);//范圍校驗(yàn)，不在0到size內(nèi)就IndexOutOfBoundsException

    return elementData(index);//直接通過數(shù)組下標(biāo)返回值
}

set()方法實(shí)現(xiàn)

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

    E oldValue = elementData(index);//拿出index位置的元素
    elementData[index] = element;//設(shè)置index位置的元素為新elment
    return oldValue;//返回原index位置元素
}

add()方法實(shí)現(xiàn)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);//如果elementData數(shù)組長(zhǎng)度不夠當(dāng)前size+1，就擴(kuò)容
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {//如果elementData還是0，則取minCapacity和默認(rèn)長(zhǎng)度10兩個(gè)數(shù)中的大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //因?yàn)槭翘砑?，所以模?shù)需要加1
    
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);//前面介紹過，如果長(zhǎng)度不夠則擴(kuò)容
}

remove()方法實(shí)現(xiàn)

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

    modCount++; //模數(shù)自增，筆者反復(fù)強(qiáng)調(diào)模數(shù)，因?yàn)檫@是一種防止線程安全的措施
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);//本地方法copy數(shù)組，把index后的所有數(shù)組往前挪一個(gè)位置
    //最后一個(gè)位置置為空，注意看很多JDK源碼中都會(huì)寫到 Help GC或者下面這段話，
    //因?yàn)樵O(shè)置引用為null之后，GC可以檢查到GC Roots 不可達(dá)，從而回收內(nèi)存
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

subList(int fromIndex, int toIndex)方法實(shí)現(xiàn)

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);//校驗(yàn)fromIndex和toIndex是否合法
    return new SubList(this, 0, fromIndex, toIndex);
}

/* 產(chǎn)生一個(gè)當(dāng)前集合從fromIndex位置到toIndex位置的子集合，
 * 這個(gè)地方大家看源碼留意下子集合的產(chǎn)生過程？
 */
private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;//保存父集合的引用
    private final int parentOffset;//上面的fromIndex
    private final int offset;//針對(duì)父集合的偏移量，后續(xù)根據(jù)用戶輸入的index進(jìn)行偏移
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;//默認(rèn)賦值為fromIndex
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }

    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        //其實(shí)就是獲取父集合指定位置的元素，所以子集合并沒有new出新內(nèi)存，這點(diǎn)請(qǐng)讀者理解
        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;
    }

ArrayList總結(jié)：因?yàn)锳rrayList的底層是數(shù)組實(shí)現(xiàn)，所以它是一個(gè)線性的結(jié)構(gòu)，它在內(nèi)存中是一段連續(xù)的地址，所以我們可以通過Index很快的訪問元素，然而我們看到了每add或者remove操作都會(huì)調(diào)用System.arraycopu()復(fù)制改動(dòng)之后的所有元素，所以我們說隨機(jī)插入和刪除操作線性結(jié)構(gòu)沒有鏈表結(jié)構(gòu)效率高（這里請(qǐng)大家注意，后續(xù)講到鏈表結(jié)構(gòu)的時(shí)候會(huì)做一個(gè)對(duì)比，看看是否一定線性結(jié)構(gòu)的效率比較高）

然后請(qǐng)大家注意的是subList()方法，上面有說過subList并非產(chǎn)生一個(gè)新對(duì)象，而是通過使用下標(biāo)偏移量取父類數(shù)組中的元素，也就是說子集合和父集合其實(shí)在內(nèi)存中是一個(gè)集合，所以對(duì)子集合的任何修改將直接影響到父集合，我們很多剛?cè)腴T的童鞋，可能再使用中會(huì)遇到這個(gè)問題，所以在這里提出來

總結(jié)

ArrayList講到這里就已經(jīng)講完了，因?yàn)锳rrayList作為我們JCF框架源碼分析系列的第一集，所以里面著重的介紹了Iterable、Iterator、Collection、AbstractCollection、List、Abstract、RandomAccess等接口或抽象類，后續(xù)文章中如有重復(fù)的就不在贅述。

轉(zhuǎn)載請(qǐng)注明出處：http://www.itdecent.cn/p/9a08cdc8f4be