So, when we have a list of integers / string / object and try to search an element in that list using LINQ.

Does LINQ perform binarysearch or linearsearch internally?

public class Person
{
    public string Name { get; set; }
    public string Address { get; set; }
}

and our LINQ, looks something like this:

List<Person> persons = new List<Person>();
persons.Where(x => x.Name == "kushal");

CodePudding user response：

Where is not a search for a single element. It's just a way to allow executing your predicate (a function that returns true or false) on each element and return elements where the predicate is true.

In order to move through the collection LINQ uses iterators so the movement depends on the iterator. List<T> has a dedicated iterator for Where. You can see this in .NET sources: public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate):

...
if (source is List<TSource> list)
{
   return new WhereListIterator<TSource>(list, predicate);
}

WhereListIterator's MoveNext in turn uses List's MoveNext and List<T>'s MoveNext moves one item at a time in the following fashion:

_current = localList._items[_index];
_index  ;

When you reason about this it's worth remembering that LINQ doesn't actually move through the list. Only when you enumerate the result of .Where - for example with foreach or ToList - the real work is done (moving through the elements and checking if the predicate is true).