LinkedList 與 List 在三大基礎演算法中的效能實測對比

.NET Framework 提供兩種清單實作：鏈結清單 與 動態陣列。本文透過嚴謹的效能基準測試，在佇列（FIFO）、堆疊（LIFO）、單純尾端插入三大基礎演算法場景下，對比兩者在不同資料量級下的真實表現，並給出明確的選型建議。

1. 初始容量對 List 效能的影響

結論：初始容量對 List 效能無顯著影響（佇列測試波動屬測試誤差範圍）。

2. 佇列演算法對比

測試邏輯：AddLast 入隊 → RemoveFirst 出隊，循環 1000 次

分析：

• LinkedList：近似線性增長，節點操作固定成本
• List：指數級增長，每次 RemoveAt(0) 觸發整個陣列記憶體搬移
• 臨界點：長度 < 30 時 List 較快（避免節點建立開銷）；長度 ≥ 30 LinkedList 完勝

3. 堆疊演算法對比

測試邏輯：AddLast 入棧 → RemoveLast 出棧，循環 1000 次

分析：兩者皆線性增長，但 List 全程領先。原因：RemoveAt(Count-1) 僅調整 Count，無記憶體搬移、無重新配置（除非主動 TrimExcess）。LinkedList 仍需節點建立/銷毀開銷。

4. 單純尾端插入對比

測試邏輯：AddLast 循環插入 → Clear，循環 1000 次

結論：與堆疊結果高度一致，List 尾端插入極致高效（摊還 O(1)），LinkedList 節點開銷固定存在。

5. 完整測試程式碼

class Program {
    const int TEST_TIMES = 1000;
    static void Main() {
        // 容量影響測試
        TestQueue(10000, 0); TestQueue(10000, 64); TestQueue(10000, 255); TestQueue(10000, 1024);
        TestStack(10000, 0); TestStack(10000, 64); TestStack(10000, 255); TestStack(10000, 1024);
        TestInsert(10000, 0); TestInsert(10000, 64); TestInsert(10000, 255); TestInsert(10000, 1024);
        // 核心對比測試
        foreach (int n in new[]{10,30,50,100,1000,10000}) {
            TestQueue(n); TestStack(n); TestInsert(n);
        }
    }
    // TestQueue, TestStack, TestInsert 方法完整實作見原文
    // 關鍵：使用 Stopwatch 高精度計時，ElaspedTicks 轉換毫秒
}

6. 選型決策指南

7. 結語

效能測試揭示了資料結構本質：陣列尾端操作極快、頭部操作極慢；鏈結清單頭尾操作均衡但固定開銷較大。實務選型請依據演算法存取模式與資料量級決策，而非習慣性預設使用 List<T>。