List剖析

List 继承于IList，IReadOnlyList，IList是提供了主要的接口，IReadOnlyList提供了迭代接口。

List内部是用数组实现的，而不是链表，并且当没有给予指定容量时，初始的容量为0。

每次增加一个元素的数据，Add接口首先检查的是容量还够吗，如果不够则用 EnsureCapacity 来增加容量。

在 EnsureCapacity 中，

int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;

每次容量不够的时候，整个数组的容量都会扩充一倍，_defaultCapacity 是容量的默认值为4. 所以整个扩充的路线为4，8，16，32，64，128，256，512，1024....

用数组形式作为底层数据结构，好处是使用索引方式提取元素很快，但在扩容的时候就很糟糕了，每次new数组都会造成内存垃圾，这给垃圾回收GC带来了很多负担。一次性扩充更多的数组容量为GC减轻了负担，但数组连续的new也还是GC的不小负担，特别是代码中List频繁使用的Add时。另外，如果数量不得当也会浪费大量内存空间，比如当元素数量为 520 时，List 就会扩容到1024个元素，如果不使用剩余的504个空间单位，就造成了大部分的内存空间的浪费。

Remove接口中包含了 IndexOf 和 RemoveAt，用 IndexOf 找到元素的索引位置，用 RemoveAt 删除指定位置的元素。删除的原理其实就是用 Array.Copy 对数组进行覆盖。IndexOf 启用的是 Array.IndexOf 接口来查找元素的索引位置，这个接口内部实现是就是按索引顺序从0到n对每个位置的比较，复杂度为O(n)。

与Add接口一样，先检查容量是否足够，不足则扩容。插入元素时，则以拷贝数组的形式，将数组里的指定元素后面的元素向后移动一个位置。

到这里，可以知道List的Add，Insert，IndexOf，Remove接口都是没有优化过的，如果过于频繁使用的话，会导致CPU使用过高，造成不少内存的冗余，也会使得垃圾回收(GC)时承担了更多的压力。

AddRange，RemoveRange的原理和Add与Remove是一样的，只是多了几个元素，把单个元素变成了以容器为单位的形式进行操作。都是先检查容量是否合适，不合适则扩容，以及Remove时先得到索引位置再进行整体的覆盖删掉的元素。

从上看得出来，代码是线程不安全的。所以最好别使用公用的 List 来添加，并发情况下，无法判断 _size++ 的执行顺序。

List 并不是高效的组件，真实情况是，他比数组的效率还要差的多，他只是个兼容性比较强得组件而已，好用，但效率差。