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.关键变量

3.主要功能

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

4.时间复杂度

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

5.示例说明

List<int> list = new List<int>(); // 初始容量为 0

list.Add(10); 
list.Add(20); 

for(int i = 0;i<list.length,i++){
	Console.WriteLine(list[i]); 
}

6.总结

二、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，则直接设置为 min
        if (newCapacity < min)
            newCapacity = min;

        // 设置新的容量（这会触发内部数组重新分配）
        Capacity = newCapacity;
    }
}

2.关键变量

3.主要功能

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

4.时间复杂度

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

5 示例说明

List<int> list = new List<int>(); // 初始容量为 0

list.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. 总结

三、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.关键变量

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.总结

四、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.关键变量

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(...) 的区别

6.总结

五、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.关键变量

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.总结

六、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.关键变量

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)

6.总结

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.关键变量

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.总结

九、InsertRange方法

1.代码解析

/// <summary>
/// 在指定索引位置插入一个集合的所有元素。
/// 如果当前容量不足，会自动扩容（通常是两倍或刚好满足需求）。
/// 插入位置可以是列表末尾（index == _size）。
/// </summary>
/// <param name="index">要插入的位置</param>
/// <param name="collection">要插入的集合</param>
public void InsertRange(int index, IEnumerable<T> collection)
{
    // 检查集合是否为 null
    if (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) 到目标位置 index
                Array.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.关键变量

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.时间复杂度

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.总结

九、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.关键变量

为什么要有 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.时间复杂度

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.总结