List <T> .Remove(T)或List <T> .RemoveAt(int)方法是否更快？

Question

.NET集合中的方法List<T>.Remove(T)或List<T>.RemoveAt(int)方法更快吗？值类型或引用类型的速度是否不同？

Answer 1

简单回答:

一般来说,RemoveAt虽然并不总是很快,但速度更快.

答案很长:

我们先考虑先找到合适的项目.该Remove方法必须在列表中搜索与给定对象匹配的项目,因此O(n)通常是时间.RemoveAt在列表上可以简单地索引给定项目,因此O(1).

现在,从列表末尾删除项目O(1)当然总是如此,但通常删除项目需要花费O(n)时间,因为需要进行重新排列(在删除项目之后移动项目).因此,在一般情况下,移除的总时间复杂度分别为O(n) + O(n)或者O(n) + O(1)对于Remove和RemoveAt,因此O(n)在任何一种情况下都是如此.但是,RemoveAt保证至少同样快,尽管缩放是相同的,除非你知道你在最后/接近结束时删除它.

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;
}