一、簡(jiǎn)述

我們知道堤结，數(shù)據(jù)結(jié)構(gòu)中主要有兩種存儲(chǔ)結(jié)構(gòu)，分別是：順序存儲(chǔ)結(jié)構(gòu)（線性表）鸭丛、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表）竞穷，在Java中，對(duì)這兩種結(jié)構(gòu)分別進(jìn)行實(shí)現(xiàn)的類(lèi)有：

• 順序存儲(chǔ)結(jié)構(gòu)：ArrayList鳞溉、Vector瘾带、Stack
• 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：LinkedList、Queue

二熟菲、歸納

• 繼承了AbstractList抽象類(lèi)看政，實(shí)現(xiàn)了List接口，底層基于數(shù)組實(shí)現(xiàn)容量大小動(dòng)態(tài)變化抄罕，允許null的存在允蚣。
• 實(shí)現(xiàn)了RandomAccess, Cloneable, java.io.Serializable接口，所以支持快速訪問(wèn)呆贿、復(fù)制(拷貝)嚷兔、序列化。
• 當(dāng)使用無(wú)參數(shù)構(gòu)造函數(shù)創(chuàng)建ArrayList對(duì)象時(shí)，ArrayList對(duì)象中的數(shù)組初始長(zhǎng)度為0（是一個(gè)空數(shù)組）冒晰，然后當(dāng)進(jìn)行#add()操作添加一個(gè)元素的時(shí)候同衣，如果當(dāng)前是一個(gè)空數(shù)組，則初始化一個(gè)長(zhǎng)度為10的數(shù)組壶运。
• ArrayList的擴(kuò)容策略是每次都增加當(dāng)前數(shù)組長(zhǎng)度的一半乳怎，如果還不滿足則增加要當(dāng)前所需的數(shù)組長(zhǎng)度。
• ArrayList的擴(kuò)容方式是直接創(chuàng)建一個(gè)新的數(shù)組前弯，并將數(shù)據(jù)拷貝到新數(shù)組中。
• 查和改操作速度非筹牛快【時(shí)間復(fù)雜度：O(1)】,增和刪操作相對(duì)較慢【時(shí)間復(fù)雜度：最快O(1)最慢O(n)】恕出。
• ArrayList的操作單線安全，多線程不安全违帆，多線程中可以采用Collections.synchronizedList或者CopyOnWriteArrayList等操作浙巫。

三、分析

1刷后、接口

在分析ArrayList源碼之前的畴，我們先來(lái)看看集合的接口--List。

public interface List<E> extends Collection<E> {
    ...
    // 增
    boolean add(E e);
    void add(int index, E element);
    // 刪
    boolean remove(Object o);
    E remove(int index);
    // 改
    E set(int index, E element);
    // 查
    E get(int index);
    ...
}

在上述接口中尝胆，我只抽取了比較重要的幾個(gè)方法丧裁，然后以此為后續(xù)重點(diǎn)分析目標(biāo)，其List接口對(duì)應(yīng)的源碼中遠(yuǎn)不止上述幾個(gè)方法含衔，有興趣的同學(xué)可以自行翻閱煎娇。

2、成員變量

在ArrayList的源碼中,其成員變量并不多,所以在此把它們都一一列出贪染。

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

    // 序列化唯一表示UID
    private static final long serialVersionUID = 8683452581122892189L;

    // 默認(rèn)初始化數(shù)組容量
    private static final int DEFAULT_CAPACITY = 10;

    // 空數(shù)組實(shí)例缓呛，在不同的構(gòu)造函數(shù)中使用到
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 空數(shù)組實(shí)例，在無(wú)參構(gòu)造方法中使用
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 存儲(chǔ)ArrayList元素的數(shù)組緩沖區(qū)杭隙，其中transient的作用是防止被序列化的
    transient Object[] elementData;

    // ArrayList的大小哟绊，其實(shí)就是其內(nèi)部維護(hù)的數(shù)組存儲(chǔ)元素的數(shù)量
    private int size;
    ...
}

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

