泛型列表中的list.RemoveAt(0)有多贵？

15 浏览
0 Comments

泛型列表中的list.RemoveAt(0)有多贵？

C#，.NET4.

我们有一些性能关键代码导致一些问题。实际上，它有点类似于修改过的队列，实际上由List支持。我想知道从索引0删除元素的成本如何。我所想到的问题是:

  • 根据List的后备方式，是否在RemoveAt()后会发生任何内存分配/释放以补偿列表的新大小？例如，我知道调整数组大小可能是昂贵的（相对而言）
  • 我总是想象Lists表现得像链表，因此从零位置删除元素将意味着仅将起始列表引用从先前的零元素调整为从前1个元素（但现在是第一个元素）。但是，我的“想象”和现实并不总是一致的。

我一直认为RemovedAt对于Lists来说是O（1）。是这种情况吗？

admin 更改状态以发布 2023年5月25日
0

2 答案

0 Comments

它的时间复杂度为O(n)。在MSDN上也有明确说明。

该方法的时间复杂度为O(n)，其中n为(Count - index)。

0
0 Comments

List是由一个简单的数组支持的，加上一个size字段，表示实际使用的数组的哪个部分（为了允许未来的增长）。
除非添加了太多的元素或调用了TrimExcess，否则数组不会被重新调整大小。

Remove是O(n)，因为它需要将列表的其余部分向下移动一个。

相反，您可以使用LinkedList（除非您使用随机访问），或编写自己的列表来跟踪前面的空白部分。

0