列出操作的复杂性 [英] List operations complexity

问题描述

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

I have always thought that List<T> in C#is a classic linked list, but recently I read that it is actually backed by array internally.

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

Does this mean that when we do insert to the start of the list it is O(n) operation because other elements needs to be moved one position further like in simple array? And every time we add a new item the new array with bigger capacity is created? Or it is some hybrid like ArrayList in Java?

如果有人对C#列表操作有一些复杂性的联系，那将是很好的.

If anyone has some link with complexity for C# List operations it would be good.

推荐答案

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

Your assumption is right. You can find the complexities of the operations documented on MSDN:

List<T>.Insert :

此方法是O(n)运算，其中n是Count.

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

List<T>.Add :

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

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.

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

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.

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

Yes, the capacity is increased as needed, but no, the capacity is not increased for every Add operation. As we can see in the documentation of the constructor in the reference source, lists have a certain base capacity, and the capacity is doubled every time it is exceeded:

// 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>)中常见操作的复杂性:

So, in a nutshell, choosing the right list depends on your needs. This answer compares the complexities of common operations in array-based lists (such as List<T>) and linked lists (such as LinkedList<T>):

• .NET集合类的渐近复杂性

这篇关于列出操作的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！