如何高效使用 C# List 集合 – wiki基地

---

C# List 集合的高效使用指南

C# 中的 List<T> 是日常开发中最常用、最灵活的集合类型之一。它提供了一个动态大小的数组，可以方便地添加、删除和访问元素。然而，正如任何强大的工具一样，如果不理解其内部工作原理和性能特性，就可能在不知不觉中引入性能瓶颈。

本文将深入探讨 List<T> 的内部机制，并基于这些机制详细阐述如何高效地使用 List<T>，从基础用法到高级优化技巧，帮助您编写出更快速、更节省资源的 C# 代码。

1. 理解 List 的内部机制：动态数组的真相

要高效使用 List<T>，首先必须理解它的底层结构。List<T> 并非链表或神奇的数据结构，它本质上是围绕一个 泛型数组 T[] 构建的。

List<T> 维护两个关键的内部状态：

1. _items (或类似的名称)： 这是实际存储元素的底层数组 T[]。
2. _size (或类似的名称)： 这是一个整数，表示列表中当前包含的元素数量。这个数量就是 Count 属性返回的值。

关键在于，底层数组 _items 的大小（即其 Length）通常大于或等于当前元素的数量 _size。数组的实际大小由 Capacity 属性表示。

List<T> 的“动态”特性体现在当您添加元素导致 _size 等于 Capacity 时，List<T> 会自动进行扩容操作。这个扩容过程是 List<T> 性能特性的核心：

1. 创建一个新的、容量更大的数组（通常是当前容量的两倍）。
2. 将旧数组中的所有元素复制到新数组中。
3. 更新内部引用，指向新的数组。
4. 释放旧数组的内存（由垃圾回收器负责）。

这个扩容和复制元素的过程是一个相对耗时的操作，其成本与当前列表中的元素数量成正比（O(N)）。如果频繁发生扩容，尤其是在添加大量元素时，将显著降低性能。

理解了这一点，我们就有了优化 List<T> 使用的基础：尽量减少或优化扩容操作。

2. 基础使用与性能考量

在我们深入讨论高级优化之前，先回顾一下 List<T> 的基本操作及其性能特点。理解这些基本操作的时间复杂度是高效使用的前提。

时间复杂度简述：
* O(1)：常数时间，操作时间不随元素数量变化。
* O(log N)：对数时间，操作时间随元素数量对数增长（非常快）。
* O(N)：线性时间，操作时间与元素数量成正比。
* O(N log N)：线性对数时间，常见的排序算法复杂度。
* O(N²)：平方时间，操作时间与元素数量的平方成正比（非常慢）。

2.1 创建 List

• new List<T>(): 创建一个空列表。初始容量通常较小（可能是0或一个很小的常数，例如4），在第一次添加元素时才会进行第一次扩容。
• new List<T>(int capacity): 创建一个指定初始容量的列表。这是最推荐的方式，如果您能预估列表的大小，提前分配足够的容量可以完全避免或减少后续的扩容操作。
• new List<T>(IEnumerable<T> collection): 使用另一个集合的元素初始化列表。List<T> 会遍历源集合并添加到新列表中。其内部会首先确定源集合的大小（如果可能，例如源集合是 ICollection<T>），然后直接创建一个足够大的数组，避免多次扩容。这也是一个高效的初始化方式。

效率建议： 如果知道大致的元素数量，务必使用 new List<T>(capacity) 或 new List<T>(IEnumerable<T> collection)。这能显著减少甚至消除扩容带来的性能开销。

2.2 添加元素

• Add(T item): 在列表末尾添加一个元素。
  • 性能：平均情况 O(1)（摊销常数时间）。在不触发扩容时是 O(1)。触发扩容时是 O(N)，因为需要复制所有现有元素。由于扩容是按指数级增长容量（通常翻倍），所以在一系列 Add 操作中，尽管单次扩容成本高，但平均到每次 Add 操作上的成本是常数级别的。
• AddRange(IEnumerable<T> collection): 在列表末尾添加另一个集合的所有元素。
  • 性能：O(M)，其中 M 是要添加的元素数量。AddRange 内部会计算所需的新容量，如果当前容量不足，会一次性扩容到足够容纳现有元素和新元素的总和，然后使用 Array.Copy 高效地复制元素。这比在循环中多次调用 Add 要高效得多，尤其是在添加大量元素时。
• Insert(int index, T item): 在指定索引处插入一个元素。
  • 性能：O(N)。为了在中间或开头插入元素，List<T> 需要将插入点之后的所有元素向后移动一个位置，以腾出空间。这个移动操作的成本与需要移动的元素数量成正比，最坏情况（在索引0插入）需要移动 N 个元素，所以是 O(N)。
• InsertRange(int index, IEnumerable<T> collection): 在指定索引处插入另一个集合的所有元素。
  • 性能：O(N + M)，其中 N 是插入点之后的元素数量，M 是要插入的元素数量。需要移动 N 个元素腾出空间，然后复制 M 个元素。

效率建议：
* 优先使用 Add 在列表末尾添加元素，这是最常见且效率最高的添加方式（考虑摊销成本）。
* 添加多个元素时，始终优先使用 AddRange 而不是循环调用 Add。
* 尽量避免频繁使用 Insert 和 InsertRange，尤其是在列表的开头或中间。如果业务逻辑频繁需要在任意位置插入，LinkedList<T> 或其他数据结构可能更适合。

2.3 访问元素

• this[int index] (索引器): 通过索引访问（获取或设置）元素。
  • 性能：O(1)。数组的底层特性决定了可以通过索引直接计算出元素的内存地址，因此访问速度非常快。

效率建议： 索引访问是 List<T> 的强项，是 O(1) 操作，放心使用。请注意索引越界异常。

2.4 删除元素

• Remove(T item): 删除列表中第一次出现的指定元素。
  • 性能：O(N)。首先需要遍历列表查找元素（O(N)），找到后，为了填补删除元素留下的空隙，需要将后续所有元素向前移动（O(N)）。所以总成本是 O(N)。
• RemoveAt(int index): 删除指定索引处的元素。
  • 性能：O(N)。与 Remove 类似，删除指定索引处的元素后，需要将该索引之后的所有元素向前移动一个位置来填补空隙。最坏情况（删除索引0的元素）需要移动 N-1 个元素，所以是 O(N)。删除列表末尾的元素 (index = Count – 1) 是 O(1)，因为它不需要移动任何后续元素。
• RemoveAll(Predicate<T> match): 删除所有符合指定条件的元素。
  • 性能：O(N)。虽然内部实现可能比循环调用 Remove 更高效（例如，使用一个“写入指针”和“读取指针”一次性完成元素的移动），但仍然需要遍历整个列表并可能移动元素，所以整体复杂度是 O(N)。它通常比在循环中调用 Remove 或 RemoveAt 更快，因为后者在删除元素后可能会导致索引失效或需要调整循环逻辑。
• Clear(): 从列表中移除所有元素。
  • 性能：O(N) 理论上（需要将所有元素设置为默认值以帮助垃圾回收），但实际上非常快，接近 O(1)，因为只需要重置内部计数器 _size 为 0。底层数组通常不会立即释放，而是保留下来供后续添加使用，以避免重新分配。

效率建议：
* 删除元素通常是 O(N) 操作，尽量避免在列表的开头或中间频繁删除。
* 删除列表末尾的元素是 O(1)，可以高效使用。
* 删除多个元素时，优先使用 RemoveAll 而不是在循环中调用 Remove 或 RemoveAt。
* 如果需要删除大量元素，或者在循环中删除，可以考虑以下策略：
* 从后往前遍历删除： 如果必须使用 RemoveAt 或 Remove 并基于索引或值进行删除，从列表末尾开始向前遍历。这样删除元素时，不会影响尚未访问到的前面元素的索引。
* 创建一个新列表： 如果需要保留部分元素，可以创建一个新列表，只将需要保留的元素添加到新列表中，然后用新列表替换原列表。这可能是最高效的方法（O(N)），尤其是在需要删除大量元素时。
* 使用 RemoveAll： 如果删除条件简单，RemoveAll 通常是一个不错的选择。

3. 高效使用 List 的核心技巧

基于对 List<T> 内部机制和基本操作性能的理解，我们可以总结出以下高效使用的核心技巧。

3.1 预设容量，避免频繁扩容

这是最重要的优化手段之一。正如前面提到的，扩容是 O(N) 操作。如果能预估列表将包含多少元素，就在创建 List<T> 时指定初始容量。

“`csharp
// Bad: Frequent resizing if itemCount is large
List numbers = new List();
for (int i = 0; i < itemCount; i++)
{
numbers.Add(i);
}

// Good: Avoids resizing (if itemCount <= initialCapacity)
int initialCapacity = 1000; // Based on estimation or requirement
List optimizedNumbers = new List(initialCapacity);
for (int i = 0; i < itemCount; i++)
{
optimizedNumbers.Add(i);
}

// Also Good: Initializing from another collection
List sourceList = GetSourceData(); // Returns an ICollection or similar
List initializedList = new List(sourceList); // Capacity is set to sourceList.Count
“`

即使无法精确预估最终大小，给一个合理的初始容量（例如 100 或 1000）也比使用默认构造函数要好得多。

如果您在添加元素的过程中发现容量可能不足，或者需要确保至少有多少容量，可以使用 EnsureCapacity(int minCapacity) 方法（.NET Core 3.0 及以上版本提供）。这个方法会确保 Capacity 至少达到 minCapacity，如果当前容量不足，会进行扩容。

csharp
List<string> data = new List<string>();
// ... add some items ...
data.EnsureCapacity(100); // Ensures capacity is at least 100 before adding more
// ... add more items, potentially avoiding resizing if capacity was < 100 but now >= 100

3.2 批量操作优于循环单点操作

• 添加多个元素： 使用 AddRange 替代循环 Add。
• 删除多个元素： 使用 RemoveAll 替代循环 Remove 或 RemoveAt。或者，构建一个需要保留元素的新列表，然后替换原列表。
• 复制元素： 使用 CopyTo 替代循环索引访问复制。

“`csharp
List source = Enumerable.Range(0, 10000).ToList();
List destination = new List();

// Bad: Loop with Add
// foreach (int item in source)
// {
// destination.Add(item); // Potential multiple resizes
// }

// Good: AddRange
destination.AddRange(source); // Single potential resize, efficient Array.Copy

List items = new List() { “a”, “b”, “c”, “b”, “d”, “b” };

// Bad: Loop with Remove
// for (int i = 0; i < items.Count; i++) // This loop logic is problematic due to index changes after removal!
// {
// if (items[i] == “b”)
// {
// items.RemoveAt(i);
// i–; // Adjust index after removal – error prone!
// }
// }

// Better: Iterate backward (still O(N^2) in worst case with many removals at start)
// for (int i = items.Count – 1; i >= 0; i–)
// {
// if (items[i] == “b”)
// {
// items.RemoveAt(i);
// }
// }

// Best: RemoveAll
items.RemoveAll(item => item == “b”); // Efficient O(N)
“`

3.3 选择合适的查找方法

• 线性查找 (O(N))： Contains, Exists, Find, FindAll, FindIndex, IndexOf, LastIndexOf. 这些方法会从头到尾遍历列表直到找到或遍历完。
• 二分查找 (O(log N))： BinarySearch. 前提条件是列表必须已经排序！ 如果列表未排序，BinarySearch 的结果是不可预测的。

如果需要频繁查找元素，并且列表内容不经常变化，可以考虑先对列表进行一次排序 (Sort() 是 O(N log N))，然后使用 BinarySearch 进行查找。这在查找次数远大于排序次数时是值得的。

“`csharp
List numbers = Enumerable.Range(0, 100000).ToList(); // Unsorted potentially

// Linear search – O(N)
bool found = numbers.Contains(50000);
int index = numbers.IndexOf(50000);

// Binary search – Requires sorting first!
numbers.Sort(); // O(N log N) – Do this only once or infrequently
int foundIndex = numbers.BinarySearch(50000); // O(log N) – Fast lookup after sorting

if (foundIndex >= 0)
{
Console.WriteLine($”Element found at index: {foundIndex}”);
}
“`

如果需要非常频繁地按键查找，并且不关心元素顺序，Dictionary<TKey, TValue> (O(1) 平均查找) 或 HashSet<T> (O(1) 平均查找) 通常是比 List<T> 更好的选择。

3.4 迭代的效率

遍历 List<T> 中的元素非常常见。有几种方式可以进行迭代：

