ArrayList簡(jiǎn)介

ArrayList 是 Java 集合框架中比較常用的數(shù)據(jù)結(jié)構(gòu)了速和。ArrayList是可以動(dòng)態(tài)增長(zhǎng)和縮減的索引序列意蛀，內(nèi)部封裝了一個(gè)動(dòng)態(tài)再分配的Object[]數(shù)組

這里我們可以看到ArrayList繼承抽象類AbstractList，實(shí)現(xiàn)了 List 接口健芭，同時(shí)還實(shí)現(xiàn)了 RandomAccess、Cloneable秀姐、Serializable 接口慈迈，所以ArrayList 是支持快速訪問、復(fù)制省有、序列化的痒留。

主要成員變量

    // 底層存儲(chǔ)元素的數(shù)組
    transient Object[] elementData; 
    // ArrayList的實(shí)際大小
    private int size;

注意：size 才是 elementData數(shù)組中實(shí)際的元素個(gè)數(shù)，而 elementData.length 為數(shù)組的容量蠢沿，表示最多可以容納多少個(gè)元素伸头。

    // ArrayList的默認(rèn)初始化容量
    private static final int DEFAULT_CAPACITY = 10;

ArrayList的默認(rèn)初始容量大小為 10。

    // 記錄對(duì)List操作的次數(shù)
    protected transient int modCount = 0;

這個(gè)變量是定義在 AbstractList 中的舷蟀，主要使用是在 Iterator恤磷，目的是防止在List在迭代的過程中被修改。

    // 空的Object類型數(shù)組
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 空的Object類型數(shù)組
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

兩個(gè)空的數(shù)組有什么區(qū)別呢野宜？簡(jiǎn)單來講就是第一次添加元素（使用add方法）時(shí)知道elementData是從空的構(gòu)造函數(shù)還是有參構(gòu)造函數(shù)被初始化的扫步。以便確認(rèn)下一步的擴(kuò)容機(jī)制。

構(gòu)造函數(shù)

ArrayList類共有三種構(gòu)造函數(shù)：

• 無參構(gòu)造函數(shù)
• 帶有參數(shù)為初始容量initialCapacity的構(gòu)造函數(shù)
• 帶有參數(shù)為Collection集合的構(gòu)造函數(shù)

1匈子、無參構(gòu)造函數(shù)

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

注意：雖然在源碼的注釋中說該構(gòu)造函數(shù)構(gòu)造一個(gè)容量大小為 10 的空的ArrayList河胎，但實(shí)際上構(gòu)造函數(shù)只是給 elementData 賦值了一個(gè)空的數(shù)組（DEFAULTCAPACITY_EMPTY_ELEMENTDATA），在第一次向ArrayList添加元素時(shí)容量才擴(kuò)大至10的虎敦。

2游岳、帶有參數(shù)為初始容量initialCapacity的構(gòu)造函數(shù)

    public ArrayList(int initialCapacity) {
        // 如果initalCapacity大于0政敢，直接創(chuàng)建一個(gè)長(zhǎng)度Object數(shù)組賦值為elementData；
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        }
        // 如果initalCapcity等于0胚迫，直接將空數(shù)組EMPETY_ELEMENTDATA復(fù)制給elementData
        else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        }
        // 如果initalCapcity小于于0喷户，則拋出異常IllegalArgumentException
        else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

當(dāng) initialCapacity 為0時(shí)則是把 EMPTY_ELEMENTDATA 賦值給 elementData。 當(dāng) initialCapacity 大于零時(shí)初始化一個(gè)大小為 initialCapacity 的 object 數(shù)組并賦值給 elementData晌区。

