實現(xiàn)List接口的重要集合源碼分析

List接口是類集Collection下一個比較重要的接口探遵，它的下面有很多我們常用的實現(xiàn)類淌喻，而我們這次主要是介紹它的三個重要實現(xiàn)類！

ArrayList（底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組僚楞，線程不安全）
LinkedList（底層數(shù)據(jù)結(jié)構(gòu)是鏈表勤晚，線程不安全）
Vector（底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，線程安全）

ArrayList分析

ArrayList類擴展了AbstractList并實現(xiàn)了List接口泉褐。它支持隨需要而增長的動態(tài)數(shù)組赐写，也就是說可以動態(tài)地增加或減少其大小。它的底層是一個數(shù)組膜赃，創(chuàng)建的時候有著原始的大小挺邀，當(dāng)超過了它的大小，類集自動增大。當(dāng)對象被刪除后端铛，數(shù)組就可以縮小泣矛。

默認屬性

ArryList的默認有幾個屬性，其中包含了默認的數(shù)組大小禾蚕，定義為空返回的數(shù)組您朽，以及默認返回的數(shù)組，還有實際數(shù)組大小的變量换淆。我們先理清楚就比較能明白后面的擴容機制

//數(shù)組默認的大小
private static final int DEFAULT_CAPACITY = 10;
//當(dāng)ArrayList指定數(shù)組容量為0的時候哗总，返回的數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//默認返回的，只要不是指定為0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//保存添加到ArrayList的元素倍试，當(dāng)?shù)谝淮翁砑拥紸rrayList中的時候就會進行擴容
transient Object[] elementData;
//ArrayList的實際大小
private int size;

為了方便讯屈，transient Object[] elementData這個數(shù)組下面我會簡稱為操作數(shù)組，也就是我們實際進行操作的县习。

構(gòu)造方法

上面我們也了解到了ArrayList定義的幾個屬性涮母，下面我們來介紹關(guān)于ArrayList初始化的時候三個構(gòu)造方法！

第一個構(gòu)造方法

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

我們可以指定ArrayList的初始大小躁愿，如果大于0就是先對我們用來添加元素的數(shù)組進行初始化叛本；如果為0就是我們上面上面說的，返回數(shù)組容量為0的數(shù)組攘已；如果小于0炮赦，那就給你異常了呵呵。

第二個構(gòu)造方法

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

這是一個空構(gòu)造方法样勃，我們的操作數(shù)組就用默認返回的數(shù)組。

第三個構(gòu)造方法

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

這是一個定義了構(gòu)造一個包含指定 collection 的元素的列表性芬，這些元素是按照該 collection 的迭代器返回它們的順序排列的峡眶。？是任意類的意思植锉，E是我們指定的類型辫樱，泛型，也就是繼承了Collection的集合俊庇。

我們將集合轉(zhuǎn)換成數(shù)組狮暑，如果長度等于0還是返回容量為0的數(shù)組，如果不是就調(diào)用Arrays.copyOf進行復(fù)制給我們的ArrayList操作數(shù)組辉饱。

常用方法分析

ArrayList的方法有很多搬男，但是我們只要從常見的增刪改查一步一步分析，就可以了解了底層很多的實現(xiàn)機制彭沼！

增加方法

增加方法有兩個缔逛，一個是直接添加，一個是按角標(biāo)進行添加！

直接添加 add(E e)

首先我們來看看它的增加方法褐奴，下面這個增加方法按脚，就是直接增加了一個元素。它首先是嘗試容量+1敦冬，也就是分析對我們的容量有沒有必要加1辅搬，這是為了防止數(shù)組越界！然后就是對我們的操作數(shù)組進行元素的添加脖旱，然后返回true堪遂！

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

可以看到我們用到了一個確認容量大小的方法，我們順著源碼去看這個方法夯缺≡槭希可以看到，這是三個連串使用的方法踊兜！我們首先是進行了下面源碼中的第二個方法竿滨，然后在方法體里面調(diào)用了第一個方法并將返回結(jié)果作為第三個方法的參數(shù)，來調(diào)用第三個方法捏境。

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
        }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

簡單的分析它們進行了什么的操作

如果我們操作數(shù)組不等于默認數(shù)組于游，返回我們實際大小加1，這是需要擴容了垫言！如果等于的話贰剥，返回與默認容量較大的那個數(shù)，因為我們下面要進行判斷筷频，我們?nèi)绻M行擴容總不能擴到比默認還小吧蚌成！
然后就是minCapacity - elementData.length > 0這一步，如果加1操作后的容量大于我們操作數(shù)組的長度的話凛捏，調(diào)用grow方法進行擴容担忧！傳入的參數(shù)就是我們的最小需要的擴容大小坯癣！

那么就到了我們的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);
    }

我們進行了數(shù)組的大小擴容瓶盛，int newCapacity = oldCapacity + (oldCapacity >> 1);，默認就是擴容1.5倍示罗！如果擴容后小于我們所需要的最小容量那么直接就用我們的最小容量惩猫，下面同時還進行了一些邊界處理。最后調(diào)用我們的Arrays.copyOf進行對原來的操作數(shù)組進行復(fù)制到擴容后的新數(shù)組蚜点！

hugeCapacity方法

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

至于為什么最大數(shù)組長度要設(shè)為為Integer.MAX_VALUE - 8轧房，在后面面試題分析會介紹！

角標(biāo)添加add(int index, E element)

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

首先進行我們調(diào)用了rangeCheckForAdd(index);進行了角標(biāo)檢查禽额，防止出現(xiàn)了越界等操作锯厢！如果就是調(diào)用了我們上面一樣的要不要嘗試容量加1皮官，也就是判斷容量是否足夠！然后直接就進行了數(shù)組的復(fù)制操作实辑，直接復(fù)制大小為角標(biāo)加1的數(shù)據(jù)部分捺氢，然后再進行數(shù)組的添加元素和實際大小加1！

System.arraycopy（...）底層是native修飾的方法剪撬，也就是調(diào)用我們的C++函數(shù)來進行復(fù)制的摄乒！

移除方法

其實ArrayList的重要點也就是我們的擴容機制，其他的一些方法残黑，但是可以通過閱讀源碼可以輕松理解的馍佑。移除方法可以通過角標(biāo)和元素來移除

通過角標(biāo)

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

進行的操作有：

調(diào)用rangeCheck邊界檢查
獲取要刪除的元素，用于返回
如果角標(biāo)后面還有元素梨水，對后面的元素進行復(fù)制拭荤，也就是后面的元素都向前移以為
數(shù)組實際大小-1，調(diào)用GC

通過元素

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

這個方法看起來很簡單疫诽，就是遍歷舅世，如果找到與我們要刪除的元素相等的話，調(diào)用fastRemove方法奇徒，然后返回true雏亚；如果遍歷后沒有找到要刪除的元素的話，那么就返回false摩钙，刪除失敯盏汀！所以我們下面具體看一下fastRemove方法胖笛。

    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
    }

這個方法就是上面的remove的閹割版网持，實現(xiàn)的功能都一樣！

設(shè)置方法

檢查角標(biāo)长踊，替換舊的元素翎碑，并返回舊的元素。

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

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

查詢方法

檢查角標(biāo)之斯，如果沒有越界就返回該值。

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

        return elementData(index);
    }

面試題分析

這里選了比較常見的三道面試題遣铝，通過我們上面的源碼都可以輕松的分析了佑刷！

1、ArrayList擴容機制是怎么樣的酿炸？詳細說一下瘫絮。

我們在上面分析了，首先是進行判斷一下是否需要容量加1操作填硕，防止數(shù)組越界麦萤，定義我們所需最少的容量大新贡睢！然后就是再判斷是否需要擴容壮莹。如果需要擴容的話翅帜，就會增加老數(shù)組的1.5倍，如果增加后大小還是小于我們的所需要的最小容量命满，那么擴容的大小就會改為我們的所需的最小容量大欣缘巍！如果超過ArrayList允許的最大長度Integer.MAX_VALUE(2^31-1)胶台，那么新數(shù)組長度為Integer.MAX_VALUE歼疮，否則為Integer.MAX_VALUE - 8。（為什么需要進行-8呢诈唬？是因為對象標(biāo)頭大小是不能超過8個字節(jié)的韩脏，我們可以默認它就是8，所有留了這么一個8字節(jié)大兄酢赡矢！具體的話可以看這里）

2、在索引中ArrayList的增加或者刪除某個對象的運行過程效率很低嗎愚屁？解釋一下為什么济竹？