• for 循环 with index:
  csharp
for (int i = 0; i < list.Count; i++)
{
T item = list[i];
// ... process item
}

  • 性能：O(N)。直接通过索引访问，非常高效。适用于需要知道当前索引或需要修改列表的情况（从后往前修改）。

• foreach 循环:
  csharp
foreach (T item in list)
{
// ... process item
}

  • 性能：O(N)。List<T> 的 GetEnumerator() 方法返回一个结构体枚举器 (List<T>.Enumerator)，这是一个值类型，避免了对象的分配，效率很高， often preferred for readability. It’s generally slightly more performant than for loop in microbenchmarks due to compiler/JIT optimizations for IEnumerable on concrete types like List<T>. Cannot modify the list (add/remove) during foreach iteration; it will throw an exception.

• List<T>.ForEach(Action<T> action):
  csharp
list.ForEach(item => {
// ... process item
});

  • 性能：O(N)。接受一个委托，对每个元素执行操作。在某些场景下，使用 ForEach 可能比 foreach 稍慢，因为它涉及委托调用开销，但通常差距不大。同样不能在 ForEach 执行期间修改列表。

效率建议：
* 对于简单的遍历和读取操作，foreach 通常是最好的选择，兼顾性能和可读性。
* 需要知道当前索引，或者需要在遍历过程中（从后往前）安全地修改列表时，使用 for 循环。
* ForEach 适用于需要对每个元素执行一个特定动作的场景，代码简洁，但性能略低于前两者。

3.5 避免在循环中进行 O(N) 操作

这是一个常见的性能陷阱。例如：

“`csharp
// Bad: O(N^2) operation!
List items = GetItems(); // N items
List itemsToRemove = GetItemsToRemove(); // M items

foreach (string itemToRemove in itemsToRemove) // Outer loop: M iterations
{
items.Remove(itemToRemove); // Inner operation: O(N) for List.Remove
}
// Total complexity: O(M * N) – Very slow if N and M are large
“`

更好的方法是使用 RemoveAll 或其他批量删除策略：

“`csharp
// Good: O(N + M) or O(N) depending on implementation details
List items = GetItems(); // N items
HashSet itemsToRemoveSet = new HashSet(GetItemsToRemove()); // O(M) to build HashSet for O(1) lookup

items.RemoveAll(item => itemsToRemoveSet.Contains(item)); // O(N) for RemoveAll, O(1) average for HashSet.Contains
// Total complexity: O(M + N) – Much better than O(M * N)
“`

或者，构建一个新列表：

“`csharp
// Another Good: O(N + M)
List items = GetItems(); // N items
HashSet itemsToRemoveSet = new HashSet(GetItemsToRemove()); // O(M)

List remainingItems = new List(items.Count – itemsToRemoveSet.Count); // Pre-allocate capacity
foreach (string item in items) // O(N)
{
if (!itemsToRemoveSet.Contains(item)) // O(1) average
{
remainingItems.Add(item); // O(1) amortized
}
}
items = remainingItems; // Replace the list (reference update O(1))
// Total complexity: O(M + N)
“`

3.6 注意值类型和引用类型的性能差异

List<T> 存储的是类型 T 的元素。
* 如果 T 是值类型（struct），元素直接存储在底层数组中。访问和复制成本较低。
* 如果 T 是引用类型（class），底层数组存储的是对对象的引用。实际对象存储在堆上。访问元素时，需要通过引用间接访问对象。在进行元素复制（如扩容或 RemoveAt）时，只需要复制引用，而不是整个对象，但这涉及到更多的内存交互。对于大型列表，值类型由于内存布局更紧凑，通常能带来更好的缓存局部性，从而提升性能。

3.7 ToArray() 的使用

List<T>.ToArray() 方法会创建一个新的数组，并将列表中的所有元素复制到其中。
* 性能：O(N)。需要分配一个新的数组并复制所有元素。

在某些情况下，将 List<T> 转换为数组可能是有益的，例如：
* 当列表大小固定后，使用数组可以获得更好的性能（直接的内存访问，没有动态扩容的开销）。
* 当需要跨线程传递数据时，创建数组的副本可以避免并发修改问题（但需要注意元素如果是引用类型，复制的只是引用）。
* 某些 API 只接受数组作为参数。

