C# List源码分析

关键属性

public class List<T> : IList<T>, System.Collections.IList, IReadOnlyList<T>
{private const int _defaultCapacity = 4;private T[] _items;[ContractPublicPropertyName("Count")]private int _size;private int _version;[NonSerialized]private Object _syncRoot;static readonly T[]  _emptyArray = new T[0];   
}  

在创建时，如果不指定大小，会创建一个空数组

public List() {_items = _emptyArray;
}

指定大小创建时

public List(int capacity) {if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);Contract.EndContractBlock();if (capacity == 0)_items = _emptyArray;else_items = new T[capacity];
}

一、Add方法

1.代码解析

/// <summary>
/// 将指定元素添加到列表的末尾。
/// 如果内部数组已满，则自动扩容。
/// </summary>
/// <param name="item">要添加的元素</param>
public void Add(T item)
{// 1. 检查当前内部数组是否已满（_size == _items.Length）if (_size == _items.Length){// 如果满了，调用 EnsureCapacity() 进行扩容EnsureCapacity(_size + 1); // 确保至少能再容纳一个新元素}// 2. 将新元素添加到数组的当前末尾位置_items[_size++] = item; // 先赋值，后自增 _size// 3. 版本号递增：通知正在使用的枚举器集合已被修改_version++;
}

---

2.关键变量

变量名	含义
_items	内部数组，实际存储元素的地方
_size	当前列表中实际包含的元素个数
_items.Length	内部数组的总容量（不是当前元素数量）
EnsureCapacity(int min)	确保内部数组容量至少为 min，如果不够则扩容
_version	枚举器版本号，用于防止在遍历时修改集合

---

3.主要功能

• 向列表末尾添加一个元素；
• 如果当前数组空间不足，则自动扩容；
• 添加成功后更新 _size 和 _version；
• 不会清空已有元素，只是扩展空间。

---

4.时间复杂度

操作	时间复杂度
添加元素（无需扩容）	O(1)
添加元素（需要扩容）	O(n)，其中 n 是当前元素数量（因为要复制数组）

但均摊时间复杂度仍然是 O(1)，因为扩容不经常发生。

---

5.示例说明

List<int> list = new List<int>(); // 初始容量为 0list.Add(10); 
list.Add(20); for(int i = 0;i<list.length,i++){Console.WriteLine(list[i]); 
}

6.总结

功能	实现方式
添加元素	Add(item)
自动扩容	EnsureCapacity(min)
更新大小	_size++
防止并发修改错误	_version++
内存管理	使用数组扩容机制（Array.Resize）

---

二、EnsureCapacity方法

1.代码解析

/// <summary>
/// 确保当前列表的容量至少为指定的最小值。
/// 如果当前容量小于 min，则通过扩容来满足需求：
///     - 扩容为当前容量的两倍，或者
///     - 直接设为 min，取两者中较大的那个。
/// </summary>
/// <param name="min">需要保证的最小容量</param>
private void EnsureCapacity(int min)
{// 如果当前数组长度小于所需的最小容量，就需要扩容if (_items.Length < min){// 初始容量：如果当前数组为空，则使用默认容量；// 否则扩容为原来的两倍int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;// 防止整数溢出（overflow）导致 newCapacity 变得很小// 使用 (uint) 强制转换来安全判断是否超过 .NET 中数组的最大允许长度（约 2^31 - 1）if ((uint)newCapacity > Array.MaxArrayLength)newCapacity = Array.MaxArrayLength;// 如果扩容后的容量仍然小于所需最小值 min，则直接设置为 minif (newCapacity < min)newCapacity = min;// 设置新的容量（这会触发内部数组重新分配）Capacity = newCapacity;}
}

---

2.关键变量

内容	说明
_items	内部使用的数组，用于存储列表元素
_defaultCapacity	列表初始默认容量4
Array.MaxArrayLength	.NET 中数组最大允许长度，约为 2,147,483,591（即接近 2G 的元素）
(uint)newCapacity	防止负数溢出（当 newCapacity 超过 int.MaxValue 时会变成负数）
Capacity = newCapacity	实际触发数组扩容的赋值操作

---

3.主要功能