效率是很低，因為我們也看到了霎槐，無論是刪除還是增加觸發(fā)擴容機制的話送浊，都是在底層調(diào)用System.copyOf()方法進行數(shù)組的復(fù)制或者移位操作。

增加元素時丘跌，我們要把要增加位置及以后的所有元素都往后移一位袭景，先騰出一個空間，然后再進行添加闭树。
刪除某個元素時耸棒，我們也要把刪除位置以后的元素全部元素往前挪一位，通過覆蓋的方式來刪除报辱。

3与殃、如何復(fù)制某個ArrayList到另一個ArrayList中去？

下面就是把某個ArrayList復(fù)制到另一個ArrayList中去的幾種技術(shù)：

使用clone()方法碍现，比如ArrayList newArray = oldArray.clone();
使用ArrayList構(gòu)造方法幅疼，比如：ArrayList myObject = new ArrayList(myTempObject);
使用Collections的copy方法。

注意1和2是淺拷貝(shallow copy)昼接。這里方法1是所有Object對象都有的爽篷；方法2的構(gòu)造方法我們也介紹了；方法3的Collections是一個工具類慢睡，集成了很多對集合的操作方法逐工！

Vector分析

vector也是繼承AbstractList然后實現(xiàn)List接口的铡溪，跟ArrayList很像，和ArrayList里面很多屬性和方法都一樣泪喊。所以這里主要介紹它和ArrayList的區(qū)別棕硫。

區(qū)別1

Vector是線程安全的，ArrayList是線程不安全的窘俺！

Vector是如何實現(xiàn)線程安全的呢饲帅？它在所有容易被線程影響的方法都加了Synchronized關(guān)鍵字來修飾！所以我們可以把它看成是同步版的ArrayList瘤泪。但也恰恰是因為進行了同步操作灶泵，所以它的效率是不如ArrayList的。

當(dāng)然对途，如果我想要同步操作的話赦邻，不是一定要用Vector的，Colletions也提供了可以將ArrayList變成線程同步的方法

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

但其實去看源碼也可以發(fā)現(xiàn)实檀，這個方法同樣是給list的方法加一層synchronized惶洲。

區(qū)別2

觸發(fā)擴容機制的時候，我們的ArrayList是1.5倍膳犹，而我們的Vector確是兩倍恬吕！

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

可以看到我們的4,5行代碼，如果設(shè)置自動增長的長度就加上這個長度须床，如果沒有的話铐料，默認就是加了原來的容量，也就是擴大為原來的兩倍豺旬！

總結(jié)

簡單總結(jié)一下钠惩，Vector與ArrayList大徑相似，最大的區(qū)別就是線程安全的區(qū)別了族阅，記住這個就好了篓跛，反正現(xiàn)在也很少去用Vector了。同時坦刀，我們需要注意的愧沟，不管是Vector還是ArrayList，有時候是挺浪費內(nèi)存的鲤遥。因為有時候如果我有了5w容量了央渣，但是我下面只會再用掉一個容量單位的話忘嫉，我們的Vector會擴容到7w5霹崎，我們的Vector會擴容到10w懂盐，這內(nèi)存浪費的有點多，所以有時候初始的時候就設(shè)置大小容量卜朗！

LinkedList分析

LinkedList實現(xiàn)了List接口拔第，我們還需要關(guān)注的是它還實現(xiàn)了一個比較重要的接口就是Deque。所以我們的LinekdList是可以像操作隊列和棧一樣來操作场钉。

LinkedList底層是一個雙向鏈表蚊俺，我們同樣像分析ArrayList那樣對屬性和構(gòu)造方法還有常用方法進行分析，來了解一下它的特性逛万！

屬性

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

三個屬性泳猬，我們的鏈表長度，頭結(jié)點宇植，尾節(jié)點得封。

構(gòu)造方法

我們有兩個構(gòu)造方法，一個空構(gòu)造方法public LinkedList() {}指郁，因為我們是鏈表忙上，所以是不需要指定長度和容量的。還有一個就是有參構(gòu)造闲坎，可以傳入一個Collection類型的子集合疫粥，后續(xù)會調(diào)用方法addAll進行鏈表的初始化。

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

addAll會再調(diào)用另一個可以傳入鏈表長度的重載方法腰懂。然后代碼主要是進行這些操作：

