列表操作复杂度

我一直认为List<T> in C#是一个经典的链表，但最近我读到它实际上是由数组内部支持的。

这是否意味着当我们插入到列表的开头时，它是 O(n) 操作，因为其他元素需要像简单数组一样进一步移动一个位置？每次我们添加一个新项目时，都会创建容量更大的新数组吗？或者它是某种混合体，例如ArrayList in Java?

如果有人对 C# 列表操作的复杂性有一些联系，那就太好了。

你的假设是正确的。您可以在 MSDN 上找到记录的操作的复杂性：

List<T>.Insert https://msdn.microsoft.com/en-us/library/sey5k5z4(v=vs.110).aspx:

此方法是一个 O(n) 操作，其中 n 是 Count。

List<T>.Add https://msdn.microsoft.com/en-us/library/3wcytfd1(v=vs.110).aspx:

如果Count已经等于Capacity，则通过自动重新分配内部数组来增加List的容量，并且在添加新元素之前将现有元素复制到新数组中。

如果 Count 小于 Capacity，则此方法的操作时间复杂度为 O(1)。如果需要增加容量以容纳新元素，则此方法变为 O(n) 操作，其中 n 是 Count。

是的，容量会根据需要增加，但是不会，容量不会增加every添加操作。正如我们在参考源中构造函数的文档 http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,49，列表有一定的基础容量，容量为doubled每次超过时：

// Constructs a List. The list is initially empty and has a capacity
// of zero. Upon adding the first element to the list the capacity is
// increased to 16, and then increased in multiples of two as required.
public List() {
    ...
}

因此，简而言之，选择正确的列表取决于您的需求。这个答案比较了基于数组的列表中常见操作的复杂性（例如List<T>）和链表（例如LinkedList<T>):

• .NET 集合类的渐近复杂度 https://stackoverflow.com/a/851972/87698