频繁地将大型列表转换为数组可能会引入不必要的性能开销和内存分配。

3.8 AsReadOnly() 的使用

List<T>.AsReadOnly() 方法返回一个 ReadOnlyCollection<T> 包装器，它提供了对列表的只读视图。
* 性能：O(1)。不创建新集合，只是提供一个包装层。

使用 AsReadOnly() 是向外暴露列表但不允许外部修改的安全且高效的方式。

4. 何时 List 不是最佳选择？（与其他集合的比较）

理解 List<T> 的优势和劣势，才能在合适的场景选择合适的集合类型，这也是高效使用的一部分。

• 数组 (T[])： 大小固定，但提供最佳的索引访问性能 (O(1)) 和内存局部性。如果集合大小已知且不变，或者性能要求极高，数组是首选。List<T> 内部就是用数组实现的。
• LinkedList<T>： 双向链表。插入和删除元素（已知节点）是 O(1)，但索引访问是 O(N)（需要遍历链表）。适用于需要频繁在任意位置插入或删除，但不常按索引访问的场景。
• HashSet<T>： 基于哈希表的集合。存储不重复的元素，提供 O(1) 平均性能的添加、删除和查找 (Contains) 操作。元素无序。适用于需要快速去重或判断元素是否存在。
• Dictionary<TKey, TValue>： 基于哈希表的键值对集合。提供 O(1) 平均性能的按键添加、删除和查找 (ContainsKey, 索引器)。元素无序。适用于需要通过唯一的键快速查找值的场景。
• SortedList<TKey, TValue> / SortedDictionary<TKey, TValue>： 存储有序的键值对。查找、添加、删除的性能通常是 O(log N)。适用于需要保持元素按键排序的场景。
• Queue<T> / Stack<T>： 分别实现队列（先进先出）和栈（后进先出）的数据结构。添加和移除元素的性能是 O(1)。适用于特定操作模式的场景。
• ConcurrentBag<T> / ConcurrentQueue<T> / ConcurrentDictionary<TKey, TValue> 等： 线程安全的集合。如果在多线程环境中共享集合，应考虑使用这些类型，尽管它们通常比非并发版本有更高的开销以保证线程安全。List<T> 不是线程安全的，在多线程访问时必须手动加锁。

何时优先使用 List：
* 需要一个动态大小的集合。
* 频繁按索引访问元素。
* 主要在列表末尾添加和删除元素。
* 需要保持元素的插入顺序。
* 需要对整个列表进行排序。

何时重新考虑 List：
* 需要频繁在列表开头或中间插入/删除元素（考虑 LinkedList<T>）。
* 需要快速去重或判断元素是否存在（考虑 HashSet<T>）。
* 需要通过唯一的键快速查找值（考虑 Dictionary<TKey, TValue>）。
* 集合大小固定且性能要求极高（考虑 T[]）。
* 在多线程环境中共享集合且不使用锁（考虑并发集合）。

5. List 与 LINQ 的结合使用效率

LINQ (Language Integrated Query) 为集合操作提供了强大且富有表达力的语法。LINQ 方法通常作用于 IEnumerable<T> 接口，而 List<T> 实现了这个接口。

常见的 LINQ 操作如 Where, Select, OrderBy 返回的是延迟执行的 IEnumerable<T>。这意味着它们并不会立即处理数据或创建新的集合，而是在您开始遍历结果时（例如通过 foreach 或调用 ToList(), ToArray(), Count() 等）才执行实际的操作。

这种延迟执行对于构建复杂的查询管道非常高效，因为它避免了创建中间集合。然而，如果您在不需要的情况下频繁调用会强制执行并创建新集合的方法（如 ToList()），可能会引入性能开销。

“`csharp
List numbers = Enumerable.Range(0, 1000000).ToList();

// Efficient: Lazy evaluation
var evenNumbersQuery = numbers.Where(n => n % 2 == 0);
// No processing happens here yet

// Inefficient: Forces evaluation and creates a new List repeatedly
// List processedList = numbers;
// processedList = processedList.Where(n => n > 100).ToList(); // Create a new list
// processedList = processedList.OrderBy(n => n).ToList(); // Create another new list
// processedList = processedList.Select(n => n * 2).ToList(); // Create a third new list

// Efficient: Chain operations and finalize once
List processedList = numbers
.Where(n => n > 100) // Lazy
.OrderBy(n => n) // Lazy
.Select(n => n * 2) // Lazy
.ToList(); // Execute query and create final list – O(N log N) for OrderBy + creation
“`