3摩骨、帶有參數(shù)為Collection集合的構(gòu)造函數(shù)

   public ArrayList(Collection<? extends E> c) {
        // 將 Collection 轉(zhuǎn)化為數(shù)組并賦值給elementData
        elementData = c.toArray();
        // 把elementData中元素的個(gè)數(shù)賦值給size并判斷其是否為0
        if ((size = elementData.length) != 0) {
            // 如果 size 不為零，則判斷 elementData 的 class 類型是否為 Object[]朗若，不是的話則做一次轉(zhuǎn)換恼五。
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } 
        // 如果 size 為零，則把 EMPTY_ELEMENTDATA 賦值給 elementData哭懈，相當(dāng)于new ArrayList(0)灾馒。
        else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

該構(gòu)造方法主要就是將Collection集合的實(shí)現(xiàn)類轉(zhuǎn)換為ArrayList。

主要操作方法

add方法（添加單個(gè)元素）

    public boolean add(E e) {
        // 先確認(rèn)ArrayList集合容量大小
        ensureCapacityInternal(size + 1);
        // 先給elementData中size位置賦值為e遣总，然后size自增 
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
    // 如果elementData為默認(rèn)的空數(shù)組睬罗，則給minCapacity賦值為初始的默認(rèn)容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // modCount自增，并確定容量大于數(shù)組的長(zhǎng)度
    ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
    // modCount自增旭斥，修改次數(shù)加1
    modCount++;
    // 如果minCapacity超過了數(shù)組長(zhǎng)度容达，則進(jìn)行擴(kuò)容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
    }

上述三個(gè)函數(shù)的調(diào)用關(guān)系很簡(jiǎn)單，也很清楚垂券。

• 在add方法中花盐，每次添加元素到ArrayList中時(shí)都會(huì)先確認(rèn)下集合容量大小，然后將size位置的元素賦值為e菇爪，size再進(jìn)行自增算芯。
• 在ensureCapacityInternal方法中先對(duì)elementData進(jìn)行判斷 ，如果elementData為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是10凳宙。這就是 EMPTY_ELEMENTDATA 與 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的區(qū)別所在熙揍。同時(shí)也驗(yàn)證了上面的說法：使用無參構(gòu)造函數(shù)時(shí)是在第一次添加元素時(shí)初始化容量為10 。
• ensureExplicitCapacity 方法中首先對(duì)modCount 自增1氏涩，記錄操作次數(shù)届囚，然后如果 minCapacity 大于 elementData 的長(zhǎng)度，則對(duì)集合進(jìn)行擴(kuò)容是尖。顯然當(dāng)?shù)谝淮翁砑釉貢r(shí) elementData 的長(zhǎng)度為零奖亚。那我們來看看 grow 函數(shù)。

    private void grow(int minCapacity) {
    // ArrayList的舊容量為數(shù)組長(zhǎng)度
    int oldCapacity = elementData.length;
    // 將新容量賦值為原容量的1.5倍（左移一位相當(dāng)于除以二）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果此時(shí)新容量還是小于添加元素后的容量析砸，則將新容量直接賦值為添加元素后的容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果此時(shí)新容量大于數(shù)組的最大大小昔字，則返回上限最大的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 把舊的數(shù)組elementData拷貝到新的elementData，并將容量設(shè)置為newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

默認(rèn)將list的容量擴(kuò)容至原來容量的 1.5 倍。但是擴(kuò)容之后也不一定適用作郭，有可能太小陨囊，有可能太大。所以才會(huì)有下面兩個(gè) if 判斷夹攒。如果1.5倍太小的話蜘醋，則將增加元素的容量大小賦值給newCapacity，如果1.5倍太大或者我們需要的容量太大咏尝，則調(diào)用hugeCapacity函數(shù)压语，給newCapacity賦一個(gè)合適的值。最后將原數(shù)組中的數(shù)據(jù)復(fù)制到大小為 newCapacity 的新數(shù)組中编检，并將新數(shù)組賦值給 elementData胎食。

    private static int hugeCapacity(int minCapacity) {
        // 如果minCapacity小于0，就拋出異常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 如果此時(shí)增加元素后得minCapacity大于數(shù)組的最大長(zhǎng)度就返回整數(shù)最大值允懂，否則返回?cái)?shù)組最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add方法（批量添加厕怜，在指定位置添加）

public void add(int index, E element) {
    // 檢查index是否越界
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

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

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

這三個(gè)方法基本思路與上述add方法基本思路是一致，博主這里就不再贅述了蕾总。

remove方法

public E remove(int index) {
    // 檢查index是否越界粥航，如果越界則拋出異常
    rangeCheck(index);
    // modCount自增，修改次數(shù)加一
    modCount++;
    // 獲取elementData在index位置的值
    E oldValue = elementData(index);
    // 獲取后移的位置長(zhǎng)度
    int numMoved = size - index - 1;
    // 如果大于零生百，則調(diào)用System.arraycopy方法完成數(shù)組移動(dòng)
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // size自減递雀，并將elementData索引值為size的元素引用賦值為空，讓GC對(duì)他進(jìn)行回收
    elementData[--size] = null; 
    // 返回index位置的值
    return oldValue;
}

當(dāng)我們調(diào)用 remove(int index) 時(shí)蚀浆，首先會(huì)檢查 index 是否合法缀程，然后再判斷要?jiǎng)h除的元素是否位于數(shù)組的最后一個(gè)位置。如果 index 不是最后一個(gè)蜡坊，就再次調(diào)用 System.arraycopy() 方法拷貝數(shù)組。說白了就是將從 index + 1 開始向后所有的元素都向前挪一個(gè)位置赎败。然后將數(shù)組的最后一個(gè)位置空秕衙，size - 1。如果 index 是最后一個(gè)元素那么就直接將數(shù)組的最后一個(gè)位置空僵刮，size - 1即可据忘。

public boolean remove(Object o) {
    // 如果o為空，則查找數(shù)組中為空的索引搞糕，并調(diào)用fastRemove方法進(jìn)行刪除勇吊，并返回true
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    }
    // 如果o不為空，則查找數(shù)組中與該元素相等的索引窍仰，并調(diào)用fastRemove方法進(jìn)行刪除汉规，并返回true 
    else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    // 如果list中不存在則返回false
    return false;
}

下面我們?cè)诳磃astRemove方法，fastRemove方法相較于remove（int index）方法少了一步對(duì)index的判斷针史，因?yàn)閞emove（Object o）就是在數(shù)組中進(jìn)行查詢一定是合法的晶伦，所以在fastRemove中沒必要對(duì)index進(jìn)行判斷。

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
}

