我們經常會使用 List<T> 作為數據存儲容器。但在某些特殊場景下，List.Insert 方法可能會引發嚴重的性能問題，例如 CPU 占用率飆升。

示例程序

以下是一個簡單的控制臺程序，模擬在 List 的開頭不斷插入數據：

internal class Program
{
    static void Main(string[] args)
{
    List<string> numbers = new List<string>();
    string orderNumber = "order12345678912456";
    Console.WriteLine($"從數據庫讀取到數據，逐條放入list");
    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < 100000; i++)
    {
        numbers.Insert(0, orderNumber); // 每次插入到列表開頭
        //numbers.Add(orderNumber);
        if (i % 1000 == 0)
        {
            Console.WriteLine($"已插入 {i} 次");
        }
    }
    //numbers.Reverse();
    sw.Stop();
    Console.WriteLine($"插入完成，耗時：{sw.ElapsedMilliseconds} ms，按任意鍵退出...");
    Console.ReadLine();
}
}

運行上述代碼后，當插入數據量逐漸增大時，CPU 的占用率會顯著提升，執行完以后CPU恢復正常。原因何在？我們從源碼和數據結構的角度進行分析。

List.Insert 的底層實現

以下是 List.Insert 方法的核心實現（通過ILSpy查看）：

public void Insert(int index, T item)
{
    if ((uint)index > (uint)_size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
    }
    if (_size == _items.Length)
    {
        Grow(_size + 1);
    }
    if (index < _size)
    {
        Array.Copy(_items, index, _items, index + 1, _size - index);
    }
    _items[index] = item;
    _size++;
    _version++;
}

關鍵點：

1.Array.Copy：當插入位置在列表中間或開頭時，需要將插入點之后的所有元素向后移動一位，以騰出空間存放新元素。
2.時間復雜度：

?單次插入操作的時間復雜度為 (O(n))，其中 (n) 是列表的當前長度。
?當在循環中多次調用 Insert，整體復雜度會累積。

插入過程的圖解

以下用一張圖示意 numbers.Insert(0, i) 的操作過程：

1.初始狀態：

[1, 2, 3, 4, 5] (原始數組)`` ^ Insert(0, 10)

2.插入后：

[10, 1, 2, 3, 4, 5] (新狀態)

首先會進行擴容檢查，如果_size已達到_items.Length，會調用EnsureCapacity擴容。在插入過程中，  Array.Copy 從索引 0 開始，將每個元素向右移動一位，最終完成插入。

復雜度分析

對于長度為 (n) 的 List，在頭部插入元素的時間復雜度為 (O(n))。在一個循環中執行 (m) 次插入操作，累積復雜度為：

[ O(1) + O(2) + O(3) + \ldots + O(m) = O\left(\frac{m^2}{2}\right) ]

示例計算

假設 List<int> 的長度為 100,000，每次在頭部插入數據：

?第 1 次插入移動 0 個元素?第 2 次插入移動 1 個元素?第 3 次插入移動 2 個元素?...?第 100,000 次插入移動 99,999 個元素

總移動次數為：

[ T = 0 + 1 + 2 + \ldots + (100,000 - 1) = \frac{(100,000) \times (100,000 - 1)}{2} = 4,999,950,000 ]

移動了 49.9 億次元素，這就是導致 CPU 爆高的根本原因。

解決方案

需要注意的是，LinkedList 的遍歷效率不如 List，因此適用場景有限。

1. 使用 List.Add + Reverse 優化

可以先用 List.Add 插入，再調用 Reverse 方法。List.Add 方法，復雜度為 (O(1))。

var numbers = new List<int>();
for (int i = 0; i < 100000; i++)
{
    numbers.Add(orderNumber);
}
numbers.Reverse();

2. 使用 LinkedList

對于頻繁在頭部插入的場景，可以選擇 LinkedList，插入操作復雜度為 (O(1))。

var linkedNumbers = new LinkedList<int>();
for (int i = 0; i < 100000; i++)
{
    linkedNumbers.AddFirst(i);
}

總結

List<T> 存放的數據可能有一定量時候，要考慮的List.Insert性能問題。了解常見集合類型及其操作背后的數據結構原理，選擇合適的數據結構。