使用 LINQ 时，理解哪些方法是延迟执行的，哪些是立即执行并可能创建新集合的，对于编写高性能代码至关重要。尽量将需要创建新集合的操作（如 ToList()）放在 LINQ 链的末尾。

6. 性能测量的重要性

理论分析（如时间复杂度）能够指导我们选择更优的算法和数据结构，但在实际应用中，真实的性能可能受到硬件、JIT 编译器优化、垃圾回收、数据特征等多种因素的影响。

因此，当对性能有疑虑时，测量是关键。可以使用 System.Diagnostics.Stopwatch 类来精确测量代码片段的执行时间。

“`csharp
using System.Diagnostics;

// … code setup …

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

// Code segment to measure (e.g., populating a large List with initial capacity)
List testList = new List(1000000);
for (int i = 0; i < 1000000; i++)
{
testList.Add(i);
}

stopwatch.Stop();

Console.WriteLine($”Time elapsed: {stopwatch.ElapsedMilliseconds} ms”);

// … Compare with code segment using default capacity …
stopwatch.Reset();
stopwatch.Start();

List defaultList = new List();
for (int i = 0; i < 1000000; i++)
{
defaultList.Add(i);
}

stopwatch.Stop();

Console.WriteLine($”Time elapsed (default capacity): {stopwatch.ElapsedMilliseconds} ms”);
“`

进行性能测量时需要注意：
* 在 Release 配置下运行，并脱离调试器。
* 进行多次测量取平均值，排除冷启动、JIT 编译、垃圾回收等瞬时影响。
* 测试数据应尽量模拟真实世界场景。
* 微基准测试（microbenchmarking）非常复杂，建议使用 BenchmarkDotNet 这样的专业库来获得更可靠的结果。

7. 总结与最佳实践

List<T> 是 C# 中一个强大且灵活的集合，但要高效使用它，需要深入理解其基于数组的内部机制，尤其是扩容行为。

高效使用 List<T> 的核心原则和最佳实践总结如下：

1. 预设容量： 如果能预估元素数量，始终使用 new List<T>(capacity) 或 new List<T>(IEnumerable<T>) 构造函数，以减少或避免昂贵的扩容操作。在运行时可以考虑使用 EnsureCapacity。
2. 批量操作： 使用 AddRange 替代循环 Add 添加多个元素；使用 RemoveAll 或构建新列表替代循环 Remove/RemoveAt 删除多个元素。
3. 优化插入/删除： 尽量在列表末尾进行添加和删除操作，避免在开头或中间频繁进行 O(N) 的插入和删除。如果频繁需要在任意位置进行这些操作，考虑 LinkedList<T>。
4. 选择合适的查找： 理解线性查找 (O(N)) 和二分查找 (O(log N)) 的区别。如果列表已排序且需要频繁查找，使用 BinarySearch。如果需要快速按键查找，考虑 Dictionary<TKey, TValue> 或 HashSet<T>。
5. 高效迭代： 对于只读遍历，foreach 通常是首选。需要索引或从后往前安全修改时使用 for 循环。
6. 注意 LINQ 使用： 理解 LINQ 的延迟执行特性，尽量将需要创建新集合的操作放在查询链的末尾。
7. 考虑数据结构： 在设计阶段，根据集合的主要使用场景（添加、删除、查找、访问模式），选择最适合的数据结构，不要局限于 List<T>。
8. 线程安全： List<T> 不是线程安全的。在多线程环境中共享访问时，必须手动实现同步或使用并发集合。
9. 实际测量： 当性能是关键因素时，不要过度猜测，使用 Stopwatch 或 BenchmarkDotNet 进行实际的代码性能测量。

通过遵循这些原则和技巧，您可以充分发挥 List<T> 的优势，同时规避潜在的性能陷阱，编写出更加高效、健壮的 C# 应用程序。熟练掌握 List<T> 的高效使用，是成为一名优秀 C# 开发者的重要一步。

---