Java LinkedList 與 ArrayList 效能深度比較與選型指南

List 家族速覽

選型決策樹

需要快速隨機存取 (get/indexOf)？ → ArrayList
需要頻繁頭尾增刪、實作 Queue/Deque？ → LinkedList (或 ArrayDeque)
多線程共享列表？ → Collections.synchronizedList / CopyOnWriteArrayList
單線程、高效能棧/佇列？ → ArrayDeque (最佳選擇)

實測效能數據 (10 萬筆)

結論：LinkedList 頭尾增刪碾壓陣列類；隨機存取陣列類完勝。Vector/Stack 同步開銷大，單線程勿用。

原理深度解析

ArrayList 插入慢的原因

public void add(int index, E element) {
    ensureCapacity(size + 1);
    // 核心開銷：JNI 級記憶體複製，移動 index 後所有元素
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

System.arraycopy 是 Native 方法，雖快但隨資料量線性增長。

LinkedList 插入快的原因

public void add(int index, E element) {
    addBefore(element, (index == size ? header : node(index)));
}

private Node<E> node(int index) {
    // 雙向優化：index < size/2 從頭找，否則從尾找
    if (index < (size >> 1)) {
        for (Node<E> x = first; x != null; x = x.next) ...
    } else {
        for (Node<E> x = last; x != null; x = x.prev) ...
    }
}

private void linkBefore(E e, Node<E> succ) {
    Node<E> pred = succ.prev;
    Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null) first = newNode;
    else pred.next = newNode;
    size++; modCount++;
}

僅修改前後節點指標，無記憶體大量複製。

隨機存取差異

• ArrayList：elementData[index] 直接記憶體偏移，CPU 緩存友好
• LinkedList：需從頭/尾遍歷 Node 指標，緩存未命中率高，指令分支多

Vector vs ArrayList 差異補充

• 同步：Vector 所有方法 synchronized，ArrayList 無
• 擴容策略：ArrayList 1.5 倍 (old*3)/2+1；Vector 可指定增量，預設 2 倍
• 構造子：Vector 多一個 Vector(capacity, increment)
• Enumeration：Vector 支援 elements() 回傳 Enumeration，ArrayList 無
• 序列化：ArrayList 實作 Serializable，Vector 早期版本未實作

現代最佳實踐

// 一般列表
List<String> list = new ArrayList<>();

// 高併發讀多寫少
List<String> safeList = new CopyOnWriteArrayList<>();

// 佇列/棧 (單線程)
Deque<String> queue = new ArrayDeque<>();
queue.addLast("a"); queue.pollFirst();

// 佇列/棧 (多線程)
BlockingQueue<String> mq = new LinkedBlockingQueue<>();

口訣：查多改少 ArrayList，改多查少 LinkedList，但實測才是真理——ArrayDeque 通常比 LinkedList 更快且記憶體更省。