【Unity C#基础】浅谈List底层逻辑

1.内部实现

List实际是通过数组来实现的，而不是链表。并且没设定初始容量的情况下，初始容量默认为0。

2.扩容

每次容量不够时，数组容量会扩充一倍。按照4、8、16、32、64、128、256……递增。

按照2的指数进行扩容可以为GC减少负担。

每次扩容时，都会new一个新的数组，并抛弃旧数组，造成内存垃圾，为GC带来负担。

因此我们最好可以在创建List时，指定一个数组范围，避免扩容所带来的GC消耗。

3.Add、Remove、Insert

Add：会检测List容量是否需要扩容，并为对应的数组元素赋值。

Remove：通过IndexOf找到元素标号，在调用RemoveAt，通过标号删除元素。
删除过程实际上是通过Array.Copy对数组进行覆盖。

Insert：同Add一样，检测是否需要扩容，再通过复制数组的形式，将标号之后的元素都向后移动一个位置。

4.其它接口

（1）[]：直接使用数组索引方式调用。
（2）Clear：不删除数组，只对数组中元素设置0或者Null，并设置表示size的参数为0。
（3）Constant：for循环线性查找。
（4）ToArray：创建一个新数组，用于复制后的返回结果。频繁使用会会造成大量的内存分配。
（5）Find：for循环的线性查找。
（6）Enumerator：.Net4.0之前会产生大量的垃圾对象（Enumerator实例），4.0之后已修复此问题。
（7）Sort：使用快速排序进行排序，时间复杂度为O(nlgn)。

5.总结

List的效率不高，只是实用性强，可以对线性算法和内存分配方式进行优化。
在使用时尽量避免扩容等操作，频繁创建数组。
并且List时线程不安全的，在多线程中使用要加锁。