您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 集合源碼深度剖析：ArrayList 與 LinkedList 底層結構、擴容、迭代器與效能選型

編輯：Java 相關知識

一、ArrayList 源碼核心解析 (JDK 8/11/17 通用)

1. 核心欄位

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // 非序列化
private int size;

2. 三種建構子

ArrayList()：elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA（延遲初始化）
ArrayList(int initialCapacity)：預分配陣列，避免擴容開銷
ArrayList(Collection<? extends E> c)：c.toArray() 複製元素

3. 擴容機制：grow() 核心邏輯

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

擴容因子 1.5（舊版 2.0），平衡記憶體與複製開銷
MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8（留給 VM header）
每次擴容伴隨 Arrays.copyOf 完整陣列複製

4. 迭代器與 Fail-Fast 機制

private class Itr implements Iterator<E> {
    int cursor, lastRet = -1;
    int expectedModCount = modCount; // 快照

    public E next() {
        checkForComodification();
        // ...
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

modCount：結構性修改次數（add/remove/clear）
迭代器建立時快照 expectedModCount，遍歷中檢測不一致拋出 CME
單執行緒也會觸發：迭代中直接呼叫 list.remove() 而非 itr.remove()

5. ListItr：雙向迭代器 + set/add

繼承 Itr，實作 ListIterator
新增 previous()、hasPrevious()、set()、add()

6. 多執行緒替代方案：CopyOnWriteArrayList

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally { lock.unlock(); }
}

寫時複製：讀無鎖、寫加鎖複製新陣列
適合「讀多寫少」、可容忍短暫資料不一致場景（快取、監聽器列表）
記憶體開銷大、寫入延遲高

二、LinkedList 源碼核心解析

1. 節點結構：雙向鏈表

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

2. 核心欄位

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

3. 四大核心操作

操作	方法	時間複雜度	關鍵邏輯
頭插	linkFirst()	O(1)	新節點 prev=null, next=first; first.prev=新節點
尾插	linkLast()	O(1)	新節點 prev=last, next=null; last.next=新節點
指定位置插入	linkBefore()	O(n) 定位 + O(1) 插入	找到 succ，新節點 prev=succ.prev, next=succ
刪除節點	unlink()	O(n) 定位 + O(1) 刪除	斷開 prev/next 連結，協助 GC

4. 隨機存取優化：node(int index)


Node<E> node(int 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;
    }
}

雙向鏈表特性：索引 < size/2 從 first 走，否則從 last 走
實作 List 介面隨機存取，但效能仍為 O(n)

5. Deque 介面實作：雙端佇列

push()/pop() = addFirst()/removeFirst()（棧）
offer()/poll() = addLast()/removeFirst()（佇列）
peekFirst()/peekLast() 查看不移除

三、ArrayList vs LinkedList vs Vector 效能選型指南

操作	ArrayList	LinkedList	Vector
隨機存取 get/set	⭐⭐⭐ O(1)	⭐ O(n)	⭐⭐⭐ O(1)
尾部新增 add	⭐⭐⭐ 攤平 O(1)	⭐⭐⭐ O(1)	⭐⭐ 同步開銷
頭部/中間新增	⭐ O(n) 陣列位移	⭐⭐ O(n) 定位 + O(1) 插入	⭐ 同步開銷
刪除指定位置	⭐ O(n) 陣列位移	⭐⭐ O(n) 定位 + O(1) 刪除	⭐ 同步開銷
記憶體開銷	低（陣列）	高（Node 物件 + 參考）	低
執行緒安全	❌	❌	✅ synchronized
擴容策略	1.5 倍	不適用	2 倍