Lesson 31 of 62Intermediate16 min

List

By the end of this lesson

Use a growable list and understand its cost characteristics.

List holds a sequence of values like an array, and grows as you add to it. It is the collection you will reach for most often, and it is worth knowing what it does underneath, because two of its methods are much more expensive than they look.

You have already used one. The angle brackets in List<Order> say what kind of item the list holds; the final lesson in this module explains what that notation actually is.

The operations you will use every day

List<string> pendingApprovals = new List<string>();

pendingApprovals.Add("INV-2201");
pendingApprovals.Add("INV-2202");
pendingApprovals.Add("INV-2203");

Console.WriteLine(pendingApprovals.Count);              // 3
Console.WriteLine(pendingApprovals[1]);                 // INV-2202

pendingApprovals.Insert(0, "INV-2199");                 // put it at the front
pendingApprovals.Remove("INV-2202");                    // by value
pendingApprovals.RemoveAt(0);                           // by position

Console.WriteLine(pendingApprovals.Contains("INV-2203")); // True
Console.WriteLine(pendingApprovals.IndexOf("INV-2203"));  // 1

foreach (string reference in pendingApprovals)
{
    Console.WriteLine(reference);
}

pendingApprovals.Clear();
Console.WriteLine(pendingApprovals.Count);              // 0

Count is the number of items actually in the list. An array's Length is the number of slots; a list tracks the two separately, which is the bookkeeping it saves you.
Indexing with [1] works exactly as it does on an array, and is equally fast.
Remove takes a value and removes the first match. RemoveAt takes a position. Mixing them up is easy when the list holds numbers, because both calls compile.
Contains and IndexOf search from the start, item by item. On a list of ten that is free; on a list of a hundred thousand, inside a loop, it is the reason a report takes four minutes.

What it is doing underneath

A List is an array with management on top. It holds an internal array that is usually larger than the number of items, and remembers how many slots are in use. Count is that number; Capacity is the size of the internal array.

When you Add an item and the internal array is full, the list allocates a new array — typically double the size — copies every existing item across, and then stores the new one. That copy is proportional to how many items you already have, so it is not cheap.

It is also rare, and that is the point. Each doubling buys twice as many free Adds before the next one. Add a thousand items and you pay for roughly ten copies, totalling under two thousand item moves — so the average cost per Add stays flat no matter how large the list gets. The word for that is amortised: individual operations vary, but the average over a run of them is constant. Add is amortised constant time, not constant time, and the difference only matters if you care about one specific call rather than the total.

Rough cost of each operation, where n is the number of items:

list[i] — read or write by position: Constant. It is one calculation into the internal array, the same as on an array.
Add: Amortised constant. Cheap almost always; occasionally it allocates a bigger array and copies everything.
Insert at position 0, or anywhere but the end: Proportional to the number of items after that point, because they all shift up one slot. Inserting at the front of a large list repeatedly is a common accidental performance problem.
Remove, RemoveAt: Proportional to the items after the removed one, which shift down. Remove also has to find the item first.
Contains, IndexOf: Proportional to the number of items. Every item may be compared. If you are doing this often, a HashSet or Dictionary is the better structure.

Common mistake

Common mistakes

Adding to or removing from a list while a foreach over it is running. This throws InvalidOperationException, because the loop detects that the collection changed underneath it. Collect what you want to change into a second list, then act on it after the loop.

Removing inside a forward for loop. When you remove position 3, everything shifts down, so the old position 4 is now position 3 and your next pass skips it. Loop backwards from Count - 1, or use RemoveAll with a condition.

Treating Contains as free. Checking membership inside a loop over the same list means the work grows with the square of the size — fine at a hundred items, unusable at fifty thousand.

Assuming a List is safe to use from several threads. It is not. Concurrent additions can corrupt it in ways that surface much later as impossible-looking bugs. Use a lock or a collection from System.Collections.Concurrent.

Returning your private List from a public property and expecting it to stay yours. The encapsulation lesson covers this; the fix is IReadOnlyList.

Summary

A List is an array plus management: Count is items in use, Capacity is slots available
When the internal array fills, the list allocates a larger one and copies — usually doubling
Add is amortised constant: individual calls vary, the average stays flat
Index access is fast; Insert, Remove, Contains and IndexOf all scale with the number of items
Never add or remove while a foreach over the same list is running

Practice

Attempt each one before opening the solution. Getting it wrong first is how the idea sticks.

Try it yourself

Build a List of order references. Then remove every reference that ends in an odd digit, using a forward for loop, and print the result.

It will be wrong. Work out why from the output, then fix it two ways: looping backwards, and using RemoveAll.

Show solution

The forward loop skips items because removal shifts everything after the removed position down by one, while the loop counter still moves up. Two adjacent matches means the second one is never examined.

Looping backwards works because removing an item only shifts positions after it, and you have already passed those.

RemoveAll is the version to write in real code. It does one pass, is clear about intent, and cannot suffer this bug. Reaching for it does not remove the need to understand the problem, because the same shifting trap appears whenever you modify a collection you are walking.

List<string> references = new List<string>
{
    "INV-2201", "INV-2203", "INV-2204", "INV-2205", "INV-2208"
};

// Correct: walk backwards so removals only affect positions already visited.
for (int i = references.Count - 1; i >= 0; i--)
{
    int lastDigit = references[i][^1] - '0';

    if (lastDigit % 2 != 0)
    {
        references.RemoveAt(i);
    }
}

// Or say it in one line.
// references.RemoveAll(reference => (reference[^1] - '0') % 2 != 0);

foreach (string reference in references)
{
    Console.WriteLine(reference);
}

Think about it

A colleague says Add is constant time. Another says it is sometimes expensive because the list has to copy itself.

Both are describing something true. What is each one measuring, and which answer would you give if asked whether a loop of a million Adds is acceptable?

Show solution

The second colleague is describing the worst case of a single call, which really is proportional to the current item count when the internal array is full. The first is describing the average across many calls, which stays flat because each resize doubles the headroom.

For a million Adds the average is the number that matters, and the answer is yes, that loop is fine — roughly twenty resizes in total, and under two million item moves spread across a million calls.

The worst case matters when one individual call must be predictable, such as inside code with a hard timing budget. Pre-sizing the list with a capacity removes the resizes and therefore removes the question.

Saved in this browser only.