列出操作复杂性

Question

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

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

如果有人与C#List操作的复杂性有一些联系,那就太好了.

Answer 1

你的假设是对的.您可以找到MSDN上记录的操作的复杂性:

List<T>.Insert:

该方法是O(n)操作,其中n是Count.

List<T>.Add:

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

如果Count小于Capacity,则此方法为O(1)操作.如果需要增加容量以容纳新元素,则此方法变为O(n)操作,其中n为Count.

是的,容量会根据需要增加,但不会,每次添加操作的容量都不会增加.正如我们在参考源中的构造函数的文档中所看到的,列表具有一定的基本容量,并且每次超出时容量都会加倍:

// 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集合类的渐近复杂性