前言
在一次面试的时候，被问到List初始化容量，然后发现我都没用过初始化容量，一下暴露C#写得少。
List是一个C#中最常见的可伸缩数组组件，我们常常用它来替代数组，因为它是可伸缩的，所以我们在写的时候不用手动去分配数组的大小。甚至有时我们也会拿它当链表使用。那么到底它的底层是怎么编写的呢，每次增加和减少以及赋值，内部是怎么执行和运作的呢？
目录
· Add
· Insert
· Remove
· Find
· Clear
· foreach
· 总结
Add
在Add前，都会调用EnsureCapacity来保证有充足的空间存放元素，如果容量不足，就会进行扩容
每次容量不够的时候，整个数组的容量都会扩充一倍，_defaultCapacity 是容量的默认值为4。因此整个扩充的路线为4，8，16，32，64，128，256，512，1024…依次类推。
List使用数组形式作为底层数据结构，好处是使用索引方式提取元素很快，但在扩容的时候就会很糟糕，每次new数组都会造成内存垃圾，这给垃圾回收GC带来了很多负担。
这个就是我们平时写代码要注意的点：
使用List的时候，如果能提前知道List的最大容量，可以直接在初始化的时候初始化容量，这样List就不必频繁扩容，加剧GC负担了
public void Add(T item) {
if (_size == _items.Length) EnsureCapacity(_size + 1);
_items[_size++] = item;
_version++;
}
private void EnsureCapacity(int min) {
if (_items.Length < min) {
int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
if (newCapacity < min) newCapacity = min;
Capacity = newCapacity;
}
}
Insert
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);
}
Contract.EndContractBlock();
if (_size == _items.Length) EnsureCapacity(_size + 1);
if (index < _size) {
Array.Copy(_items, index, _items, index + 1, _size - index);
}
_items[index] = item;
_size++;
_version++;
}
插入的关键就是这句Array.Copy(_items, index, _items, index +1, _size - index);
把指定索引+1到数组末尾的元素向后移动，然后赋值，这个跟数组的插入删除一样，都要花费O（n）的时间去挪动数组。
Remove
public bool Remove(T item) {
int index = IndexOf(item);
if (index >= 0) {
RemoveAt(index);
return true;
}
return false;
}
public void RemoveAt(int index) {
if ((uint)index >= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}
Contract.EndContractBlock();
_size--;
if (index < _size) {
Array.Copy(_items, index + 1, _items, index, _size - index);
}
_items[_size] = default(T);
_version++;
}
删除跟插入相反，Array.Copy(_items, index +1, _items, index, _size - index);
Copy(Array sourceArray,int sourceIndex,Array destinationArray,int destinationIndex,int length)
用IndexOf(遍历)找到指定元素在数组中的索引，然后用指定索引+1到数组末尾的元素向前移动，覆盖。这个步骤，被删除元素后面的数都要往前移动。O(n)
因此，在使用List的时候，要注意，如果过于频繁使用的话，会导致效率降低，也会造成不少内存的冗余，使得垃圾回收(GC)时承担了更多的压力。
索引
直接数组下标访问
public T this[int index] {
get {
// Following trick can reduce the range check by one
if ((uint) index >= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}
Contract.EndContractBlock();
return _items[index];
}
set {
if ((uint) index >= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}
Contract.EndContractBlock();
_items[index] = value;
_version++;
}
}
Find接口使用的同样是线性查找，对每个元素都进行了比较，复杂度为O(n)。
Clear
public void Clear() {
if (_size > 0)
{
Array.Clear(_items, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
_size = 0;
}
_version++;
}
Clear接口在调用时并不会删除数组，而只是将数组中的元素清零，并设置 _size 为 0 而已，用于虚拟地表明当前容量为0。
foreach
一些情况下用foreach很合适，方便。而在Unity中使用C#，不允许使用foreach，所有foreach的地方统统用for/while代替，这如同教条般的存在，我一直没搞清楚具体原因，所有人的回答出乎意料的一致——foreach会产生额外的GC...这件事一直被我当知识点记着，知其然不知所以然。今天，我决定探索一下。
List<int> list = new List<int>();
public void Test()
{
foreach (int current in list)
{
Debug.Log(current);
}
}
反编译以后，foreach语法糖会被展开
private List<int> list = new List<int>();
public void Test()
{
using (List<int>.Enumerator enumerator = this.list.GetEnumerator())
{
while (enumerator.MoveNext())
{
int current = enumerator.get_Current();
Debug.Log(current);
}
}
}
public Enumerator GetEnumerator() {
return new Enumerator(this);
}
foreach每次获取迭代器时，会new一个Enumerator，如果大量使用迭代器的话，比如foreach就会造成大量的垃圾对象，这也是为什么我们常常告诫程序员们，尽量不要用foreach，因为 List 的 foreach 会增加有新的 Enumerator 实例，最后由GC垃圾回收掉。
至于那个产生额外GC的问题，已经在unity5.5解决了，详情分析见：李路亚：Unity/C# 漫谈一：foreach与GC
Sort
Array.Sort 使用的是快速排序方式进行排序，从而我们明白了 List 的 Sort 排序的效率为O(nlogn)。
总结
1. 使用List的时候，如果能提前知道List的最大容量，可以直接在初始化的时候初始化容量，这样List就不必频繁扩容，加剧GC负担了
2. 代码是线程不安全的，它并没有对多线程下做任何锁或其他同步操作。并发情况下，无法判断 _size++ 的执行顺序，因此当我们在多线程间使用 List 时加上安全机制。