java中的資料集合--List源碼分析

• Collection
• List
• • ArrayList
  • • Iterator方法
    • add方法與ArrayList的擴容
  • LinkList分析
  • • 構造方法
    • add方法
• 再看一下LinkList和ArrayList的不同與多數部落格的錯誤認知

Collection

先看一下collection的解釋說明部分：

/ *
 * @param <E> the type of elements in this collection
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Set
 * @see     List
 * @see     Map
 * @see     SortedSet
 * @see     SortedMap
 * @see     HashSet
 * @see     TreeSet
 * @see     ArrayList
 * @see     LinkedList
 * @see     Vector
 * @see     Collections
 * @see     Arrays
 * @see     AbstractCollection
 * @since 1.2
 */
           

這個解釋實際上基本涵蓋了所有我們編碼過程中使用的資料集合類，可以分析一下這些類的源碼，基本上java中的集合類對你再無什麼秘密。

public interface Collection<E> extends Iterable<E> {}
           

collection本身是一個接口，繼承自疊代器Iterable。

如上所述，确實隻能implement一個接口，但是作為interface同樣可以被extends調用，并且一個子類可以extends多個interface父類，這句話有些拗口，不過看看上面collection同樣是一個interface類，但是他用extends了一個類Iterable仍然是interface類型的。

上圖是collection類中的所有方法，同僚涵蓋了Iterable中的方法，還有自己的方法，比如toArray，增删等等。

上圖是collection的子類，從圖中可以看出，他的子類包含ArrayList，ArrayDueque，ArraySet，concurrentlist、concurrentSet之類的子類，實際上集合類的三大件，set 、list、 map三個中，除了map其餘的兩個都繼承自Collection。

List

List同樣是一個接口類，看一下源碼：

public interface List<E> extends Collection<E> {
           

類中的接口如上圖，我們通過分析ArrayList中的增删改查來看list接口方法和Iterator中的方法。

ArrayList

ArrayList繼承自SeriaLizable，表明它是一個可序列化的類

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

Arraylist中存儲資料的資料結構是

transient Object[] elementData; // non-private to simplify nested class access
           

有上面一行代碼可以看出，ArrayList的底層結構實際上是一個數組，并且數組的類型是Object，并且ArrayList定義的時候是以泛型定義，這樣也就解釋了，為什麼ArrayList既可以存放基本類型的資料，也可以存放自定義類型的資料。

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
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;
    }
}
           

ArrayList有三個構造方法，分别是直接new一個不帶參數的ArrayList，一個帶有初始容量的ArrayList，或者參數是Collection的ArrayList，其中我們最常用的不帶參的ArrayList構造方法，實際上等于在new的時候建立了一個DEFAULTCAPACITY_EMPTY_ELEMENTDATA，這個是一個空的數組，這樣做的目的，筆者認為是減小不必要的記憶體損耗。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
           

既然是數組那麼定義的時候就會定義一個初始容量，後面我們會講到一個ArrayList的另一個機制–擴容

Iterator方法

首先看ArrayList中的iterator方法：

/**
 * Returns an iterator over the elements in this list in proper sequence.
 *
 * <p>The returned iterator is <a href="#fail-fast" target="_blank" rel="external nofollow" ><i>fail-fast</i></a>.
 *
 * @return an iterator over the elements in this list in proper sequence
 */
public Iterator<E> iterator() {
    return new Itr();
}
           

注釋的意思是按照一定順序傳回清單中的元素，疊代的實作是通過一個内部類實作，每次疊代都會new一個Itr（）

Itr（）源碼如下：

/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    // Android-changed: Add "limit" field to detect end of iteration.
    // The "limit" of this iterator. This is the size of the list at the time the
    // iterator was created. Adding & removing elements will invalidate the iteration
    // anyway (and cause next() to throw) so saving this value will guarantee that the
    // value of hasNext() remains stable and won't flap between true and false when elements
    // are added and removed from the list.
    protected int limit = ArrayList.this.size;

    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor < limit;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        int i = cursor;
        if (i >= limit)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
            limit--;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;

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

下面這句話是在内部類中的next（）方法完成對list中元素的拷貝，是以next的操作不會對list中的元素有所改變：

Object[] elementData = ArrayList.this.elementData;
           

下面這句話的意思是在多線程操作list的時候的異常檢查，也側面證明了ArrayList并不是一個線程安全的集合類。

throw new ConcurrentModificationException();
           

remove（）中的實作過程核心是這句話，表明他是直接對ArrayList進行的操作。

ArrayList.this.remove(lastRet);
           

add方法與ArrayList的擴容

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
           

add方法有兩個，一個是直接添加，一個是帶有index，可以指定位置添加，此處的添加不做過多讨論，看一下，add方法中的ensureCapacityInternal方法，此方法牽扯到ArrayList的另一個機制–擴容。

首先我們看一下ensureCapacityInternal方法源碼：

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

上面第一個方法中，實作了對new一個參數為空的ArrayList的容量初始化過程，初始化容量也正是DEFAULT_CAPACITY,這個常量值為10。

下面分析一下比較關鍵的一個方法，也就是最常分析的ArrayList的擴容機制。

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}
           

下面這句話的意思就是如果目前容量在不夠用的時候，會先擴容到目前數組長度的1.5倍，如果你一次添加的資料超過原來容量的1.5倍，那麼擴容的容量擴容為當下添加數量和原來數量的容量和，如果添加的資料量超過數組最大的容量，那麼就會報一個outofMemory錯誤：（初始容量的定義是，如果你第一次添加的資料量大于10，那麼你的初始容量就是你添加的長度，如果小于10，那麼數組的初時容量就是10），此處很多部落格上直接說arraylist擴容直接說擴容1.5倍是不準确的。

