列出操作复杂度

Question

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

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

这样的混合体

如果有人对 C# List 操作有一些 link 的复杂性，那就更好了。

Answer 1

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

List<T>.Insert:

This method is an O(n) operation, where n is Count.

List<T>.Add:

If Count already equals Capacity, the capacity of the List is increased by automatically reallocating the internal array, and the existing elements are copied to the new array before the new element is added.

If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

是的，根据需要增加容量，但是不，每个添加操作都不会增加容量。我们在documentation of the constructor in the reference source中可以看到，列表是有一定的基础容量的，每超过一次容量就会翻倍：

// 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>）中常见操作的复杂度：

Asymptotic complexity of .NET collection classes

列出操作复杂度

List operations complexity

.net

c#

list

data-structures