get方法

public E get(int index) {
        // 檢查index是否合法啄枕，是否越界
        rangeCheck(index);
        // 利用數(shù)組的特點(diǎn)婚陪，直接訪問數(shù)組中該索引位置上的元素
        return elementData(index);
}

總結(jié)

• ArrayList可以存放null。
• ArrayList本質(zhì)上就是一個(gè)elementData數(shù)組频祝。
• ArrayList區(qū)別于數(shù)組的地方在于能夠自動(dòng)擴(kuò)展大小泌参，其中關(guān)鍵的方法就是gorw()方法。
• ArrayList中removeAll(collection c)和clear()的區(qū)別就是removeAll可以刪除批量指定的元素常空，而clear是全是刪除集合中的元素沽一。
• ArrayList由于本質(zhì)是數(shù)組，所以它在數(shù)據(jù)的查詢方面會(huì)很快窟绷，而在插入刪除這些方面锯玛，性能下降很多，有移動(dòng)很多數(shù)據(jù)才能達(dá)到應(yīng)有的效果
• ArrayList實(shí)現(xiàn)了RandomAccess兼蜈，所以在遍歷它的時(shí)候推薦使用for循環(huán)攘残。

最后

歡迎關(guān)注公眾號(hào)：前程有光，領(lǐng)取一線大廠Java面試題總結(jié)+各知識(shí)點(diǎn)學(xué)習(xí)思維導(dǎo)+一份300頁pdf文檔的Java核心知識(shí)點(diǎn)總結(jié)为狸！