.NET 数据结构：线性表 - 列表

列表同其他线性表一样，会将元素保存在一个集合内，并支持增改删查的操作。在使用列表时，通常无需考虑他的容量大小。

列表可以基于数组或链表实现：

数组：一个固定长度的列表。实现列表时，若元素数量超过容量大小，则需进行扩容操作。
链表：遍历性能较低，占用内存更多的列表。但它本身可以灵活地增改删查且无需扩容。

在.NET中，列表List<T>是基于数组实现的

实现代码片段

扩容操作

基于数组实现的列表均要考虑扩容问题，大多数语言会在列表初始化时预设一个容量(Capacity) 。在.NET中，这个预设值是4。

为什么要扩容

为了使列表的容量可变，数组的容量需要时刻检查。一旦新增的元素数量超过了当前数组的容量，则需要创建一个容量更大的数组，再将原有数组的元素复制进去。

比如说，对于一个容量为4的数组：

int[] Add(int[] arr, int element)  // 一个简单的添加元素实现，与语言实现不同
{
	int[] newArr = new int[arr.Length+1];
	for (int i=0; i<arr.Length; i++)  // 将旧数组的元素复制进新数组
	{
		newArr[i] = arr[i];
	}
	newArr[arr.Length] = element;  // 将元素放进数组的后面
	return newArr;
}

int[] arr = [1, 1, 4, 5];
arr = Add(arr, 1);  // 1, 1, 4, 5, 1

需要扩容多大

每次添加一个元素就要扩容一次当然是极其低效的，即使这可以节省一点内存。

在.NET中，扩容后长度增加一倍。

// System.Collections.Generic.List<T> Translated Source Code

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private int GetNewCapacity(int capacity)
{
    Debug.Assert(_items.Length < capacity);

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

    // 让列表扩容到最大的可能容量（大约2G的元素数据），防止溢出
    if ((uint)newCapacity > Array.MaxLength) newCapacity = Array.MaxLength;

    // 如果扩容力度不够，采用capacity的容量
    if (newCapacity < capacity) newCapacity = capacity;

    return newCapacity;
}

常用操作

初始化列表

创建一个空列表：

1	List<int> bad = new List<int>();

从已有的数组创建列表：

1 2	int[] s = [1, 1, 4, 5, 1, 4]; List<int> bad = new List<int>(s);

访问列表元素

由于.NET列表是基于数组实现的，在访问元素的效率上和数组相当。

1 2	int first = bad[0]; // 获取列表的第1个元素 bad[1] = 2; // 修改列表的第2个元素的值为2

添加，插入与删除

若未触发扩容操作，向列表后增加元素的时间复杂度是O(1)：

// 在列表的尾部添加元素
bad.Add(1);
bad.Add(9);

// 添加多个元素
bad.AddRange([1, 9, 8, 1, 0]);

插入和删除元素的时间复杂度均为O(n)：

1 2	bad.Insert(3, 0); // 在 bad 列表索引为 3 的位置插入 0 值 bad.RemoveAt(3); // 删除 bad 列表索引为 3 的元素

遍历

可以通过for或foreach关键字来遍历列表的元素，和数组类似：

// 通过 for 循环得到列表的索引，从而获取值
int total = 0;
for (int i=0; i<bad.Count; i++) {
    total += bad[i];
}

// 通过 foreach 得到列表的各个元素
total = 0;
foreach (int num in bad) {
    total += num;
}

排序

.NET的列表可以通过list.Sort()方法来让列表元素进行从小到大的排列。

对于更复杂的排序，譬如当元素是对象的时候，通过对象内的某个属性排序，则需要使用LINQ。

var personA = new Person(10, "A");
var personB = new Person(17, "B");
var personC = new Person(22, "C");
var personList = new List<Person> {personC, personA, personB};
/*
C(22) A(10) B(17)
*/
personList = personList.OrderBy(person => person.Age).ToList();
/*
A(10) B(17) C(22)
*/

class Person(int age, string name)
{
	public int Age {get; init;} = age;
	public string Name {get; init;} = name;
}

实践

场景：缓存清除操作

在一个播放器应用中，用户设置了1145 MB的最大缓存文件夹空间占用，在每次程序启动时，需要将该文件夹内的文件遍历删除（依据文件创建时间，从最旧的文件开始），直到文件夹占用小于用户的设定值。

如果只是考虑遍历删除，那么实现将不需要动脑子，但在删除的同时需要记录当前的文件夹容量，这就意味着在删除前：

拿到文件夹内的一长串FileInfo，以便于在遍历删除时既能获取到文件的大小和路径。
文件夹的总容量，可以使用LINQ获取所有FileInfo的容量，为了考虑文件夹大小判断时的颗粒度，我们需要将它们都对齐到字节水平。

回顾列表的特性，如果将FileInfo们从旧到新（即 Ascending）排序，那么我们总是需要删除列表的第一项，这会导致整个列表频繁的移动，增大性能开销。

这时候我们可以让它们从新到旧（即 Descending）排序，在每次删除的时候从尾部开始删即可，借助while循环在每次删除后判断文件夹大小是否减小到用户的设定值了。