• 确保列表内部数组 _items 的容量至少为指定的最小值 min；
• 如果当前容量不足，则进行 扩容操作；
• 初始扩容使用默认容量 _defaultCapacity，后续扩容为原来容量的 两倍；
• 在扩容过程中会 防止整数溢出，确保不会因溢出导致容量异常；
• 如果扩容后的容量仍小于所需最小值 min，则直接设置为 min；
• 扩容通过设置 Capacity = newCapacity 触发内部数组的 重新分配和复制；
• 不会缩小容量，仅支持扩容。

---

4.时间复杂度

操作	时间复杂度
添加元素（无需扩容）	O(1)
添加元素（需要扩容）	O(n)，其中 n 是当前元素数量（因为要复制数组）

但均摊时间复杂度仍然是 O(1)，因为扩容不经常发生。

---

5 示例说明

List<int> list = new List<int>(); // 初始容量为 0list.Add(10); // 容量变为 4
list.Add(20); // 容量仍为 4
list.Add(30); // 容量仍为 4
list.Add(40); // 容量仍为 4
list.Add(50); // 容量变为 8（因为需要容纳第 5 个元素）Console.WriteLine(list.Capacity); // 输出：8

---

6. 总结

功能	实现方式	说明
确保最小容量	if (_items.Length < min)	判断当前数组容量是否满足需求
计算新容量	newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2	初始扩容使用默认容量，后续每次扩容为原来两倍
防止整数溢出	(uint)newCapacity > Array.MaxArrayLength newCapacity = Array.MaxArrayLength	避免因溢出导致容量异常变小
保证最终容量 ≥ min	if (newCapacity < min) newCapacity = min	如果扩容后仍不足，直接设为所需最小值
执行扩容	Capacity = newCapacity	触发实际数组重分配和数据复制操作

---

三、Insert方法

1.代码解析

/// <summary>
/// 在列表的指定索引位置插入一个元素。
/// 插入后，列表的大小（元素数量）会增加 1。
/// 如果当前内部数组容量不足，则会自动扩容（通常是翻倍）以容纳新元素。
/// </summary>
/// <param name="index">要插入的位置（索引），范围必须在 [0, Count] 之间</param>
/// <param name="item">要插入的元素</param>
public void Insert(int index, T item)
{// 检查索引是否越界：index 必须在 [0, _size] 范围内// 使用 (uint) 避免负数引发异常，并统一处理边界情况if ((uint)index > (uint)_size){// 抛出参数越界的异常ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index,ExceptionResource.ArgumentOutOfRange_ListInsert);}Contract.EndContractBlock();// 如果当前数组已满，则扩容以容纳新元素if (_size == _items.Length)EnsureCapacity(_size + 1); // 扩容逻辑：确保至少有 _size + 1 的空间// 如果插入位置不是末尾，则需要将插入点之后的元素整体后移一位if (index < _size){Array.Copy(_items, index, _items, index + 1, _size - index);}// 将新元素插入到指定索引位置_items[index] = item;// 列表中实际元素数量增加 1_size++;// 版本号递增，用于迭代过程中检测集合是否被修改（防止 ConcurrentModificationException）_version++;
}

---

2.关键变量

变量名	含义
_items	内部使用的数组，存储列表的实际数据
_size	当前列表中实际包含的元素个数
_defaultCapacity	初始默认容量4
EnsureCapacity(...)	确保内部数组容量足够，不够则扩容
Array.Copy(...)	将现有元素从某个位置开始复制到后面一个位置
_version	版本号，用于在 foreach 或枚举器中检测是否修改了集合

---

3.主要功能

• 向列表中 指定索引位置插入一个新元素；
• 如果插入时内部数组空间不足，则 自动扩容（调用 EnsureCapacity）；
• 插入位置必须在 [0, Count] 范围内，否则会抛出 越界异常；
• 如果插入位置不是末尾，则 将该位置之后的所有元素整体后移一位；
• 成功插入后，增加 _size 表示元素数量变化；
• 增加 _version 版本号，用于防止 迭代过程中集合被修改。

---

4.时间复杂度

• 最坏情况 O(n)：当插入位置不是末尾时，需要移动后面的全部元素，时间复杂度与元素数量成正比。
• 最好情况 O(1)：当插入位置是末尾，并且仍有空间时，直接插入即可。

---

5.示例说明

假设有一个 List<int>，内容为 [10, 20, 30]，调用：

list.Insert(1, 15);

结果变为：

[10, 15, 20, 30]

6.总结

功能	实现方式
插入元素	Insert(index, item)
越界检查	使用 (uint)index > (uint)_size 安全判断
扩容机制	EnsureCapacity()，按需扩容
元素移动	Array.Copy(...) 移动插入点后的元素
迭代安全	_version++，避免并发修改错误

四、Clear方法

---

1.代码解析

/// <summary>
/// 清空列表中的所有元素。
/// 调用此方法后，列表的 Count（即 _size）将变为 0，
/// 但内部数组 (_items) 的容量 (Capacity) 不会改变。
/// </summary>
public void Clear()
{// 如果当前有元素（_size > 0），则需要清理引用以帮助垃圾回收器回收内存if (_size > 0){// 使用 Array.Clear 将数组中从索引 0 开始、长度为 _size 的区域设为默认值（null 或 0 等）// 这样做是为了断开对对象的引用，防止内存泄漏（尤其对于引用类型非常重要）Array.Clear(_items, 0, _size);}// 将实际元素数量设置为 0_size = 0;// 版本号递增：用于通知正在使用的枚举器（Enumerator）集合已被修改_version++;
}

---

2.关键变量

变量名	含义
_items	内部数组，存储列表的实际数据
_size	当前列表中实际包含的元素个数
Array.Clear(...)	将数组指定范围内所有元素设置为默认值（释放引用）
_version	枚举器版本号，用于在遍历时检测集合是否被修改

---

3.主要功能

• 清除列表中的所有元素；
• 设置 _size = 0，表示当前没有元素；
• 增加 _version，防止迭代器继续使用旧状态；
• 对引用类型来说，调用 Array.Clear() 是为了释放引用，避免内存泄漏；
• 不会重新分配或缩小内部数组 _items，因此 Capacity 不变。

---

4.时间复杂度

• O(n)：Array.Clear() 需要清除 _size 个元素；
• 不会释放内部数组，所以不清除内存占用，只是逻辑上“清空”。

---

5.示例说明

List<string> list = new List<string> { "A", "B", "C" };list.Clear();Console.WriteLine(list.Count); // 输出：0
Console.WriteLine(list.Capacity); // 输出：仍为 4（假设初始容量为 4）

虽然此时列表为空了，但内部数组的容量并没有变化，下次添加元素时可以复用这个数组，性能更高。

---

与 new List<T>() 和 RemoveAll(...) 的区别

操作	是否保留容量	是否释放引用	是否影响版本号
Clear()	✅ 是（保留 _items 数组）	✅ 是（调用 Array.Clear）	✅ 是（_version++）
new List<T>()	❌ 否（创建新数组）	✅ 是（原数组可被回收）	-
RemoveAll(x => true)	✅ 是（逐个删除）	✅ 是（逐个置 null）	✅ 是（每次 RemoveAt 都改 version）

---

6.总结

功能	实现方式
清空所有元素	Clear()
清理引用	Array.Clear(_items, 0, _size)
更新状态	_size = 0
防止并发修改错误	_version++
不释放内存	保留内部数组，提高后续插入效率

---

五、RemoveAt方法

1.代码解析

/// <summary>
/// 从列表中移除指定索引位置的元素。
/// 移除后，列表的实际大小（元素数量）会减少 1。
/// </summary>
/// <param name="index">要移除的元素的索引</param>
public void RemoveAt(int index)
{// 检查索引是否越界：index 必须在 [0, _size - 1] 范围内// 使用 (uint) 避免负数引发异常，并统一处理边界情况if ((uint)index >= (uint)_size){ThrowHelper.ThrowArgumentOutOfRangeException();}Contract.EndContractBlock();// 实际元素个数减 1_size--;// 如果被删除的不是最后一个元素，则需要将后面的元素前移一位if (index < _size){Array.Copy(_items, index + 1, _items, index, _size - index);}// 将最后一个元素的位置设置为默认值（释放引用，帮助 GC 回收）_items[_size] = default(T);// 版本号递增，用于迭代过程中检测集合是否被修改（防止 ConcurrentModificationException）_version++;
}

---

2.关键变量

变量名	含义
_items	内部使用的数组，存储列表的实际数据
_size	当前列表中实际包含的元素个数
Array.Copy(...)	将后面的数据向前移动覆盖被删除的元素
default(T)	泛型 T 的默认值（例如对引用类型是 null，对 int 是 0）
_version	版本号，用于在 foreach 或枚举器中检测是否修改了集合

