列出操作复杂性

本文关键字：复杂性 操作 | 更新日期: 2023-09-27 18:33:11

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

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

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

列出操作复杂性

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

List<T>.Insert ：

此方法是 O(n( 操作，其中 n 是计数。

List<T>.Add ：

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

如果计数小于容量，则此方法为 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 集合类的渐近复杂性
相关文章：