Java 數組、ArrayList、LinkedList、Vector 性能基準測試對比分析

測試設計

對比四種數據結構在四種核心操作上的性能：

• 迭代：Iterator 遍歷
• 隨機訪問：get(index) 循環讀取
• 插入：中間位置 ListIterator.add() 批量插入
• 刪除：ListIterator.remove() 全量刪除

測試數據量：SIZE = 100,000，迭代/隨機訪問重複 10 次取平均。環境：JDK 8+, 默認堆內存。

基準測試代碼

public class PerformanceTest {
    private static final int SIZE = 100000;

    static abstract class Test {
        String op;
        Test(String op) { this.op = op; }
        abstract void test(List<String> list);
        String getOp() { return op; }
    }

    // 迭代測試
    static Test iterateTest = new Test("iterate") {
        public void test(List<String> list) {
            for (int i = 0; i < 10; i++) {
                Iterator<String> it = list.iterator();
                while (it.hasNext()) it.next();
            }
        }
    };

    // 隨機訪問測試
    static Test getTest = new Test("get") {
        public void test(List<String> list) {
            for (int i = 0; i < list.size(); i++) {
                for (int k = 0; k < 10; k++) list.get(k);
            }
        }
    };

    // 插入測試（中間位置）
    static Test insertTest = new Test("insert") {
        public void test(List<String> list) {
            ListIterator<String> it = list.listIterator(list.size() / 2);
            for (int i = 0; i < SIZE; i++) it.add("lion");
        }
    };

    // 刪除測試
    static Test removeTest = new Test("remove") {
        public void test(List<String> list) {
            ListIterator<String> it = list.listIterator();
            while (it.hasNext()) { it.next(); it.remove(); }
        }
    };

    static void runTests(List<String> list, Test... tests) {
        for (Test t : tests) {
            long start = System.currentTimeMillis();
            t.test(list);
            System.out.printf("%s: %d ms%n", t.getOp(), System.currentTimeMillis() - start);
        }
    }

    public static void main(String[] args) {
        // 數組轉 List（固定大小，不支援增刪）
        String[] arr = new String[SIZE];
        Arrays.fill(arr, "lion");
        List<String> arrayList = Arrays.asList(arr);
        System.out.println("=== Array (Arrays.asList) ===");
        runTests(arrayList, iterateTest, getTest); // 僅測試支援的操作

        // 初始化半量數據用於增刪測試
        Collection<String> half = Arrays.asList(new String[SIZE/2]);
        Arrays.fill((String[])half.toArray(), "lion");

        // Vector
        List<String> vector = new Vector<>();
        vector.addAll(half);
        System.out.println("=== Vector ===");
        runTests(vector, insertTest, iterateTest, getTest, removeTest);

        // LinkedList
        List<String> linked = new LinkedList<>();
        linked.addAll(half);
        System.out.println("=== LinkedList ===");
        runTests(linked, insertTest, iterateTest, getTest, removeTest);

        // ArrayList
        List<String> array = new ArrayList<>();
        array.addAll(half);
        System.out.println("=== ArrayList ===");
        runTests(array, insertTest, iterateTest, getTest, removeTest);
    }
}

典型測試結果（參考值，ms）

註：Array 不支援增刪；Vector 同步開銷大；LinkedList 節點對象開銷導致迭代/隨機訪問極慢；ArrayList 擴容拷貝導致中間插入/刪除較慢。

結果深度解析

1. 數組：內存連續、無對象頭開銷、CPU 緩存友好 → 迭代與隨機訪問最快。但固定長度、不支援增刪。
2. ArrayList：動態數組，擴容 1.5 倍。隨機訪問 O(1) 接近數組；中間增刪需 System.arraycopy 移動元素 O(n)；迭代器有快速失效檢查開銷。
3. LinkedList：雙向鏈表，每個節點 3 個引用。中間增刪只需修改指針 O(1)（定位後）；但隨機訪問 O(n) 需遍歷，迭代器創建節點對象開銷大 → 大量中間增刪場景首選。
4. Vector：同步版 ArrayList，所有方法 synchronized，單線程下性能最差，已棄用，替代方案：Collections.synchronizedList 或 CopyOnWriteArrayList。

選型指南

現代 JVM 優化補充

• 逃逸分析 + 標量替換：JIT 可將未逃逸的 ArrayList 節點標量化，消除對象分配。
• 壓縮指針：64 位 JVM 默認開啟 -XX:+UseCompressedOops，堆 < 32GB 時引用壓縮為 32 位，減少內存佔用。
• Value Types (Project Valhalla)：未來 Java 將引入內聯類，進一步消除對象頭開銷，使 ArrayList 性能逼近數組。

總結

性能測試確認了經典理論：數組/ArrayList 適合隨機訪問，LinkedList 適合中間增刪，Vector 應棄用。實際選型還需考慮內存佔用、GC 壓力、併發模式。建議在真實業務數據與訪問模式下進行 JMH 基準測試，而非依賴微基準測試結果直接決策。