---

3.主要功能

• 从列表中移除指定索引位置的元素；
• 索引必须在 [0, Count - 1] 范围内，否则抛出 越界异常；
• 移除后，实际元素数量减 1（即 _size--）；
• 如果删除的不是最后一个元素，则将该元素之后的所有元素 前移一位，保持数组连续性；
• 将原最后一个元素位置设置为 default(T)，释放引用类型对象的引用，帮助 GC 回收内存；
• 增加 _version 版本号，用于防止 迭代过程中集合被修改（ConcurrentModificationException）。

---

4.时间复杂度

• 最坏情况 O(n)：当删除的不是最后一个元素时，需要将后面的元素整体前移，时间复杂度与元素数量成正比。
• 最好情况 O(1)：当删除的是最后一个元素时，只需减少 _size 和 _version++，无需复制数组。

---

5.示例说明

假设有一个 List<int>，内容为 [10, 20, 30]，调用：

list.RemoveAt(1); // 删除索引 1 的元素（即 20）

结果变为：

[10, 30]

---

6.总结

功能	实现方式
删除元素	RemoveAt(index)
越界检查	使用 (uint)index >= (uint)_size 安全判断
元素移动	Array.Copy(...) 移动删除点之后的元素
释放引用	_items[_size] = default(T)
迭代安全	_version++，避免并发修改错误

---

六、IndexOf方法

1.代码解析

/// <summary>
/// 从列表的起始位置开始查找，返回第一个等于指定值的元素的索引。
/// 查找范围为整个列表（从索引 0 到 Count - 1）。
/// 使用 Object.Equals 方法进行比较。
///
/// 此方法内部调用了 Array.IndexOf 方法来完成实际查找。
/// </summary>
/// <param name="item">要查找的目标元素</param>
/// <returns>
/// 如果找到该元素，则返回其在列表中的索引；
/// 否则返回 -1。
/// </returns>
public int IndexOf(T item)
{// 合约保证：// - 返回值 >= -1（-1 表示未找到）// - 返回值 < Count（不会超过当前元素数量）Contract.Ensures(Contract.Result<int>() >= -1);Contract.Ensures(Contract.Result<int>() < Count);// 调用 Array.IndexOf 方法进行查找// 参数说明如下：//   _items: 内部数组，用于存储列表的实际数据//   item: 要查找的目标元素//   0: 从索引 0 开始查找//   _size: 查找的元素个数（即整个列表的有效范围）return Array.IndexOf(_items, item, 0, _size);
}

---

2.关键变量

变量名	含义
_items	内部使用的数组，存储列表的实际数据
item	要查找的目标元素
_size	当前列表中实际包含的元素个数
Array.IndexOf(...)	.NET 提供的数组查找方法，返回匹配项的索引或 -1

---

3.主要功能

• 从列表中查找第一个与指定元素相等的项；
• 查找范围为整个有效元素区域：[0, Count - 1]；
• 使用 Object.Equals() 方法进行比较，支持值类型和引用类型的默认相等判断；
• 内部实际调用 Array.IndexOf() 实现查找逻辑，性能高效；
• 如果找到匹配项，返回其索引位置；
• 如果未找到匹配项，则返回 -1；
• 不会修改列表内容或结构，是只读操作；
• 可用于后续删除、替换等基于索引的操作。

---

4.时间复杂度

• 最坏情况 O(n)，需要遍历整个数组
• 最好情况 O(1)：查找的元素在第一个时。

---

5.示例说明

List<string> list = new List<string> { "apple", "banana", "cherry", "banana" };int index = list.IndexOf("banana");
Console.WriteLine(index); // 输出：1

在这个例子中，我们查找 "banana" 第一次出现的位置，它出现在索引 1 处，所以返回 1。

---

对比：IndexOf(T item) vs IndexOf(T item, int index)

方法	描述
IndexOf(T item)	从头开始查找第一个匹配项
IndexOf(T item, int index)	从指定索引开始查找第一个匹配项

---

6.总结

功能	实现方式
查找元素索引	IndexOf(item)
查找范围	整个列表（从索引 0 到 Count - 1）
比较方式	使用 Object.Equals()
返回值	找到返回索引，否则返回 -1
底层实现	调用 Array.IndexOf(...)
应用场景	快速定位某个元素在列表中的位置