int newCapacity = oldCapacity + (oldCapacity >> 1);
           

至此，ArrayList的擴容機制講解完畢。

ArrayList中還有替換對應位置元素的方法，set方法，可以根據上面的分析方法檢視，比較簡單。

LinkList分析

連結清單結構印象中一直有些複雜，貌似牽扯到頭指針尾指針的問題，不過比較複雜的結構，也代表着更強大的功能，今天來從源碼分析一下。

構造方法

LinkList比ArrayList要複雜一些，首先看一下類的定義和構造

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{}
           

從定義中可以看出，他內建在list，Deque，cloneable，Serializable，這些說明他可以序列化，可以實作雙端隊列，同時又是一個list。

接下來看一下類中的變量

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;
           

變量隻有三個，一個是size表示連結清單的長度，然後分别是Node類型的頭first和尾部last。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
           

Node是LinkList的靜态内部類，分别維護了一個next和prev兩個節點，分别定義為節點前一個節點和後一個節點，而item則代表目前節點存放的内容。

下面看一下構造。

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
           

構造分為兩個，我們先看一下帶參構造，稍後分析一下add方法。

帶參構造主要的實作過程是addAll方法

/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element
 *              from the specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
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;
    //帶參初始化傳入的index==size
    if (index == size) {
    //此處pred首先指派為連結清單尾部
        succ = null;
        pred = last;
    } else {
    //對于插傳入連結表中某個位置的邏輯，走的是這裡，這個時候，succ代表的是插入的原始節點，而pred代表的是他前一個節點，新插入的元素插在二者中間
        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的下一個節點位置
            pred.next = newNode;

		//這一步是把剛剛插入的節點指派給pred，保證pred始終代表最新插入的節點，也就是保證pred，是被插入位置的前一個節點
        pred = newNode;
    }

    if (succ == null) {
    //succ代表新插入的最後一個節點，循環結束，指派。
        last = pred;
    } else {
    //同樣循環結束，指派
        pred.next = succ;
        succ.prev = pred;
    }

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

上面指派部分已經把連結清單中的addAll講解完畢了，下圖是一個從網上盜的圖，便于大家了解連結清單結構，此圖是一個循環連結清單的結構，咱們介紹的是一個單向連結清單，是以看的時候把紅框圈住的部分忽略即可。

add方法

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
           

add方法的主要實作過程是linkLast，顧名思義，add方法插入元素的時候，是插入到最後一個位置的。

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

在分析一個帶參的add方法

/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
           

此方法中如果插入的位置和size相同就插入到後面，如果不同，就插入到前面，意思是什麼呢，

通俗點講，如果你傳入的index小于連結清單的尺寸，那麼就把元素插入到你設定的那個index節點之前，有人會問那是不是存在index大于size的情況，答案是不存在的，因為上面還有一兒checkPositionIndex方法。linkBefore方法源碼如下。

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //首先把插入目标節點的前一個節點指派給pred
    final Node<E> pred = succ.prev;
    //定義一個新的節點
    final Node<E> newNode = new Node<>(pred, e, succ);
    //把要插入的節點，指派給插入index位置的前一個節點
    succ.prev = newNode;
    if (pred == null)
    //如果連結清單為空，則指派第一個節點為新插入的節點
        first = newNode;
    else
    //如果不為空個，那麼把新的節點，把原始插入節點的前一個節點和新的節點關聯
        pred.next = newNode;
    size++;
    modCount++;
}
           

至此簡單的介紹了LinkList的源碼。

參考：（https://blog.csdn.net/qedgbmwyz/article/details/80108618）

再看一下LinkList和ArrayList的不同與多數部落格的錯誤認知

ArrayList和LinkList的根本上不同是存儲方式不同，一個是順序存儲結構，一個是鍊式存儲結構，二者實體表現是，一個存儲空間是連續的，一個是不連續的。

很多部落格上說ArrayList插入删除效率低，查詢效率高，LinkList反之，并且說出了複雜度,ArrayList的插入删除時間複雜度是O(N),查詢是O（1）

LinkList插入和删除是O（1）查詢則是O（N）

這種說法是十分不準确的，既然LinkList查詢的效率更低，那麼向某一個位置插入資料，所經曆的過程必定是先查詢到這個元素，之後在插入，那麼這個過程是不是時間複雜度已經提高了呢？有源碼為證

/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
           

上述代碼的意思是，如果插入到連結清單的末端，則直接插入即可，如果插入的不是末端，那麼調用linkBefore，這裡面的參數中有一個node(index),我們看一下node（）的源碼：

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
           

源碼中根據插入的位置和連結清單的長度進行比較，大于二人之一，則從尾部查詢，小于二分之一則從頭部開始查詢，這個過程，恰好印證了之前的想法。是以直接說連結清單插入和删除效率高，是十分不準确的，如果連結清單的長度足夠大，那麼實際上連結清單的插入和删除時間複雜度并不低。

ArrayList 是線性表（數組）

get() 直接讀取第幾個下标，複雜度 O(1)

add(E) 添加元素，直接在後面添加，複雜度O（1）

add(index, E) 添加元素，在第幾個元素後面插入，後面的元素需要向後移動，複雜度O（n）

remove（）删除元素，後面的元素需要逐個移動，複雜度O（n）

LinkedList 是連結清單的操作

get() 擷取第幾個元素，依次周遊，複雜度O(n)

add(E) 添加到末尾，複雜度O(1)

add(index, E) 添加第幾個元素後，需要先查找到第幾個元素，直接指針指向操作，複雜度O(n)

remove（）删除元素，同樣需要先查詢後删除，複雜度O(n)