How is List<T> implemented in C#?

Question

I was thinking about the performance of calling List<T>.Indexof(item). I am not sure if it will be a O(n) performance for a sequential algorithm or O(log(n)) performance for a binary tree??

Thanks!

Answer 1

Behind the scenes a regular arrayis used, infact the IndexOf method simply calls Array.IndexOf. Since arrays don't sort elements, performance is O(n).

Answer 2

Using Reflector for .NET we can see:

public int IndexOf(T item)
{
    return Array.IndexOf<T>(this._items, item, 0, this._size);
}

public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
{
    return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
}

internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int num = startIndex + count;
    for (int i = startIndex; i < num; i++)
    {
        if (this.Equals(array[i], value))
            return i;
    }
    return -1;
}

Answer 3

It's O(n) according to MSDN.

This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.

Answer 4

List<T> is backed by a flat array, so list.IndexOf(item) is O(n).

Answer 5

If you need a faster performer, consider HashSet<T>. It's a speed vs. memory tradeoff, but it is worth it if you value the former over the latter.

(It's not exactly the same as a List<T>, it behaves like a single column dictionary, but for instances where you are going to have a unique list, it's one way to do it.)

Answer 6

List<T>.IndexOf is O(n) which is in fact optimal for an unordered set of n elements.

List<T>.BinarySearch is O(log n) but only works correctly if the List is sorted.

Answer 7

This is a old question, but I thought this link would be interesting: Experiment: List internals and performance when adding new elements