How is List<T>.IndexOf() 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??

Oratorio

Answer 1

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

Wendling

Don't ever look at the code when there's detailed documentation. Sometimes the code is just an implementation detail, and there are no guarantees. – Ifill

@Ken Bloom: MSDN articles sometimes are very good, sometime are awful. So if you have a question about implementation of specific method, I think the best way - go and see how does it really implemented. – Wendling

When the code and comments disagree, both are probably wrong. – Galegalea

@Wendling do you have reflector for Add() method ? – Mastic

Answer 2

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.

Protease

Answer 3

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

Hertha

Answer 4

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.

Tuttle

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.)

Guncotton

Answer 6

My late answer but I think it worth mentioning that nowadays you can directly access to the MS sources: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

No more need for reflection since the .NET BCL code is now available online.

Implements a variable-size List that uses an array of objects to store the elements. A List has a capacity, which is the allocated length of the internal array. As elements are added to a List, the capacity of the List is automatically increased as required by reallocating the internal array.

As implemented as an array and performing a linear search, you can easily deduce that the algorithmic complexity of the IndexOf method is O(n).

As mentioned by others the information are publicly available on the msdn: https://msdn.microsoft.com/en-us/library/e4w08k17(v=vs.110).aspx

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

Again, you can check out the sources and end up seing that the static helper method IndexOf of the Array class is actually called behind the scenes:

http://referencesource.microsoft.com/#mscorlib/system/array.cs

If the list / array is already sorted beforehand you can then rather use a binary search: https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx

This method is an O(log n) operation, where n is the number of elements in the range.

Adele

Awesome! Thanks so much for that. I don't care what people say, sometimes you just gotta look at the source code. – Ending

Answer 7

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).

Benefactress