List<T>.Remove(T) 方法和 List<T>.RemoveAt(int) 方法哪个更快？

Question

在.NET集合中，List<T>.Remove(T)方法比List<T>.RemoveAt(int)方法更快吗？对于值类型和引用类型，速度是否不同？

- abenci

Answer 1

简短回答：

通常情况下，RemoveAt更快，但差别并不是很大。

详细回答：

首先考虑找到要删除的项。Remove方法需要在列表中搜索匹配给定对象的项，因此通常情况下时间复杂度为O(n)。而对于列表的RemoveAt方法，可以直接按索引删除给定项，因此时间复杂度是O(1)。

当然，从列表末尾删除项总是O(1)的。但是，通常情况下删除项需要O(n)的时间，因为需要进行重排（将删除后的项之后的项向前移动）。因此，在一般情况下，删除操作的总时间复杂度分别为O(n) + O(n) 或者 O(n) + O(1)，即O(n)。但是，RemoveAt方法始终至少与Remove方法一样快，除非您知道要删除项在或靠近列表末尾。

- Noldorin

---

谢谢，我现在明白为什么MSDN说RemoveAt的时间复杂度是O(n)，其中n是Count-index。 - Yellowfog

Answer 2

List.Remove(T)的实现方法使用了IndexOf和RemoveAt(int)。因此，List.RemoveAt(int)更快。

public bool Remove(T item)
{
    int index = this.IndexOf(item);
    if (index >= 0)
    {
        this.RemoveAt(index);
        return true;
    }
    return false;
}

- DevExpress Team

---

但是如果这会使你的代码变得更糟糕或难以阅读，那么最好还是继续使用Remote(T)。 - Pierre-Alain Vigeant

this.IndexOf(item) 代码在性能方面的代价非常高，因为它会扫描整个支撑数组，直到找到要删除的项。特别是当要删除的项位于列表末尾时，每次请求删除时都会扫描整个列表。这曾经发生在我尝试使用 List<int> 类来实现一个堆栈数据结构时。随着列表大小的增长，例如超过10K个元素，使用 Remove(T) 从末尾删除可能会对程序造成严重破坏。 - RBT

Answer 3

Remove(T) 在内部调用 RemoveAt(int)，因此直接使用 RemoveAt 更快。

但是你想要实现什么？

- cRichter

Answer 4

鉴于 .Net 实际上是一个向量（或数组），而不是链表，因此 RemoveAt() 更快。

- Ian Ringrose

Answer 5

使用 System.Diagnostics.Stopwatch() 我会创建一个小的控制台应用程序来检查哪个更快。

- HarveySaayman