【C#知识点详解】List＜T＞储存结构详解

        今天来介绍一下List内部的存储结构，话不多说直接开始。

内部数据

        List内部采用了连续数组的方式存储数据，其中包含了三个重要的成员变量，示例如下：

// 用于存储数据的数组
internal T[] _items;
// 列表中实际包含数据的数量
internal int _size;
// 版本号，用于迭代时检测是否修改
internal int _version;

• T[] _items：存储数据的数组，实际存储数据的地方。
• int _size：实际包含数据的数量，用于记录_items实际存储数据的数量。
• int _version：版本号，List迭代时用于检测_items是否被修改。

        

数据操作

        添加数据

        List添加数据是在数据队列尾部进行添加（不是数组尾部），添加时会对_size计数进行增加，示例代码如下：

public void Add(T item)
{_version++;T[] array = _items;int size = _size;if ((uint)size < (uint)array.Length){_size = size + 1;array[size] = item;}
}

        当_items容积不够时，List会进行扩容，默认会扩容到原来的2倍。然后会创建一个新的newItems数组，并将原先的_items数据拷贝进去，示例代码如下：

internal void Grow(int capacity)
{int newCapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;if ((uint)newCapacity > Array.MaxLength) newCapacity = Array.MaxLength;if (newCapacity < capacity) newCapacity = capacity;Capacity = newCapacity;
}public int Capacity
{get => _items.Length;set{if (value != _items.Length){if (value > 0){T[] newItems = new T[value];if (_size > 0){Array.Copy(_items, newItems, _size);}_items = newItems;}}}
}

        

        移除数据

        List在移除数据的时候较常用的两个方法是Remove(T item)和RemoveAt(int index)。Remove()的执行过程也是先找到数据所在位置的索引，然后在调用RemoveAt()方法，示例代码如下：

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

        RemoveAt()的执行过程是将索引后的数据拷贝前移，拷贝完成后再将最后一位设置成默认值，示例代码如下：

public void RemoveAt(int index)
{_size--;if (index < _size){Array.Copy(_items, index + 1, _items, index, _size - index);}if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()){_items[_size] = default!;}_version++;
}

        

        插入数据

        List在插入数据时会调用Insert(int index, T item)接口，插入数据的执行过程与移除数据比较相似，插入数据是将索引位置的数据拷贝后移，然后将索引位置进行赋值，示例代码如下：

public void Insert(int index, T item)
{// Note that insertions at the end are legal.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++;
}

        

        访问数据

        在List中访问数据最常用的方式是索引访问，通过this[int index]直接获取修改数据。由于数据存储在_items数组中，访问数据时唯一需要注意的只有越界问题。示例代码如下：

public T this[int index]
{get{// Following trick can reduce the range check by oneif ((uint)index >= (uint)_size){ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();}return _items[index];}set{if ((uint)index >= (uint)_size){ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();}_items[index] = value;_version++;}
}

使用场景

        基于前面对List的介绍，List的使用场景可以归纳如下：

• List提供了灵活的数组存储空间，当数组元素数量不确定时可以选择List。
• List有较为灵活的数据访问机制，通过索引值即可访问数据，在需要随机访问数据时可以选择List。
• List存储的数据为连续的数组空间，在遍历数据时有较快的速度。
• List存储的数据为连续的数组空间，在频繁的添加/移除数据时，建议使用Add(T item)和RemoveAt(int lastIndex)方法，这两个方法是在数组尾部进行的数据操作。
• List存储的数据为连续的数组空间，在调用Insert(int index, T item)和RemoveAt(int index)方法插入/移除数据时，会进行数组数据的拷贝，所以不建议高频使用。需要高频在头部/中间插入/删除数据时可以使用LinkedList<T>。

相关文档链接

List官方文档：https://learn.microsoft.com/zh-cn/dotnet/api/system.collections.generic.list-1?view=net-9.0

List源码地址：

https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs