Java List 實作效能深度分析：ArrayList、Vector 與 LinkedList

前言

Java Collections Framework 提供三種主流 List 實作：Vector、ArrayList、LinkedList。它們在隨機存取、插入刪除、記憶體佔用等面向有顯著差異。本文從底層實作角度剖析效能特徵。

一、Vector 與 ArrayList：動態陣列實作

底層結構

兩者內部皆維護一個 Object[] elementData 陣列，並以 size 記錄實際元素數。陣列容量 capacity 可大於 size，預留空間減少擴容頻率。

核心操作複雜度

擴容機制

public void ensureCapacity(int minCapacity) {
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object[] oldData = elementData;
        int newCapacity = Math.max(oldCapacity * 2, minCapacity); // 或 1.5 倍
        elementData = new Object[newCapacity];
        System.arraycopy(oldData, 0, elementData, 0, size);
    }
}

擴容涉及陣列複製，若能預估資料量，建議在建構時指定初始容量：new ArrayList(1000)。

Vector vs ArrayList 差異

• 同步化：Vector 方法多為 synchronized，執行緒安全但效能較差；ArrayList 非同步，單執行緒環境下更快。
• 現代 JVM：逃逸分析、鎖消除等優化使兩者差距縮小，但在高併發下 Vector 仍有鎖競爭開銷。
• 建議：非執行緒共享場景優先用 ArrayList；需執行緒安全時考慮 Collections.synchronizedList 或 CopyOnWriteArrayList。

二、LinkedList：雙向鏈結串列實作

底層結構

由 Node 節點組成雙向鏈結，每節點持有 prev、next 參考與元素值。維護 first、last 指標與 size。

核心操作複雜度

記憶體與快取特性

• 每個元素額外佔用兩個參考（prev/next），記憶體開銷大於陣列。
• 節點在堆中分散分佈，CPU 快取命中率低，遍歷效能不如連續陣列。

三、選擇指南

效能測試建議

實際專案中應依據真實資料分佈與操作模式，使用 JMH（Java Microbenchmark Harness）進行基準測試，而非單純相信理論複雜度。