ArrayList類(lèi)是一個(gè)繼承自AbstractList類(lèi)的變長(zhǎng)數(shù)組雏门，其長(zhǎng)度可以隨著元素?cái)?shù)量的變化而變化。它同時(shí)實(shí)現(xiàn)了List、RandomAccess、Cloneable和Serializable接口硅则。此外，ArrayList允許插入的元素為null株婴，是一個(gè)線(xiàn)程不安全版本的Vector怎虫。

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

所在路徑：\java\util\ArrayList.java

ArrayList類(lèi)繼承關(guān)系圖

一、成員變量

ArrayList類(lèi)的成員變量共7個(gè)困介，大概可以分為四類(lèi)大审。1是默認(rèn)容量（長(zhǎng)度）和最大長(zhǎng)度；2是空數(shù)組實(shí)例座哩；3是當(dāng)前數(shù)組的值和長(zhǎng)度徒扶；最后是常規(guī)的UID。各變量具體的描述如下所示根穷。

/** 默認(rèn)容量為10（List的長(zhǎng)度） */
private static final int DEFAULT_CAPACITY = 10;
/** List的最大長(zhǎng)度（因?yàn)橛行┨摂M機(jī)為head word保留了空間姜骡，所以這個(gè)值減了8） */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/** 空數(shù)組實(shí)例，適用于有參數(shù)的構(gòu)造器（容量傳入為0） */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** 默認(rèn)容量的空數(shù)組屿良，適用于無(wú)參數(shù)的構(gòu)造器（沒(méi)有傳入容量） */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** 存儲(chǔ)List元素的數(shù)組 */
transient Object[] elementData;
/** elementData的長(zhǎng)度 */
private int size;

/** serialVersionUID */
private static final long serialVersionUID = 8683452581122892189L;

EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的區(qū)別主要是供不同的構(gòu)造器使用圈澈，ArrayList類(lèi)的創(chuàng)造者認(rèn)為這是一種規(guī)范：https://blog.csdn.net/weixin_43390562/article/details/101236833

transient關(guān)鍵字修飾elementData是為了在序列化時(shí)不將數(shù)組尾部的空元素也輸入進(jìn)去，而是采取實(shí)現(xiàn)writeObject()方法的方式尘惧，只序列化有值的數(shù)組部分：https://www.cnblogs.com/vinozly/p/5171227.html

二士败、構(gòu)造器

1、無(wú)參構(gòu)造器

直接將一個(gè)空的數(shù)組賦值給elementData褥伴。

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

2谅将、入?yún)槌跏既萘?/h5>

初始化一個(gè)長(zhǎng)度為initialCapacity的數(shù)組。

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

3重慢、入?yún)镃ollection接口的實(shí)現(xiàn)類(lèi)或其子類(lèi)

當(dāng)入?yún)橐粋€(gè)集合接口的實(shí)現(xiàn)類(lèi)或其子類(lèi)時(shí)饥臂，使用toArray()方法進(jìn)行初始化。例如：List<String> stringList = new ArrayList<>(Arrays.asList("1", "2"));

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

三似踱、add()和addAll()

1隅熙、add()

add()方法是ArrayList類(lèi)的核心方法，它可以將元素添加到數(shù)組的尾部或指定位置核芽。用戶(hù)在使用add()方法不需要關(guān)心elementData的長(zhǎng)度囚戚，只要不超過(guò)之前定義的最大長(zhǎng)度，ArrayList會(huì)自動(dòng)對(duì)elementData進(jìn)行擴(kuò)容轧简。

/** 默認(rèn)添加至尾部 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/** 添加至指定位置 */
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++;
}

每次插入數(shù)據(jù)前驰坊，ArrayList都會(huì)計(jì)算當(dāng)前elementData是否需要擴(kuò)容。擴(kuò)容的具體過(guò)程如下：

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

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

擴(kuò)容的動(dòng)作最終由Arrays.copyOf()方法完成（這個(gè)方法我們之前介紹過(guò)哮独，它最終調(diào)用的是System.arraycopy()方法拳芙，實(shí)際上就是數(shù)組元素的逐一拷貝）察藐，數(shù)組的實(shí)際長(zhǎng)度會(huì)增加為原來(lái)的1.5倍。

modCount表示被修改次數(shù)舟扎，在ArrayList的所有涉及結(jié)構(gòu)變化的方法中都增加modCount的值分飞，包括：add()、remove()睹限、addAll()譬猫、removeRange()及clear()方法。這些方法每調(diào)用一次羡疗，modCount的值就加1染服。當(dāng)線(xiàn)程對(duì)ArrayList進(jìn)行遍歷時(shí)，通過(guò)比較modCount和expectModCount的值來(lái)確保循環(huán)不會(huì)因多線(xiàn)程的不安全操作而出錯(cuò)顺囊。

