A Guide to C# List<T>: Adding, Removing, Capacity, Sorting and Searching

Version note: The code in this post uses C# 10 and the .NET 6 APIs; it was built and run with the .NET 10 SDK.

Guess First

We do not want to show out-of-stock books on the catalog page. We walk the list from start to end and remove the ones with zero stock. What does this code print?

List<Book> books = new()
{
    new("978-0441172719", "Dune", 12.99m, Stock: 4),
    new("978-0553293357", "Foundation", 9.50m, Stock: 0),
    new("978-0261102217", "The Hobbit", 10.99m, Stock: 0),
    new("978-0451524935", "1984", 8.99m, Stock: 7),
};

for (int i = 0; i < books.Count; i++)
{
    if (books[i].Stock == 0)
    {
        books.RemoveAt(i);
    }
}

Console.WriteLine(string.Join(", ", books.Select(b => b.Title)));

record Book(string Isbn, string Title, decimal Price, int Stock);

When the Index Shifts, an Element Gets Skipped

The output is Dune, The Hobbit, 1984. The Hobbit, with zero stock, stayed in the list. At i = 1 the loop removes Foundation. Removing shifts every element behind it one step forward; The Hobbit now sits at index 1. The loop, meanwhile, moves on to 2 with i++, and index 2 now holds 1984. Nobody ever looked at The Hobbit.

Picture checking tickets row by row in a cinema. If everyone slides over one seat the moment you send the person in seat 5 out, then when you move on to seat 6 you are actually looking at the person who was in seat 7. The one in between escapes the check.

Try the same thing with foreach and List<T> stops you more harshly. Call books.Remove(book) inside the loop and you get this exception:

Unhandled exception. System.InvalidOperationException: Collection was modified; enumeration operation may not execute.

List<T> keeps a version counter internally and bumps it on every change. The enumerator checks at each step whether the counter has changed, and refuses to go on if it has. Blowing up loudly is better than quietly producing a wrong result. There are two correct ways:

// books: the four-book list from the start of the post
List<Book> copy = new(books);

int removed = books.RemoveAll(b => b.Stock == 0);
Console.WriteLine($"RemoveAll: {removed} removed, left: {string.Join(", ", books.Select(b => b.Title))}");

for (int i = copy.Count - 1; i >= 0; i--) // back to front: shifting happens in the part already checked
{
    if (copy[i].Stock == 0)
    {
        copy.RemoveAt(i);
    }
}
Console.WriteLine($"Backwards: {string.Join(", ", copy.Select(b => b.Title))}");

RemoveAll: 2 removed, left: Dune, 1984
Backwards: Dune, 1984

RemoveAll is both readable and fast. It walks the list in a single pass, compacts the remaining elements in place, and returns how many it removed. Walking back to front also gives the correct result, but because every RemoveAt shifts the elements behind it again, it is slower than RemoveAll when you remove a lot.

There Is an Array Inside List<T>

All of this behavior comes from the fact that List<T> holds a plain T[] inside. Count tells you how many elements are in it, and Capacity tells you how many elements that array can hold. When the array is full, the list allocates a new array twice the size and copies everything over:

List<int> orderIds = new();
Console.WriteLine($"Count {orderIds.Count,2} -> Capacity {orderIds.Capacity}");

int lastCapacity = orderIds.Capacity;
for (int id = 1; id <= 20; id++)
{
    orderIds.Add(id);
    if (orderIds.Capacity != lastCapacity)
    {
        Console.WriteLine($"Count {orderIds.Count,2} -> Capacity {orderIds.Capacity}");
        lastCapacity = orderIds.Capacity;
    }
}

orderIds.Clear();
Console.WriteLine($"After Clear: Count {orderIds.Count}, Capacity {orderIds.Capacity}");

orderIds.TrimExcess();
Console.WriteLine($"After TrimExcess: Capacity {orderIds.Capacity}");

List<int> sized = new(1000);
sized.EnsureCapacity(1500);
Console.WriteLine($"Presized: Capacity {sized.Capacity}");

Count  0 -> Capacity 0
Count  1 -> Capacity 4
Count  5 -> Capacity 8
Count  9 -> Capacity 16
Count 17 -> Capacity 32
After Clear: Count 0, Capacity 32
After TrimExcess: Capacity 0
Presized: Capacity 2000

An empty list allocates no array at all. On the first Add the capacity becomes 4, and after that it doubles every time it fills up. It is like moving to a house twice as big whenever your things no longer fit. Moving is expensive, because every item goes to the new house one by one. But since the house doubles every time, the number of moves stays very small. Adding one million elements takes only about twenty moves. That is why the cost of Add is considered O(1) on average (amortized O(1)).