Remove方法就是调用上述两个函数

public bool Remove(T item) {int index = IndexOf(item);if (index >= 0) {RemoveAt(index);return true;}return false;
}

八、RemoveRange方法

1.代码解析

/// <summary>
/// 从列表中移除指定范围内的多个元素。
/// </summary>
/// <param name="index">要移除范围的起始索引</param>
/// <param name="count">要移除的元素个数</param>
public void RemoveRange(int index, int count)
{// 检查 index 是否合法：必须是非负数if (index < 0){ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index,ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);}// 检查 count 是否合法：必须是非负数if (count < 0){ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count,ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);}// 检查 index + count 是否超出当前列表的有效范围if (_size - index < count){ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);}Contract.EndContractBlock();// 如果确实需要删除元素（count > 0）if (count > 0){// 记录旧的大小int i = _size;// 更新实际元素数量_size -= count;// 如果被删除的不是末尾元素，则需要将后面的元素前移覆盖if (index < _size){Array.Copy(_items, index + count, _items, index, _size - index);}// 清空数组中多余部分（帮助 GC 回收内存）Array.Clear(_items, _size, count);// 版本号递增，用于在迭代时检测集合是否被修改_version++;}
}

---

2.关键变量

变量名	含义
_items	内部使用的数组，存储列表的实际数据
_size	当前列表中实际包含的元素个数
index	要删除区域的起始位置
count	要删除的元素个数
Array.Copy(...)	将后面的数据向前移动，覆盖被删除的区域
Array.Clear(...)	清空被删除区域的引用，释放内存
_version	版本号，用于防止并发修改异常（如在遍历过程中修改集合）

---

3.主要功能

• 从列表中移除指定范围内的多个连续元素；
• 参数 index 指定起始索引，count 指定删除个数；
• 确保参数合法性：
  • index >= 0
  • count >= 0
  • index + count <= Count（不越界）
• 如果删除的是中间部分元素，则将后续元素前移覆盖被删除区域；
• 删除后更新 _size 表示实际元素数量减少；
• 调用 Array.Clear() 清除被删除位置的引用，帮助 GC 回收内存（对引用类型有效）；
• 增加 _version 版本号，用于防止 迭代过程中集合被修改（ConcurrentModificationException）；
• 如果 count == 0，则不会执行任何操作。

---

4.时间复杂度

• 最坏情况 O(n)：当删除的不是末尾元素时，需要移动大量数据。

---

5.示例说明

List<string> list = new List<string> { "A", "B", "C", "D", "E" };list.RemoveRange(1, 3); // 删除从索引 1 开始的 3 个元素（即 B、C、D）Console.WriteLine(string.Join(", ", list)); // 输出：A, E

---

6.总结

功能	实现方式
批量删除元素	RemoveRange(index, count)
越界检查	对 index 和 count 分别做非负判断，并验证范围合法性
元素移动	使用 Array.Copy(...) 将后面元素前移
释放内存	使用 Array.Clear(...) 清除被删除区域的引用
迭代安全	_version++ 避免并发修改错误

---

九、InsertRange方法

1.代码解析

/// <summary>
/// 在指定索引位置插入一个集合的所有元素。
/// 如果当前容量不足，会自动扩容（通常是两倍或刚好满足需求）。
/// 插入位置可以是列表末尾（index == _size）。
/// </summary>
/// <param name="index">要插入的位置</param>
/// <param name="collection">要插入的集合</param>
public void InsertRange(int index, IEnumerable<T> collection)
{// 检查集合是否为 nullif (collection == null){ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);}// 检查 index 是否合法：必须在 [0, _size] 范围内if ((uint)index > (uint)_size){ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index,ExceptionResource.ArgumentOutOfRange_Index);}Contract.EndContractBlock();// 尝试将集合转换为 ICollection<T> 接口ICollection<T> c = collection as ICollection<T>;if (c != null)  // 如果转换成功（说明集合支持 Count 属性）{int count = c.Count; // 获取集合中元素数量// 如果集合不为空，则继续处理插入逻辑if (count > 0){// Step 1: 确保当前数组有足够空间容纳新增元素EnsureCapacity(_size + count);// Step 2: 如果插入位置不是末尾，则需要移动现有元素腾出空间if (index < _size){Array.Copy(_items, index, _items, index + count, _size - index);}// Step 3: 处理特殊情况：如果插入的是自己（this == c）if (this == c){// 插入自己时要小心避免数据覆盖问题// 先复制前半部分 [0, index) 到目标位置 indexArray.Copy(_items, 0, _items, index, index);// 再复制后半部分 [index, size - index] 到 index + count 的位置Array.Copy(_items, index + count, _items, index * 2, _size - index);}else{// Step 4: 一般情况：将集合内容拷贝到临时数组，再拷贝进主数组T[] itemsToInsert = new T[count];c.CopyTo(itemsToInsert, 0); // 把集合内容拷贝到临时数组itemsToInsert.CopyTo(_items, index); // 再拷贝到主数组的 index 位置}// Step 5: 更新列表大小_size += count;}}else{// Step 6: 如果集合不支持 ICollection<T>（即没有 Count 属性），则使用 IEnumerator 逐个插入using (IEnumerator<T> en = collection.GetEnumerator()){while (en.MoveNext()){// 每次插入一个元素，并递增 index（连续插入）Insert(index++, en.Current);}}}// Step 7: 版本号加一，防止遍历时修改集合_version++;
}

