我们经常会使用 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性能问题。了解常见集合类型及其操作背后的数据结构原理，选择合适的数据结构。