If you know how many elements are coming, say you are about to read 1000 rows from the database, give the capacity up front with new List<T>(1000) and skip all the moves. EnsureCapacity, new in .NET 6, does the same thing later on; as the output shows, it went to 2000 rather than the requested 1500, because when it grows it still prefers to double. Clear keeps the capacity, which is a good thing if you are going to fill the same list again. If you really want to give the memory back, you call TrimExcess.

Adding: Add, AddRange, Insert

List<string> titles = new() { "Dune", "1984" };

titles.Add("Foundation");
titles.AddRange(new[] { "The Hobbit", "Brave New World" });
titles.Insert(0, "Neuromancer");
titles.InsertRange(2, new[] { "Hyperion", "Solaris" });

Console.WriteLine(string.Join(" | ", titles));
Console.WriteLine($"Count: {titles.Count}, [2]: {titles[2]}, last: {titles[^1]}");

titles.Insert(20, "Snow Crash"); // ArgumentOutOfRangeException

Neuromancer | Dune | Hyperion | Solaris | 1984 | Foundation | The Hobbit | Brave New World
Count: 8, [2]: Hyperion, last: Brave New World
Unhandled exception. System.ArgumentOutOfRangeException: Index must be within the bounds of the List. (Parameter 'index')

Add appends to the end and is cheap. AddRange sets the capacity in one go when it knows the size of the incoming collection; it beats calling Add one by one in a loop. Insert adds in the middle, and the price is that every element after the insertion point shifts one step: O(n). If you keep inserting at the front of a list, you may have picked the wrong collection; we will see the alternatives in this series' post on Queue<T> and LinkedList<T>. The last line is a reminder too: the most you can pass to Insert is Count, so adding at the end is fine but leaving a gap is not.

Removing and Equality

RemoveAt(index) removes by position, Remove(item) by value. RemoveRange(index, count) removes a range, and Clear() removes everything. Remove's job is a little more subtle, because the answer to "is this element in the list?" depends on the type's definition of equality:

// books: the four-book list from the start of the post
bool bookRemoved = books.Remove(new Book("978-0553293357", "Foundation", 9.50m, 0));

List<CartLine> lines = new() { new CartLine("978-0441172719", 2) };
bool lineRemoved = lines.Remove(new CartLine("978-0441172719", 2));

Console.WriteLine($"Book removed: {bookRemoved}, count: {books.Count}");
Console.WriteLine($"Line removed: {lineRemoved}, count: {lines.Count}");

record Book(string Isbn, string Title, decimal Price, int Stock);

class CartLine
{
    public CartLine(string isbn, int quantity)
    {
        Isbn = isbn;
        Quantity = quantity;
    }

    public string Isbn { get; }
    public int Quantity { get; }
}

Book removed: True, count: 3
Line removed: False, count: 1

Remove uses EqualityComparer<T>.Default internally. A record considers two instances equal if all their properties are the same; that is why the Book we just created found the one in the list. An ordinary class, unless it overrides Equals, compares references: a new CartLine carrying the same values is not "the same" as the one in the list, and Remove quietly returns false. Contains and IndexOf follow the same rule. We cover equality in depth in the equality and comparison post of the OOP series.

Searching: The Find Family

using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

// books: the four-book list from the start of the post
Book? cheap = books.Find(b => b.Price < 10m);
int hobbitIndex = books.FindIndex(b => b.Title == "The Hobbit");
List<Book> outOfStock = books.FindAll(b => b.Stock == 0);
bool anyExpensive = books.Exists(b => b.Price > 50m);
bool allPriced = books.TrueForAll(b => b.Price > 0m);
Book? missing = books.Find(b => b.Title == "Snow Crash");

Console.WriteLine($"Find: {cheap?.Title}, FindIndex: {hobbitIndex}, FindAll: {outOfStock.Count}");
Console.WriteLine($"Exists: {anyExpensive}, TrueForAll: {allPriced}, missing: {missing?.Title ?? "(null)"}");

List<DateOnly> releaseDates = new() { new(1965, 8, 1), new(1951, 6, 1) };
DateOnly future = releaseDates.Find(d => d.Year > 2030);
Console.WriteLine($"Future release: {future}");

Find: Foundation, FindIndex: 2, FindAll: 2
Exists: False, TrueForAll: True, missing: (null)
Future release: 01/01/0001

Find returns the first element that matches the condition, FindLast the last one, FindIndex the index of the first (or -1 if there is none), and FindAll returns all of them in a new list. Exists and TrueForAll are the List<T>-specific counterparts of LINQ's Any and All. These methods predate LINQ and go back to .NET Framework 2.0; both styles are fine in new code.

