C#中List＜T＞底层原理剖析

1. 基础用法

list.Max() 取最大元素

list.Avgage() 取平均值

static void Main()
{List<string> names = new List<string>();names.Add("一号元素");names.Add("二号元素");names.Add("狗");names[2] = "三号元素";//修改第三个元素string[] str = new string[] { "四号元素", "五号元素", "六号元素" };names.AddRange(str);//为集合增加数组Console.WriteLine("当前集合元素个数为{0}",names.Count);//返回集合元素个数Console.WriteLine("当前集合的容量为{0}", names.Capacity);//返回当前集合的容量//当添加元素的时候集合的容量不足以容纳所有元素就会自动增加目前元素数一倍的容量。Console.WriteLine(names.Contains("三号元素"));//返回集合中是否存在某元素，bool类型names.IndexOf("三号元素");//返回元素的索引值names.Clear();//清空所有元素，元素个数为0，但是容量不变
}

2. List的Capacity与Count：

• Count 属性表示 List 中实际包含的元素数量。它是一个只读属性。
• Capacity 属性表示 List 内部数组的容量，即它可以容纳的元素的数量。容量是指分配给列表的内部数组的大小，而不是列表中实际包含的元素数量。
• 当添加元素时，如果内部数组的容量不够，List 会自动调整容量以容纳更多的元素。

List<int> list1= new List<int>();
WriteLine($"List的初始容量：{list1.Capacity}"); 
WriteLine($"List的初始数量：{list1.Count}");
list1.Add(0);
WriteLine($"通过Add()添加一个元素后的容量：{list1.Capacity}");
WriteLine($"通过Add()添加一个元素后的数量：{list1.Count}");

以上代码输出：

List的初始容量：0
List的初始数量：0
通过Add()添加一个元素后的容量：4
通过Add()添加一个元素后的数量：1

3.List的底层原理

3.1. 构造

private class List<T> : Ilist<T>, System.Collections.IList, IReadOnlyList<T>

List内部是由数组实现的，当没有指定额定容量时，初始容量为0。

3.2 Add()接口

将给定对象添加到此列表的末尾。每次增加元素前，都会判断数组容量是否够。不够则进行扩容。

public void Add(T item)

• 每次扩容都会扩充一倍。数组初始值为0，扩容初始值为4，因此整个扩容路线是：0-4-8-16-32-64-125-256……
• 每次扩容都会申请新的空间，然后进行元素拷贝，然后还要回收旧空间。会给GC造成不小的负担。
• 另外还有浪费空间的缺点。比如存放126个元素时，会扩容到256的空间，剩下的130个空间就浪费了。

3.3 Remove()接口

删除列表中首次出现的item。将从头到尾搜索，使用Object.Equal()进行相等的判断。

public bool Remove(T item)

• 找到要删除的位置后，使用Array.Copy()进行覆盖;
• 时间复杂度O(n);
• 删除一个元素后，内部数组的容量不变。

3.4 Inster()接口

功能：在给定索引处插入元素。每次插入元素前都会检查当前容量是否足够，如果不够则进行扩容。

public void Insert(int index, T item);

• 在插入元素时，采用的也是复制数组的形式，将数组指定索引后面的元素向后移动一个位置。
• 与Add()类似，会给GC产生负担，并且存在空间浪费的问题。

3.5 Clear()接口

功能：清除列表内容。注意：只是将Count置，之前申请空间不变，也就是Capacity不变。

List<int> list1= new List<int>();
list1.Add(0);
WriteLine($"通过Add()添加一个元素后的容量：{list1.Capacity}"); 
WriteLine($"通过Add()添加一个元素后的数量：{list1.Count}");
list1.Clear();
WriteLine($"Clear后的容量：{list1.Capacity}"); //清除后容量不变。即之前申请的空间不变
WriteLine($"Clear后的数量：{list1.Count}"); //数量置0

以上输出：

通过Add()添加一个元素后的容量：4
通过Add()添加一个元素后的数量：1
Clear后的容量：4
Clear后的数量：0

3.6 Contains()接口

功能：确定某元素是否在List中。

public bool Contains(T item)

• 使用线性查找的方式，挨个比较元素。

3.7 ToArray()接口

复制列表到一个新数组，O(n)的操作。

public T[] ToArray()

3.8 Find()接口

功能：查找满足指定条件的元素。接受一个Predicate委托作为参数，该委托定义了要应用于每个元素的条件。

public T Find(Predicate<T> match)

• 线性查找的方式，挨个比较，返回满足条件的第一个元素。
• 用法：

  List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
  // 使用Find函数查找大于3的第一个元素
  int result = numbers.Find(x => x > 3); //Lambda表达式x => x > 3表示条件
  Console.WriteLine(result);  // 输出: 4
  

3.8 Sort()接口

功能：对列表中的元素进行排序。Sort 方法使用元素的默认比较器进行排序，或者可以传递一个自定义的比较器作为参数。

public void Sort(int index, int count, TComparee<T> comparer)

• index与count是指定排序区间。不指定的话则整个列表进行排序；
• 用法

  List<int> numbers = new List<int> { 5, 2, 8, 1, 3 };
  numbers.Sort();
  numbers.Sort((x, y) => y.CompareTo(x));// 使用自定义比较器对列表进行降序排序
  

• 该方法在原地修改列表，而不是返回排序后的列表。
• 排序时使用Array.Sort()方法进行排序，该方法内部采用了快速排序，效率是O(nlogn).

4. 总结

1. List的效率并不高，甚至比数组还差，只是通用性强而已；
2. List 的内存分配方式也不合理。当List 里的元素不断增加时，会多次重新分配数组，导致原来的数组被抛弃，造成回收的压力。
3. 对于第2点的问题，我们可以在创建List 实例时提前告知 List 对象最多会有多少元素在里面，这样 List 就不会因为空间不够而抛弃原有的数组去重新申请教组了。例如：

   List<int> list11 = new List<int>(128);
   WriteLine($"容量：{list11.Capacity}"); //容量：128
   WriteLine($"数量：{list11.Count}"); //数量：0
   

4. List是线程不安全的。
   • 当多个线程同时访问和修改同一个 List 实例时，可能会导致不可预测的结果或发生错误。
   • 例如，并发读写的问题。一个线程正在读取列表的元素，而另一个线程在同时修改列表，这可能导致读取到无效或不正确的数据。
   • 可使用同步机制解决该问题。lock语句或其他同步机制来保护对 List 的并发访问。确保同一时间只有一个线程访问列表。

5. 参考

List源码地址：链接: https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs