25

C#, .NET4.

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:

  • Depending on how List is backed, do any memory allocations/deallocations happen after at RemoveAt() for compensating for the new size of the list? I know, for example, that resizing an array can be expensive (relatively speaking)
  • I always imagined Lists to behave like linked-lists, such that removing an element at the zero position would mean simply having the start-of-list reference adjusted from the previous zero element to what used to be the 1st element (but is now the first element). But, my 'imagination' and reality are not always in line.

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

CoolUserName
  • 3,715
  • 6
  • 26
  • 30
  • While I don't have a direct answer, I think you're confusing List with LinkedList, which are different: http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx - also, please see http://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist – Codesleuth May 18 '11 at 23:06
  • .NET would not have a Queue<> class if that was O(1). – Hans Passant May 18 '11 at 23:14

3 Answers3

26

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.

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

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

SLaks
  • 868,454
  • 176
  • 1,908
  • 1,964
  • 3
    Yes, it is. Most .NET collections besides linked lists are array-based. – Quick Joe Smith May 18 '11 at 23:12
  • @user90070 - SLaks is saying that List is really an object wrapper around Array that provides Add, Remove, and other List semantics. – Ritch Melton May 18 '11 at 23:13
  • I realized that there is in fact a built-in Queue class in .NET. Any benefit in going with that over LinkedList for this sort of activity? – CoolUserName May 18 '11 at 23:13
  • 2
    @user90070 - Queue is based on a linked list internally, so apart from the fact that you'd be reinventing the wheel using LinkedList, there should be little difference. – Will A May 18 '11 at 23:17
  • 1
    @user: LinkedLists has the added benefit of access to the nodes that make up the list. So it's easy to walk through the list in any direction from an inner node. Not as easy with most other collections. – Jeff Mercado May 18 '11 at 23:18
  • 3
    @will @user90070 Queue is based on a circular array, not a linked list. Either will work, depending on unmentioned requirements, as the performance characteristics should both be O(1) for the specified operation. All else being equal I'd go for the queue. – Kevin Pullin May 19 '11 at 03:32
  • @Kevin P - thanks Kevin, my apologies for the misinformation. – Will A May 19 '11 at 06:41
  • @SLaks What do you mean with *'unless you use random access'*? – VansFannel Nov 25 '17 at 17:19
  • 1
    @VansFannel: Accessing an element at an arbitrary index. – SLaks Nov 27 '17 at 15:22
13

It's O(n). It even says so on MSDN.

This method is an O(n) operation, where n is (Count - index).

Jeff Mercado
  • 129,526
  • 32
  • 251
  • 272
  • 1
    ...and .Net Reflector says ` Array.Copy(Me._items, (index + 1), Me._items, index, (Me._size - index))` - so I'll triple vouch for O(n). :) – Will A May 18 '11 at 23:08
  • 4
    Does this then imply that removing the last element in the list is O(1) ? – 3Pi Jun 25 '12 at 01:55
  • Not really @3Pi, because you are still doing an `Array.Copy` operation under the hood. – JwJosefy May 11 '16 at 17:45
  • Not to dwell on the subject but time complexity is a measure of the worst case. Removal is still `O(n)`. Removing the last element just happens to be the best case. – Jeff Mercado May 11 '16 at 18:00
  • @JwJosefy No, removing the last item does not copy anything. Since only the first `_size` values of the backing array matter, it doesn't make a difference what they are filled with (caveat, simplified: if it's a reference type it is set to `default(T)`, to remove the reference so that the object can be garbage collected). That's why only `_size` is reduced. – emilyisstewpid Dec 07 '22 at 11:12
4

From what I can tell, it should be an O(n) operation. Internally it uses Array.Copy (which is an O(n) operation) to copy the elements after 0 back into the list's backing array. From Reflector:

public void RemoveAt(int index) {
    if (index >= this._size) {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    this._size--;
    if (index < this._size) {
        Array.Copy(this._items, index + 1, this._items, index, this._size - index);
    }
    this._items[this._size] = default(T);
    this._version++;
}

So for any valid array index i, it copies all subsequent elements from i + 1 into i.

Quick Joe Smith
  • 8,074
  • 3
  • 29
  • 33
  • Yup - it's O(n) - I think I'm right in saying that you can't say it's 'very close to' O(n), O(n) + k = O(n), O(n) * 0.9 = O(n) etc. – Will A May 18 '11 at 23:23