https://blog.csdn.net/qq_24235325/article/details/52450331

當(dāng)newCapacity大于MAX_ARRAY_SIZE時(shí)肌索，會(huì)調(diào)用hugeCapacity()方法，最多返回一個(gè)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;
}

2诚亚、addAll()

addAll()方法可以將一個(gè)集合中的每個(gè)元素的都加入到數(shù)組中，具體的實(shí)現(xiàn)方法基本與add()一致午乓。在copy前站宗，ArrayList會(huì)先調(diào)用目標(biāo)集合的toArray()方法，將其轉(zhuǎn)換為一個(gè)Object類(lèi)型的數(shù)組益愈。

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

四梢灭、remove()和removeAll()

1、remove()

remove()方法被用來(lái)從ArrayList中移除一個(gè)元素蒸其，移除元素的空當(dāng)會(huì)被其他元素有序補(bǔ)齊敏释。如果輸入的參數(shù)是元素的index，ArrayList會(huì)直接用System.arraycopy()對(duì)其進(jìn)行覆蓋摸袁。如果入?yún)⑹且粋€(gè)Object類(lèi)對(duì)象钥顽，ArrayList會(huì)在遍歷數(shù)組后調(diào)用fastRemove()方法。

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

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

入?yún)镺bject類(lèi)對(duì)象的remove()方法會(huì)在第一次遍歷到該對(duì)象時(shí)移除并返回靠汁，此時(shí)ArrayList調(diào)用的是對(duì)象的equals()方法蜂大，必要的時(shí)候這個(gè)方法需要由調(diào)用者進(jìn)行重寫(xiě)。

其中蝶怔，fastRemove()方法的實(shí)現(xiàn)和入?yún)閕ndex的remove()方法是一樣的奶浦，它的源碼為：

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
}

2、removeAll()

removeAll()方法可以移除數(shù)組中所有被包含在輸入集合中的元素踢星，ArrayList采用判斷后再賦值給新數(shù)組的方式澳叉，避免了頻繁的arraycopy操作。

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

與removeAll()對(duì)應(yīng)的是retainAll()方法，這個(gè)方法在調(diào)用fastRemove()方法時(shí)傳入true耳高，將入?yún)⒓现邪脑亓粝聛?lái)并刪除其他元素扎瓶。

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

五所踊、indexOf()和lastIndexOf()

indexOf()和lastIndexOf()方法分別返回輸入元素按從前往后和從后往前兩種順序查找出的數(shù)組下標(biāo)泌枪，如果該元素出現(xiàn)了多次，則只返回按當(dāng)前順序查找到的第一個(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;
}

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

六碌燕、writeObject()和readObject()

由于elementData被transient修飾，不會(huì)在序列化時(shí)被轉(zhuǎn)換出來(lái)继薛，ArrayList自己實(shí)現(xiàn)了writeObject()和readObject()方法修壕。序列化時(shí)，ObjectOutputStream類(lèi)會(huì)通過(guò)反射獲得ArrayList的這兩個(gè)方法遏考，從而實(shí)現(xiàn)只序列化有elementData的有值部分慈鸠。

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

七、subList()

subList()方法會(huì)返回一個(gè)ArrayList的內(nèi)部類(lèi)灌具，這個(gè)類(lèi)同樣繼承自AbstractList青团，只是在起止index上與當(dāng)前ArrayList有所不同。

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

/** 內(nèi)部類(lèi)SubList */
private class SubList extends AbstractList<E> implements RandomAccess

八咖楣、iterator()

iterator()方法同樣返回一個(gè)類(lèi)型為Itr的內(nèi)部類(lèi)督笆，它實(shí)現(xiàn)了Iterator<E>接口。

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

/** 內(nèi)部類(lèi)Itr */
private class Itr implements Iterator<E>

九诱贿、其他

最后娃肿，ArrayList同樣提供了幾個(gè)入?yún)楦黝?lèi)接口實(shí)現(xiàn)的工具方法，用戶(hù)可以自定義操作的規(guī)則珠十。

/** 遍歷并支持函數(shù)式處理 */
public void forEach(Consumer<? super E> action)
/** 有條件移除 */
public boolean removeIf(Predicate<? super E> filter)
/** 全部替換并支持函數(shù)式處理 */
public void replaceAll(UnaryOperator<E> operator)
/** 排序 */
public void sort(Comparator<? super E> c)