Java List 常用集合 ArrayList、LinkedList、Vector

2020 年 9 月 23 日
筆記
JAVA

Java 中的 List 是非常常用的數據類型。List 是有序的 Collection，Java List 一共有三個實現類，分別是：ArrayList、Vector、LinkedList

本文分析基於 JDK8

ArrayList

ArrayList 繼承自 AbstractList，實現了 List 介面。底層基於數組實現容量大小動態變化，初始容量為 10，允許值為 null，有序，非執行緒安全，擅長隨機訪問

ArrayList 還實現了 RandomAccess、Cloneable、Serializable 介面，所以 ArrayList 是支援快速訪問、複製、序列化的

RandomAccess

標記介面，用來表明其支援快速隨機訪問。如果是實現了這個介面的 List，那麼使用 for 循環的方式獲取數據會優於用迭代器獲取數據
Serializable

標記該類支援序列化
Cloneable

允許在堆中克隆出一塊和原對象一樣的對象，並將這個對象的地址賦予新的引用。ArrayList 提供的是一種深克隆機制，即克隆除自身對象以外的所有對象，包括自身所包含的所有對象實例。實現方式是先調用 super.clone() 方法克隆出一個新對象，然後再手動將原數組中的值複製到一個新的數組，並賦值

ArrayList 擴容機制

擴容機制應該是面試中最常問的了。其他關於 ArrayList 的一些瑣碎方法我就不細說了，主要介紹一下擴容機制。首先了解一下 ArrayList 的成員屬性

// 表示 ArrayList 的默認容量大小
private static final int DEFAULT_CAPACITY = 10;
// 一個空的 Object 數組對象，長度為 0，如果使用默認構造函數創建，則 elementData 默認是該值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// ArrayList 中存放的實際元素個數
private int size;
// 當前元素對象存放的數組，不參與序列化
transient Object[] elementData;

執行 add 方法時，會先執行 ensureCapacityInternal 方法，判斷當前數組容量是否足夠，不夠就擴容。然後將待添加元素加到 elementData 末尾

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

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

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

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // minCapacity > elementData.length 則擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

再分析一下 ensureCapacityInternal 方法，此時 minCapacity 是 size + 1，這裡有兩個嵌套方法 calculateCapacity 和 ensureExplicitCapacity，作用分別如下：

calculateCapacity

如果當前數組為空，則先設置容量為默認值 10，此時還未初始化數組
ensureExplicitCapacity

確認實際的容量，如果不夠就擴容，關鍵的擴容函數 grow 就在這裡

擴展數組大小，首先將容量擴大為原來的 1.5 倍，如果數組是空數組，則將數組初始化，默認容量為 10，如果不是，再判斷是否超出最大容量，超過直接賦予最大值，否則賦予新值，複製原數組到新數組

private void grow(int minCapacity) {
    // 擴容前的容量
    int oldCapacity = elementData.length;
    // oldCapacity 右移一位，等於除以二
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 擴容之後還是不夠，直接賦予新值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 擴容之後超出最大容量，直接賦予最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 複製原數組的值到新數組
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList

LinkedList 繼承自 AbstractSequentialList，實現了 List 和 Deque 介面，基於雙向鏈表實現，每個節點都包含了對前一個和後一個元素的引用，可以被當作堆棧、隊列或雙端隊列進行操作，有序，非執行緒安全

// 指向鏈表的第一個節點
transient Node<E> first;
// 指向鏈表的最後一個節點
transient Node<E> last;

JDK8 中 LinkedList 有一個靜態內部類 Node，它包括的屬性有：當前節點所包含的值，上一個節點，下一個節點

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

除此之外就沒啥好分析的了，LinkedList 不存在容量不足的問題，克隆函數也是將所有元素全都克隆到新的 LinkedList 對象

Vector

Vector 是一個矢量隊列，和 ArrayList 類似，繼承自 AbstractList，實現了 List 介面，就連額外介面也是一樣。不同之處在於：

Vector 使用 synchronized 保證執行緒同步
Vector 中遺留了大量傳統的方法，這些方法不屬於集合框架

Vector 有四個構造方法

// 創建一個默認大小為 10 的向量
public Vector()
// 創建指定大小的向量
public Vector(int initialCapacity)
// 創建指定大小的向量，並且指定增量。增量表示向量每次增加的元素數目
public Vector(int initialCapacity, int capacityIncrement)
// 創建一個包含集合 c 元素的向量
public Vector(Collection<? extends E> c)

Vector 的數據結構和 ArrayList 差不多，它包含了三個成員變數：

// 存放元素的動態數組
protected Object[] elementData;
// 動態數組的實際大小
protected int elementCount;
// 動態數組的增長係數
protected int capacityIncrement;

隨著 Vector 中元素的增加，Vector 的容量也會動態增長，capacityIncrement 是與容量增長相關的增長係數，具體增長細節在 grow 函數中，和 ArrayList 類似

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 如果 capacityIncrement > 0，新的容量大小 = 舊的容量大小 + 增長係數
    // 否則容量擴大為原來的兩倍
    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);
}

Stack

Stack 是 Vector 的子類，實現了一個標準的後進先出的棧。Stack 也是通過數組實現的，當然了，我們也可以將 LinkedList 當作棧來使用

Stack 只定義了默認構造函數，用來創建一個空棧

public Stack()

Stack 除了具有 Vector 的所有 API，還有自己實現的方法

// 判斷堆棧是否為空
public boolean empty()
// 查看堆棧頂部的對象，但不從堆棧中移除它
public synchronized E peek()
// 移除堆棧頂部的對象，並作為此函數的值返回該對象
public synchronized E pop()
// 把對象壓入堆棧頂部
public E push(E item)
// 返回對象在堆棧中的位置，以 1 為基數
public synchronized int search(Object o)

Stack 的擴容機制基於 Vector，不過由於沒有指定增長係數，所有默認為 0，每次擴容數組長度增大為原來的兩倍

Tags: JAVA