檢查邊界梗逮，只能在大于等于0和小于等于鏈表長度的范圍才行
進行判斷，如果要用來初始化的集合長度等于0绣溜，返回false
如果判斷是否在尾結(jié)點插入慷彤，然后進行相關(guān)操作
對數(shù)組遍歷進行結(jié)點的插入
鏈表的長度加上我們的數(shù)組長度，返回true涮毫。

public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

常用方法

LinkedList常用的方法太多了瞬欧，很多都是鏈表的相關(guān)操作，可以看起來有點復(fù)雜罢防，但是仔細去研讀源碼艘虎，也就很好理解。這里也就介紹一下增加刪除吧

增加

增加操作的話咒吐，可以在頭結(jié)點前面增加野建，也可以在我們的尾結(jié)點后面增加，默認的add方法是在尾結(jié)點后面增加恬叹。

add(E) 在尾結(jié)點后面插入候生，調(diào)用linkLast(e)方法
addLast(E)在尾結(jié)點后面插入，調(diào)用linkLast(e)方法
addFirst（E）在頭結(jié)點前面插入绽昼，調(diào)用linkFirst(e)方法

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

代碼很好理解唯鸭，具體操作解析的如下圖：

刪除

移除元素的話，有三個方法

remove(Object o)硅确，移除在鏈表中的元素
removeLast()目溉，移除鏈表最后一個元素
removeFirst()明肮，移除鏈表第一個元素

remove方法

我們先來看看remove方法

    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

首先是進行了元素的判空，然后進行了遍歷缭付，然后都調(diào)用了unlink方法后返回true柿估；如果沒有找到元素就返回false。

順藤摸瓜來看看unlink方法

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

這個方法呢陷猫，很普通秫舌，就是進行雙向鏈表的正常刪除操作，沒什么好解釋的绣檬，如果不懂的話足陨，可以看看下面這張圖。如果看了圖還是不能理解的話河咽，需要去補充鏈表的知識了钠右！

removeFirst()與removeLast()

這兩個方法，一個調(diào)用了unlinkFirst(Node<E> f)忘蟹，一個調(diào)用了unlinkLast(Node<E> l)飒房，也都是雙向鏈表的正常操作，沒有什么特別難的地方媚值！

LinkedList小總結(jié)

LinkedList的方法非常多狠毯，基本都是一些鏈表的操作。同時它也是線程不安全的褥芒，我們同樣可以用Collections幫助類對其進行轉(zhuǎn)換成線程安全的嚼松。

        LinkedList<Integer> linkedList = (LinkedList<Integer>) Collections.synchronizedList(new LinkedList<Integer>());

面試題分析

這里我只找了一題，因為很多基本很多都只問這題锰扶。其他的話献酗，通過上面的學(xué)習(xí)也可以說道說道！

請說明ArrayList和LinkedList的區(qū)別坷牛？

ArrayList是基于索引的數(shù)據(jù)接口罕偎，它的底層是數(shù)組。它可以以O(shè)(1)時間復(fù)雜度對元素進行隨機訪問京闰。與此對應(yīng)颜及，LinkedList是以元素列表的形式存儲它的數(shù)據(jù)，每一個元素都和它的前一個和后一個元素鏈接在一起蹂楣，在這種情況下俏站，查找某個元素的時間復(fù)雜度是O(n)。
相對于ArrayList痊土，LinkedList的插入肄扎，添加，刪除操作速度更快，因為當(dāng)元素被添加到集合任意位置的時候反浓，不需要像數(shù)組那樣重新計算大小或者是更新索引萌丈。
LinkedList比ArrayList更占內(nèi)存，因為LinkedList為每一個節(jié)點存儲了兩個引用雷则，一個指向前一個元素，一個指向下一個元素肪笋。

（這里再補充一下）

ArrayList增刪慢不是絕對的(在數(shù)量大的情況下月劈，已測試)：

如果增加元素一直是使用add()(增加到末尾)的話，那是ArrayList要快
一直刪除末尾的元素也是ArrayList要快【不用復(fù)制移動位置】
至于如果刪除的是中間的位置的話藤乙，還是ArrayList要快猜揪！

但一般來說：增刪多還是用LinkedList，因為上面的情況是極端的~

參考資料

Core Java

公眾號《Java 3y》文章

知乎專欄《Java那些事兒》