List with fixed capacity item removal process time / C#

Question

I have the following question:

List<int> list = new List<int>(10);
for (int i = 0; i < 10; i++)
   list.Add(i);

Now list.Count and list.Capacity are 10. It's OK. But what will happen when I will try to remove first item?

list.RemoveAt(0);

Count is now 9 and Capacity still 10, but what happened inside list? List had to go through all the elements like:

list[0] = list[1];
list[1] = list[2];
// etc...
list[9] = null;

?

May be it could be better just to do by myself smthng like:

list[0] = list[list.Count - 1];

? But items order will be changed in this case.

And how long will list.RemoveAt(0) take if I have a List with 10000000 elements with a preinitialized length? Will there be any difference if List will not have preinited length?

UPD:

Looked to the source (didn't know that they are in free access o.O ):

    // Removes the element at the given index. The size of the list is
    // decreased by one.
    //
    public void RemoveAt(int index) {
        if ((uint)index >= (uint)_size) {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }
        _size--;
        if (index < _size) {
            Array.Copy(_items, index + 1, _items, index, _size - index);
        }
        _items[_size] = default(T);
        _version++;
    }

So it really has Array.Copy inside. What a pity. Thanks to @TomTom.

What about you go int othe source of List and check and then write some tests? Obviously this is highly important to you. Anyhow, the ton of questions you have all make this quite too broad. — TomTom, Nov 18 '14 at 11:19
http://stackoverflow.com/questions/6052003/how-expensive-is-list-removeat0-for-a-generic-list you can see some details here, but for more than that you are going to have to run some tests. About "preinited length" - just read about how list works internally and it will be clear to you. — Moti Azu, Nov 18 '14 at 11:21
@TomTom Thnx! Checking sources really helped. Sorry but don't know the way to mark your comment as answer. — Anton Egorov, Nov 18 '14 at 11:28
@AntonEgorov Added my comment as answer so you can select it. — TomTom, Nov 18 '14 at 11:32

score 0 · Answer 1 · answered Nov 18 '14 at 11:20

0

Take a look at the LinkedList. It's only O(1) to remove item from it

answered Nov 18 '14 at 11:20

Max Brodin

3,903
1
14
23

Thnx but I really need to know how List.RemoveAt works – Anton Egorov Nov 18 '14 at 11:26

score 0 · Answer 2 · answered Nov 18 '14 at 11:25

As you pointed out for a generic List, a RemoveAt(0) operation will take O(N) for a list of N items. (as it will process N items). This is because a List is backed by an array.

Per MSDN, removing index I from a List with count C takes C - I. You can use this to answer your question around the initial capacity (no it doesnt help)

You can use other data structures, like a LinkedList which is written as a linked list (as the name suggest) and will remove the 1st item in O(1). However, other operations are significantly worse than a List

Thanks. Found the same in the List sources (didn't know that they can be free accessed). — Anton Egorov, Nov 18 '14 at 11:29

score 0 · Answer 3 · answered Nov 18 '14 at 11:31

This is what happens:

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

Look it up at:

http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,3d46113cc199059a

Double linked list is the fastest, or use unsafe pointer change.

Locality of reference is important, however. Dictionary or Hashsets are not indexable. You could always look at Red Black Trees for something in the middle( Removal O(LogN) ) — Erez Robinson, Nov 18 '14 at 11:36

score 0 · Accepted Answer · answered Nov 18 '14 at 11:32

What about you go int othe source of List and check and then write some tests? Obviously this is highly important to you. Anyhow, the ton of questions you have all make this quite too broad.

In general, since source are public if often helps to just look into them.

List with fixed capacity item removal process time / C#

4 Answers4