構(gòu)造函數(shù)是一個(gè)類(lèi)最常見(jiàn)的痰憎，同樣也是最常被使用到的票髓，接著我們分析Arraylist的三個(gè)不同的構(gòu)造函數(shù)。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...
    /**
     * 無(wú)參構(gòu)造函數(shù)
     */
    public ArrayList() {
        // 給elementData數(shù)組賦值為一個(gè)空數(shù)組實(shí)例
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 有參構(gòu)造函數(shù)
     *
     * @param initialCapacity 數(shù)組的容量
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {// 當(dāng)initialCapacity為負(fù)數(shù)的時(shí)候?yàn)榉欠ㄐ攀猓瑨伋霎惓?            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }
    
    /**
     * 有參構(gòu)造函數(shù)
     * 構(gòu)造包含指定元素的列表集合
     *
     * @param c 集合元素
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 判斷其是不是Object對(duì)象炬称，如果不是將其轉(zhuǎn)換為Object對(duì)象數(shù)組
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 給elementData數(shù)組賦值為一個(gè)空數(shù)組實(shí)例
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    ...
}

4、增

ArrayList的增操作有兩種實(shí)現(xiàn)涡拘，分別為add(E e)和add(int index, E element)玲躯，下面我們來(lái)分析其兩種實(shí)現(xiàn)。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...
    /**
     * 將元素e添加到列表中
     *
     * @param e 元素e
     * @return 返回true標(biāo)識(shí)添加成功
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    /**
     * 將元素element添加到指定的索引位置
     *
     * @param index 要插入指定元素的索引
     * @param element 要插入的元素
     * @throws IndexOutOfBoundsException 如果索引角標(biāo)不合法，則拋出索引越界異常
     */
    public void add(int index, E element) {
        // 如果索引角標(biāo)不合法跷车，則拋出索引越界異常
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        // 確保數(shù)組有足夠的容量棘利，
        ensureCapacityInternal(size + 1);  
        // 從指定的源數(shù)組指定的位置開(kāi)始，將數(shù)組復(fù)制到目標(biāo)數(shù)組的指定位置朽缴，且規(guī)定要復(fù)制的長(zhǎng)度
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        // 更新數(shù)組索引為index的元素值
        elementData[index] = element;
        // 維護(hù)size
        size++;
    }
    
    /**
     * 復(fù)制數(shù)組善玫，注意src【源數(shù)組】和dest【目標(biāo)數(shù)組】可為同一數(shù)組
     *
     * @param src    源數(shù)組
     * @param srcPos 源數(shù)組中的起始索引位置
     * @param dest   目標(biāo)數(shù)組
     * @param dest   目標(biāo)數(shù)組中的起始索引位置
     * @param length 要copy的數(shù)組的長(zhǎng)度
     */
    public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)
    
    /**
     * 計(jì)算并擴(kuò)大最小的容器體積
     *
     * @param minCapacity  容積，其實(shí)就是數(shù)組的容量大小
     */
    private void ensureCapacityInternal(int minCapacity) {
        // 判斷當(dāng)前數(shù)組elementData是否為空數(shù)組
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 獲取當(dāng)前最大的容積
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 看是否需要進(jìn)行擴(kuò)容操作
        ensureExplicitCapacity(minCapacity);
    }
    
    /**
     * 看是否需要進(jìn)行擴(kuò)容操作
     *
     * @param minCapacity  容積密强，其實(shí)就是數(shù)組的容量大小
     */
    private void ensureExplicitCapacity(int minCapacity) {
        // 這是ArrayList的父類(lèi)AbstractList中定義了一個(gè)int型的屬性
        // 在此用來(lái)記錄了ArrayList結(jié)構(gòu)性變化的次數(shù)
        modCount++;
        // 當(dāng)該if成立時(shí)茅郎，說(shuō)明當(dāng)前數(shù)組(容器)的空間不夠了，需要擴(kuò)容或渤，所以調(diào)用grow()方法
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);// 擴(kuò)容操作
    }
    
    /**
     * 增加容量以確保它至少可以容納由最小容量參數(shù)指定的元素?cái)?shù)目
     *
     * @param minCapacity 容積系冗，其實(shí)就是數(shù)組的容量大小
     */
    private void grow(int minCapacity) {
        // 獲取原始容積
        int oldCapacity = elementData.length;
        // (oldCapacity >> 1)等價(jià)于(oldCapacity / 2)
        // 這里就是擴(kuò)容到原始容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果擴(kuò)容1.5倍后還不滿足，則直接賦值到其所需的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果擴(kuò)容的容量大于整型的最大值薪鹦，則進(jìn)行異常處理或者賦值為整型最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 調(diào)用Arrays.copyOf()創(chuàng)建一個(gè)新的數(shù)組并將數(shù)據(jù)拷貝到新數(shù)組中掌敬，最后讓elementData進(jìn)行引用
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    /**
     * 判斷minCapacity是否溢出
     *
     * @param minCapacity 容積，其實(shí)就是數(shù)組的容量大小
     */
    private static int hugeCapacity(int minCapacity) {
        // 判斷minCapacity是否小于零池磁，小于則拋出異常
        if (minCapacity < 0) throw new OutOfMemoryError();
        // 判斷minCapacity是否超過(guò)整型的邊界值從而進(jìn)行賦值
        return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
    }
    ...
}