Watch the last line: when Find finds nothing, it returns default(T). For a reference type that is null, which is easy to check. For a value type such as DateOnly, though, the result is January 1, 0001, which you cannot tell apart from a real date. On value type lists, using FindIndex and checking for -1 is safer.

All of these methods walk the list from start to end: O(n). That is nothing for ten elements, but not for a hundred thousand elements searched by ISBN on every request. The answer to that need is the subject of the next post: Dictionary and HashSet.

Sorting: Sort and Comparers

// books: the four-book list from the start of the post
try
{
    books.Sort();
}
catch (InvalidOperationException ex)
{
    Console.WriteLine($"{ex.Message} / {ex.InnerException?.Message}");
}

books.Sort((x, y) => x.Price.CompareTo(y.Price));
Console.WriteLine(string.Join(", ", books.Select(b => $"{b.Title} {b.Price}")));

books.Sort((x, y) => string.CompareOrdinal(x.Isbn, y.Isbn));
int index = books.BinarySearch(new Book("978-0451524935", "", 0m, 0), new IsbnComparer());
Console.WriteLine($"BinarySearch: {index} -> {books[index].Title}");

record Book(string Isbn, string Title, decimal Price, int Stock);

class IsbnComparer : IComparer<Book>
{
    public int Compare(Book? x, Book? y) => string.CompareOrdinal(x?.Isbn, y?.Isbn);
}

Failed to compare two elements in the array. / At least one object must implement IComparable.
1984 8.99, Foundation 9.50, The Hobbit 10.99, Dune 12.99
BinarySearch: 2 -> 1984

The parameterless Sort() expects the elements to know how to compare themselves; since Book does not implement IComparable<Book>, it blew up at run time. The overload that takes a lambda supplies the comparison from outside: negative means "x first," positive "y first," zero "equal." BinarySearch searches a sorted list in O(log n), but the list has to be sorted by the same rule. That is why using the same comparer in both places matters.

Sort has one more property: it is not stable. The relative order of elements that compare equal is not preserved. I sorted 40 books by stock; half have 0 in stock, half have 1, and their names run from Book00 to Book39:

List<Book> books = new();
for (int i = 0; i < 40; i++)
{
    books.Add(new Book($"Book{i:D2}", Stock: i % 2));
}

List<Book> sorted = new(books);
sorted.Sort((x, y) => x.Stock.CompareTo(y.Stock));
List<Book> ordered = books.OrderBy(b => b.Stock).ToList();

Console.WriteLine("Sort:    " + string.Join(" ", sorted.Take(8).Select(b => b.Title)));
Console.WriteLine("OrderBy: " + string.Join(" ", ordered.Take(8).Select(b => b.Title)));

record Book(string Title, int Stock);

Sort:    Book00 Book22 Book28 Book20 Book38 Book18 Book16 Book30
OrderBy: Book00 Book02 Book04 Book06 Book08 Book10 Book12 Book14

Sort gathered the zero-stock books at the front but scrambled their order among themselves. LINQ's OrderBy is stable; it keeps the original order of equal elements. If you want to show a list sorted by price and then by title, either put the second criterion into the comparison or use OrderBy(...).ThenBy(...). Also, Sort changes the list in place while OrderBy produces a new sequence; we will look at that difference in detail in the LINQ series.

Common Pitfalls

Changing the list while walking it. Calling Add or Remove inside foreach ends with an exception, and removing in a forward for loop ends with silently skipped elements. Use RemoveAll, or walk back to front.

Trusting Find's result on a value type list. When it finds nothing it returns 0, false or 01/01/0001. Use FindIndex and check for -1.

Using Remove and Contains with class elements without defining equality. A reference comparison is done, and a new object carrying the same data is never found.

Using a list as a structure you search on every request. On large lists that are searched often, Contains and Find walk from start to end every single time. If you need access by key, build a Dictionary.

Assuming Sort is stable. On small lists you may see the order preserved, but you cannot rely on it. The 40-book example above showed that clearly.

A Small Experiment

★☆☆ Fix the forward for loop from the start of the post so that it does not increment i when it removes something, and show that you get the same result as RemoveAll.

★★☆ Fill a 1000-element list first with new List<int>(), then with new List<int>(1000); count how many times the capacity changes.

★★★ Extend the comparison you pass to Sort so that it looks at price first and, if prices are equal, at the title. Add three books with the same price and verify that they now line up by title.

We have seen the cost of searching a List<T>. In the next post we move on to Dictionary<TKey, TValue>, which reaches values by key instantly, and to HashSet<T>, which holds unique elements: TryGetValue, key equality and comparers.