如何昂贵的是list.RemoveAt（0）的泛型列表？ [英] How expensive is list.RemoveAt(0) for a generic list?

问题描述

C＃，.NET4。

C#, .NET4.

我们有一些性能的关键code，它会引起一些问题。这是一个排序修改队列这实际上是正背靠名单。我不知道怎么贵指数移除元素0。问题浮现在脑海中：

We have some performance critical code that is causing some problems. It is sort of a modified queue which is in fact being backed by a List. I was wondering how expensive removing an element at index 0 is. Questions that come to mind are:

• 取决于如何列表备份，用于补偿表的新的大小做任何内存分配/取消分配后，发生在RemoveAt（）？我知道，例如，调整阵列可以是昂贵的（相对而言）
• 在我总是想象列表的行为类似于链接列表，使得在零位移除元素将意味着只要有启动-的列表参考从previous调零元到曾经被认为是第一元件（但现在的第一个元件）。但是，我的'想象力'与现实并不总是一致。

我一直以为RemovedAt是O（1）列出。是这样吗？

I always assumed that RemovedAt was O(1) for Lists. Is that the case?

推荐答案

名单，其中，T＆GT; 通过简单的数组支持，再加上尺寸字段，指示其中该阵列的一部分实际上是在使用中。 （考虑到未来的增长）。 数组不调整，除非你加了太多的元素或呼叫 TrimExcess 。

List<T> is backed by a simple array, plus a size field that indicates which portion of the array is actually in use. (to allow for future growth). The array isn't resized unless you add too many elements or call TrimExcess.

删除是 O（N），因为它需要在列表的其余部分向下一个班次。

Remove is O(n), since it needs to shift the rest of the list down by one.

相反，您可以使用的LinkedList＆LT; T＆GT; （除非你使用随机访问），或编写自己的列表，它跟踪在前面一个空的部分。

Instead, you can use a LinkedList<T> (unless you use random access), or write your own list which tracks an empty portion in front.

这篇关于如何昂贵的是list.RemoveAt（0）的泛型列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！