---

2.关键变量

变量名	含义
_items	内部数组，存储实际数据
_size	当前列表中实际包含的元素个数
index	插入起始位置
collection	要插入的集合
count	要插入的元素数量
EnsureCapacity(...)	扩容函数，确保内部数组能容纳新元素
Array.Copy(...)	移动数组内容，腾出插入空间
_version	枚举器版本号，用于检测并发修改

---

3.主要功能

• 在指定索引位置插入一个集合中的所有元素；
• 插入后列表的实际大小（_size）会增加相应数量；
• 插入位置必须在 [0, Count] 范围内，否则抛出越界异常；
• 如果当前内部数组容量不足，则自动扩容（调用 EnsureCapacity）；
• 支持两种插入方式：
  • 批量插入（通过 ICollection<T> 接口获取 Count 并一次性复制）
  • 逐个插入（通过 IEnumerator<T> 遍历集合）
• 如果插入位置不是末尾，则将该位置之后的元素整体后移腾出空间；
• 对于插入自身集合的情况做了特殊处理，防止数据覆盖错误；
• 插入完成后更新 _size 表示元素数量变化；
• 增加 _version 版本号，用于防止 迭代过程中集合被修改（ConcurrentModificationException）；
• 不释放内存，仅改变逻辑状态，保留原有数组容量不变。

---

---

如何处理插入自身的情况？

这是非常关键的一点：

if (this == c)

如果你尝试把 List<T> 插入到它自己里面（比如 list.InsertRange(0, list)），如果不做特殊处理，直接 Array.Copy 会导致数据被覆盖。

因此代码做了两次拷贝：

• 第一次：前半段 [0, index) 插入到 index
• 第二次：后半段 [index, _size - index] 插入到 index * 2

这样就避免了数据被提前覆盖的问题。

---

4.时间复杂度

操作	时间复杂度
获取 Count	O(1)（如果是 ICollection<T>）
移动已有元素	O(n)，n 是当前元素数量
插入自身时拷贝	O(k)，k 是插入元素数量
使用 IEnumerator 逐个插入	O(k * n)（每次插入都可能移动元素）
总体时间复杂度	最坏 O(n + k)（如果是 ICollection<T>）或 O(k * n)（如果是普通枚举器）

---

5.示例说明

List<int> list = new List<int> { 1, 2, 3 };List<int> toInsert = new List<int> { 10, 20, 30 };list.InsertRange(1, toInsert);Console.WriteLine(string.Join(", ", list)); 
// 输出：1, 10, 20, 30, 2, 3

---

6.总结

功能	实现方式
插入集合	InsertRange(index, collection)
自动扩容	EnsureCapacity(size + count)
插入自身	分两次拷贝避免数据覆盖
集合类型判断	as ICollection<T>
一般集合插入	创建临时数组并拷贝
普通枚举器插入	使用 IEnumerator<T> 逐个调用 Insert()
版本控制	_version++ 防止并发修改错误

---

九、Enumerator结构体

1.代码解析

