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

Java List 實現類性能深度解析：ArrayList、Vector 與 LinkedList

編輯：Java 相關知識

核心結構對比

特性	ArrayList / Vector	LinkedList
底層結構	動態擴容的 `Object[]` 數組	雙向鏈表
隨機訪問 (get/set)	O(1) —— 直接數組下標	O(n) —— 需從頭/尾遍歷至目標節點
尾部插入/刪除	均攤 O(1)（擴容時觸發數組複製）	O(1) —— 僅調整指針
中間插入/刪除	O(n) —— 需移動後續元素（`System.arraycopy`）	O(n) —— 遍歷定位 + O(1) 指針調整 + 節點對象創建開銷
內存佔用	連續內存，預留容量（默認 10，擴容 1.5~2 倍）	離散內存，每個元素額外兩個引用（prev/next）
線程安全	Vector 同步；ArrayList 非同步	非同步（可用 `Collections.synchronizedList` 包裝，但性能損耗 2-3 倍）

ArrayList / Vector 實現細節

擴容機制

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

插入元素時先調用 ensureCapacity(size+1)，再 elementData[size++] = o。中間插入需 System.arraycopy(elementData, index, elementData, index+1, size-index) 移動元素。

同步差異

Vector：絕大多數方法加 synchronized，線程安全但有鎖開銷。
ArrayList：無同步，單線程或外部同步場景性能更優。現代 JVM (JIT、偏向鎖、鎖消除) 下差距已大幅縮小，但在高併發寫入場景仍需額外同步手段。

LinkedList 實現細節

索引定位優化

public Object get(int index) {
    Entry e = header;
    if (index < size/2) {          // 從頭向後
        for (int i = 0; i <= index; i++) e = e.next;
    } else {                       // 從尾向前
        for (int i = size; i > index; i--) e = e.previous;
    }
    return e;
}

插入節點

public void add(int index, Object element) {
    Entry e = header;
    if (index < size/2) { for (int i=0; i<=index; i++) e=e.next; }
    else { for (int i=size; i>index; i--) e=e.previous; }
    Entry newEntry = new Entry(element, e, e.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
}

優勢：插入/刪除不涉及大量元素移動，僅修改鏈表指針。劣勢：隨機訪問慢、節點對象創建/GC 開銷大、內存局部性差（不利 CPU 緩存）。

同步包裝器的性能陷阱

Collections.synchronizedList(new LinkedList()) 通過委派模式實現同步，每次方法調用增加一層間接調用。對簡單操作（get/set/addFirst）開銷顯著（2-3 倍慢），複雜操作（contains、indexOf）相對影響較小。若需線程安全 LinkedList，建議自行複製源碼對關鍵方法加 synchronized，而非使用包裝器。

選型指南

高頻隨機訪問、尾部增刪、單線程/外部同步 → ArrayList
需線程安全的列表、併發讀寫較少 → Vector（或 Collections.synchronizedList(new ArrayList())）
高頻中間插入/刪除、作為堆疊/隊列/雙端隊列 → LinkedList
固定大小、只讀、頻繁遍歷 → 轉為數組 toArray() 獲得最佳緩存友好度

總結

理解底層數據結構是性能調優前提。ArrayList/Vector 以空間換時間（預留容量、連續內存），適合「查多改少」場景；LinkedList 以指針換靈活性，適合「改多查少」且需隊列/棧語義場景。同步包裝器便利但有代價，高併發核心路徑建議採用 java.util.concurrent 包（如 CopyOnWriteArrayList）或自定義同步策略。