c# - 通用列表的 list.RemoveAt(0) 有多贵？

Question

C#、.NET4。

我们有一些性能关键代码导致了一些问题。它是一种经过修改的队列，实际上由列表支持。我想知道删除索引 0 处的元素有多昂贵。想到的问题是:

• 根据 List 的支持方式，是否会在 RemoveAt() 之后发生任何内存分配/取消分配以补偿列表的新大小？例如，我知道调整数组的大小可能很昂贵(相对而言)
• 我一直想象列表的行为类似于链表，这样删除零位置的元素就意味着简单地将列表起始引用从前一个零元素调整为曾经是第一个元素的元素(但是现在是第一个元素)。但是，我的“想象”和现实并不总是一致的。

我一直假设 RemovedAt 是列表的 O(1)。是这样吗？

Answer 1

List<T>由一个简单的数组支持，加上一个 size指示数组的哪一部分实际正在使用的字段。 (以允许 future 的增长)。除非您添加太多元素或调用 TrimExcess，否则不会调整数组大小.

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

---

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