[Serializable]
public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
{// 指向当前正在遍历的 List<T> 实例private List<T> list;// 当前遍历到的索引位置private int index;// 版本号，用于检测在遍历过程中列表是否被修改（防止并发修改异常）private int version;// 当前遍历到的元素private T current;// 构造函数，由 List<T>.GetEnumerator() 调用internal Enumerator(List<T> list){this.list = list;index = 0;                      // 初始从索引 0 开始遍历version = list._version;        // 记录当前列表版本号current = default(T);           // 初始化为默认值}// Dispose 方法，用于释放资源（结构体中一般为空实现）public void Dispose(){// 不需要做任何事情}// 移动到下一个元素的方法，返回 true 表示还有元素，false 表示结束public bool MoveNext(){List<T> localList = list;// 如果版本号一致，并且索引未超出范围，则继续遍历if (version == localList._version && ((uint)index < (uint)localList._size)){// 获取当前元素current = localList._items[index];// 索引后移index++;return true;}// 否则调用 MoveNextRare 处理特殊情况（如越界或版本不一致）return MoveNextRare();}// 处理 MoveNext 的“罕见情况”：版本变化或索引非法private bool MoveNextRare(){// 如果版本号不同，说明列表在遍历过程中被修改了，抛出异常if (version != list._version){ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);}// 设置 index 为 _size + 1，表示已经遍历结束index = list._size + 1;current = default(T);return false;}// 获取当前元素（泛型版本）public T Current{get{return current;}}// 获取当前元素（非泛型版本）Object System.Collections.IEnumerator.Current{get{// 如果 index 是 0（尚未开始） 或者已经大于 size，说明无法获取有效元素if (index == 0 || index == list._size + 1){ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);}return Current;}}// 将枚举器重置为初始状态（从头开始）void System.Collections.IEnumerator.Reset(){// 如果版本号不一致，说明列表在遍历过程中被修改过，抛出异常if (version != list._version){ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);}// 重置索引和当前元素index = 0;current = default(T);}
}

---

2.关键变量

变量名	含义
list	当前正在遍历的 List<T> 实例
index	当前遍历的位置（索引）
version	用于记录构造枚举器时的列表版本号，用于检测是否被修改
current	当前遍历到的元素
_version	List<T> 内部字段，每次修改列表（如 Add、Remove）都会递增

---

为什么要有 version？

这是为了保证 foreach 的线程安全性和一致性。如果你在使用 foreach 遍历一个 List<T> 时，同时又修改了这个列表（比如调用了 Add() 或 Remove()），就会触发版本号不一致的错误，抛出：

InvalidOperationException: Collection was modified; enumeration operation may not execute.

这就是通过 version 来实现的。

---

3.主要功能

• 构造函数初始化：

  • 记录当前列表引用；
  • 设置起始索引为 0；
  • 保存当前列表版本号 _version，用于后续版本一致性检查；
  • 初始化当前元素为默认值。

• MoveNext()：

  • 是核心方法，控制迭代流程；
  • 检查版本号是否一致（确保列表未被修改）；
  • 若索引合法，获取当前元素并后移索引；
  • 否则调用 MoveNextRare() 进行异常处理。

• MoveNextRare()：

  • 如果发现版本号不一致，抛出 InvalidOperationException，提示“集合已修改”；
  • 否则设置索引为 _size + 1 表示遍历结束。

• Current 属性：

  • 泛型版本直接返回缓存的 current；
  • 非泛型版本做了额外边界检查以保证线程安全。

• Reset()：

  • 将索引重置为 0；
  • 清除当前元素；
  • 如果版本号不一致，抛出异常。

• Dispose()：

  • 因为是值类型（struct），没有托管资源需要释放，因此为空实现。

---

4.时间复杂度

操作	时间复杂度	说明
MoveNext()	O(1)	只是移动索引和简单判断
Current	O(1)	直接返回缓存的 current 值
Reset()	O(1)	仅重置索引和 current
Dispose()	O(1)	空操作

---

5.示例说明

List<int> numbers = new List<int> { 1, 2, 3 };foreach (int num in numbers)
{Console.WriteLine(num);if (num == 2){numbers.Add(4); // 修改列表 → 会抛出 InvalidOperationException}
}

输出结果：

1
2
System.InvalidOperationException: Collection was modified...

---

6.总结

功能	实现方式
支持 foreach 遍历	使用 Enumerator 结构体实现
版本控制	使用 version 和 _version 检测集合是否被修改
元素访问	通过 Current 属性获取当前元素
异常保护	避免在遍历过程中修改集合
Reset 支持	手动重置枚举器（很少使用）

---