.NET 遺忘錄（三續）：重新理解 List<T> —— 其實是動態陣列的封裝

前文錯誤將 List<T> 視為「鏈結串列」，導致效能分析完全偏離。痛定思痛，深入 Reference Source 重新認知：List<T> 本質是動態擴容的陣列包裝器，而非鏈結串列。

建構子真相：空陣列單例起步

private static readonly T[] _emptyArray = new T[0];

public List() {
    _items = _emptyArray; // 共享唯讀空陣列，零分配
}

public List(int capacity) {
    _items = new T[capacity]; // 預先分配指定容量
}

無參數建構子不分配記憶體，直接指向靜態空陣列單例。

Add 操作與擴容機制

public void Add(T item) {
    if (_size == _items.Length)
        EnsureCapacity(_size + 1); // 擴容檢查
    _items[_size++] = item;
    _version++;
}

private void EnsureCapacity(int min) {
    if (_items.Length < min) {
        int newCapacity = _items.Length == 0 ? 4 : _items.Length * 2;
        if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity; // 觸發陣列重新分配與複製
    }
}

關鍵結論：

• 預設擴容策略：容量翻倍（0→4→8→16...）
• 頻繁 Add 觸發多次陣列複製（Array.Copy），產生 Gen0 垃圾
• 指定初始容量（new List<T>(estimatedCount)）可避免多次擴容，顯著提升效能

索引存取：直接陣列操作，O(1)

public T this[int index] {
    get {
        if ((uint)index >= (uint)_size) ThrowHelper.ThrowArgumentOutOfRangeException();
        return _items[index]; // 直接陣列索引，無任何遍歷
    }
    set { ... }
}

IL 為單條 ldelem，與陣列完全一致。隨機存取極快，適合洗牌演算法、二分搜尋等大量索引場景。

核心方法皆委派陣列靜態方法

public int IndexOf(T item) => Array.IndexOf(_items, item, 0, _size);
public int FindIndex(int start, int count, Predicate<T> match) {
    // 邊界檢查後，直接 for 迴圈遍歷 _items[i]
}

修正後的選擇指南

自訂擴容策略的可能

若專案對記憶體極度敏感，可繼承 List<T> 覆寫 EnsureCapacity 實現線性增長（如 +50% 或固定區塊），減少記憶體碎片與峰值佔用。