5奔害、刪

ArrayList的刪操作有兩種實(shí)現(xiàn)，分別是remove(int index)和remove(Object o)地熄，下面我們來(lái)分析其兩種實(shí)現(xiàn)华临。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...
    /**
     * 刪除索引為index的元素并返回
     *
     * @param index 要?jiǎng)h除的索引
     * @return 返回刪除的元素
     * @throws IndexOutOfBoundsException 拋出索引角標(biāo)越界異常
     */
    public E remove(int index) {
        // 判斷索引是否合法性
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        // 這是ArrayList的父類(lèi)AbstractList中定義了一個(gè)int型的屬性
        // 在此用來(lái)記錄了ArrayList結(jié)構(gòu)性變化的次數(shù)
        modCount++;
        // 獲取要?jiǎng)h除的元素
        E oldValue = (E) elementData[index];
        // 在執(zhí)行刪除操作時(shí)數(shù)組需要移動(dòng)的元素個(gè)數(shù)
        int numMoved = size - index - 1;
        // (numMoved > 0)成立則將數(shù)組進(jìn)行前移copy
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        // 因?yàn)閿?shù)組有可能進(jìn)行了整個(gè)前移1位，所以將最后一個(gè)索引對(duì)應(yīng)的值置空端考，從而降低GC
        elementData[--size] = null; 
        // 返回要?jiǎng)h除的元素
        return oldValue;
    }
    
    /**
     * 刪除元素o银舱，并且返回是否有效刪除
     *
     * @param o 元素將從此列表中刪除(如果存在)
     * @return 如果存在該元素將其刪除并返回true，否則返回false
     */
    public boolean remove(Object o) {
        // 這里把空和非空進(jìn)行區(qū)分跛梗，空的話用“==”判斷寻馏，非空用“equals”判斷
        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;
    }
    
    /**
     * 可以復(fù)用的方法
     */
    private void fastRemove(int index) {
        // 這是ArrayList的父類(lèi)AbstractList中定義了一個(gè)int型的屬性
        // 在此用來(lái)記錄了ArrayList結(jié)構(gòu)性變化的次數(shù)
        modCount++;
        // 在執(zhí)行刪除操作時(shí)數(shù)組需要移動(dòng)的元素個(gè)數(shù)
        int numMoved = size - index - 1;
        // (numMoved > 0)成立則將數(shù)組進(jìn)行前移copy
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        // 因?yàn)閿?shù)組有可能進(jìn)行了整個(gè)前移1位，所以將最后一個(gè)索引對(duì)應(yīng)的值置空核偿，從而降低GC
        elementData[--size] = null;
    }

    ...
}

6诚欠、改

ArrayList的改操作有一種實(shí)現(xiàn)，對(duì)應(yīng)的是set(int index, E element)漾岳，下面我們來(lái)分析這種實(shí)現(xiàn)轰绵。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...
    /**
     * 修改索引角標(biāo)為index的元素值
     *
     * @param index 要修改的索引坐標(biāo)
     * @param element 修改后存儲(chǔ)的元素值
     * @return 返回修改前的元素值
     * @throws IndexOutOfBoundsException 拋出索引角標(biāo)越界異常
     */
    public E set(int index, E element) {
        // 判斷索引是否合法性
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        // 獲取原本index的元素值
        E oldValue = (E) elementData[index];
        // 將其替換成新的元素值
        elementData[index] = element;
        // 返回修改前的元素值
        return oldValue;
    }
    ...
}

7、查

ArrayList的查操作有一種實(shí)現(xiàn)尼荆，對(duì)應(yīng)的是get(int index)左腔，下面我們來(lái)分析這種實(shí)現(xiàn)。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...
    
    /**
     * 查找索引角標(biāo)為index的元素值
     *
     * @param index 要修改的索引坐標(biāo)
     * @return 返回查找到的索引為index的元素值
     * @throws IndexOutOfBoundsException 拋出索引角標(biāo)越界異常
     */
    public E get(int index) {
        // 判斷索引是否合法性
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        // 返回查找到的索引為index的元素值
        return (E) elementData[index];
    }
    ...
}

四捅儒、ArrayList線程安全處理

1液样、Collections.synchronizedList

最常用的方法是通過(guò) Collections 的 synchronizedList 方法將 ArrayList 轉(zhuǎn)換成線程安全的容器后再使用振亮。

List<Object> list =Collections.synchronizedList(new ArrayList<Object>);

2、CopyOnWriteArrayList

使用線程安全的 CopyOnWriteArrayList 代替線程不安全的 ArrayList鞭莽。

List<Object> list1 = new CopyOnWriteArrayList<Object>();