您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

Java 容器源碼深度解析（一）：ArrayList、LinkedList、Vector、Stack、PriorityQueue 核心機制圖解

編輯：Java 綜合教學

前言：閱讀源碼是理解數據結構最快的捷徑

Java 集合框架是面試高頻、日常開發核心。本文基於 JDK 8 源碼，深度剖析 ArrayList、LinkedList、Vector、Stack、PriorityQueue 五大容器的字段設計、擴容策略、核心操作實現、線程安全模型、適用場景，配合關鍵代碼片段與圖解，助你建立「源碼級」認知。

一、 ArrayList：動態數組的標準實現

1.1 核心字段


private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // JDK 8 新增，延遲初始化標識
transient Object[] elementData; // 非序列化，自定義序列化邏輯
private int size; // 邏輯大小 ≤ elementData.length

1.2 擴容機制：1.5 倍增長


private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
    if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

關鍵點：
• 首次 add 時從空數組擴容到 10 (DEFAULT_CAPACITY)
• MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 (預留 Header 空間)
• Arrays.copyOf 底層調用 System.arraycopy (native 快速複製)

1.3 隨機訪問 O(1)，插入刪除 O(n)


// get(index) - 直接下標訪問
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

// add(index, element) - 後移元素
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

// remove(index) - 前移元素，置 null 幫助 GC
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; // 釋放引用
    return oldValue;
}

1.4 避坑指南

預估大小：大量數據用 new ArrayList<>(estimatedSize) 避免多次擴容複製。
遍歷刪除：不可 for (E e : list) list.remove(e) → ConcurrentModificationException，用 Iterator.remove() 或反向索引刪除。
modCount：結構性修改時增長，迭代器檢測 expectedModCount != modCount 快速失效。

二、 LinkedList：雙向鏈表 + Deque 雙端隊列

2.1 節點結構


private static class Node {
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

2.2 核心字段


transient int size = 0;
transient Node first;
transient Node last;

2.3 關鍵操作：折半查找優化


Node node(int index) {
    // 從離 index 近的一端開始遍歷
    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++) x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--) x = x.prev;
        return x;
    }
}

複雜度：
• get/set/add/remove(index) → O(min(index, size-index)) ≈ O(n)
• addFirst/Last、getFirst/Last、removeFirst/Last → O(1)
• 實現 Deque 接口，天然支持棧/隊列操作

2.4 隊列操作對照

操作	拋異常	返回特殊值
入隊	add(e) / addLast(e)	offer(e) / offerLast(e) → boolean
出隊	remove() / removeFirst()	poll() / pollFirst() → null
查隊首	element() / getFirst()	peek() / peekFirst() → null

三、 Vector：同步版 ArrayList (已過時不推薦)

所有公共方法加 synchronized，性能差，擴容策略 2 倍 (可配置 capacityIncrement)。
替代方案：單線程用 ArrayList；多線程用 Collections.synchronizedList()、CopyOnWriteArrayList 或並發包容器。

四、 Stack：繼承 Vector 的 LIFO 棧 (同樣過時)


public E push(E item) { addElement(item); return item; } // 底層 addElement 同步
public synchronized E pop() {
    E obj = peek();
    removeElementAt(size() - 1);
    return obj;
}
public synchronized E peek() {
    if (size() == 0) throw new EmptyStackException();
    return elementAt(size() - 1);
}
public synchronized int search(Object o) { // 從棧頂(尾部)向下找
    int i = lastIndexOf(o);
    return i >= 0 ? size() - i : -1;
}

現代替代：Deque<E> stack = new ArrayDeque<>(); 非同步、性能更強、API 更豐富。

五、 PriorityQueue：基於最小堆的優先隊列

5.1 核心字段


private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue; // 堆數組
private int size = 0;
private final Comparator comparator; // null 時元素需實現 Comparable
transient int modCount = 0;

5.2 入隊：上濾


public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length) grow(i + 1);
    size = i + 1;
    if (i == 0) queue[0] = e;
    else siftUp(i, e); // 調整堆
    return true;
}

private void siftUp(int k, E x) {
    if (comparator != null) siftUpUsingComparator(k, x);
    else siftUpComparable(k, x);
}

// Comparable 版上濾
private void siftUpComparable(int k, E x) {
    Comparable key = (Comparable) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0) break; // 父節點 ≤ 當前，滿足最小堆
        queue[k] = e; // 父節點下沉
        k = parent;
    }
    queue[k] = key;
}

5.3 出隊：下濾


public E poll() {
    if (size == 0) return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0) siftDown(0, x); // 最後葉子節點補到根，下濾
    return result;
}

private void siftDownComparable(int k, E x) {
    Comparable key = (Comparable) x;
    int half = size >>> 1; // 非葉子節點數
    while (k < half) {
        int child = (k << 1) + 1; // 左子節點
        Object c = queue[child];
        int right = child + 1;
        if (right < size && ((Comparable) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right]; // 取較小子節點
        if (key.compareTo((E) c) <= 0) break; // 父節點 ≤ 子節點，位置正確
        queue[k] = c; // 子節點上移
        k = child;
    }
    queue[k] = key;
}

5.4 關鍵特性

非線程安全：多線程用 PriorityBlockingQueue。
無界隊列：自動擴容，但初始容量 11 可優化。
不允許 null：入隊拋 NPE。
迭代器無序：iterator() 不保證優先級順序，需 Arrays.sort(queue) 或反複 poll()。
應用場景：任務調度、Dijkstra/A* 最短路徑、TopK 問題、合併 K 個有序鏈表。

六、總結對照表

容器	底層結構	線程安全	隨機訪問	首尾操作	插入刪除中間	主要用途
ArrayList	動態數組	否	O(1) ✓	O(n)	O(n)	通用列表、隨機訪問多
LinkedList	雙向鏈表	否	O(n)	O(1) ✓	O(1) 定位後	頻繁首尾增刪、隊列/棧
Vector	動態數組	是(synchronized)	O(1)	O(n)	O(n)	過時，勿用
Stack	動態數組	是(synchronized)	O(1)	O(1) 棧頂	不支持	過時，用 ArrayDeque
PriorityQueue	最小堆(數組)	否	不支持	O(log n) 入/出	不支持	優先級調度、TopK