Under the hood: List.Contains(T)

30 Jan 2014

C#

One of the best things about .NET is the manner in which complex object collection querying can be performed with the addition of the LINQ extension. Add System.Linq into your using statements, and it's very simple to perform extensive and complex in memory collection querying. Sorting and searching is pretty much taken care of, leaving us to focus on the bigger picture.

But what's happening under the hood?

List.Contains(T) : Boolean

This method performs a linear search through the contents of the list, performing a compare operation for each item in the list. The best case scenario for this operation is 1, that is, the item being searched for is found during the first compare operation. The worst case scenario for this operation is n (the size of the list), as it's possible that the entire list must be searched.

The basic execution of this method looks something like this:

• Linear search
• Iterates through the entire list
• Performs a compare operation for each item in the list
• Exits as soon as the compare operation is satisfied
• Best case scenario: O(1)
• Worst case scenario: O(n)

Regardless of the type of program produced to probe the List mechanics, the same result was returned each time. The code for this method looks similar to this:

public bool Contains(T item) 
{ 
    EqualityComparer<T> comparer = EqualityComparer<T>.Default; 
    for (int i = 0; i < this._size; i++) 
    { 
        if (comparer.Equals(this._items[i], item)) 
        { 
            return true; 
        } 
    } 
    return false; 
} 

Performing a linear search over a small list yields a small worst case scenario, however performing a linear search over a large list yields a proportionally large worst case scenario. This might be obvious, at first, but as different types of searches perform better under certain conditions, it might be a good idea to match the appropriate search to the scenario.