Collections: Picking the Right Container

Real-world analogy

What is it?

A collection is a container for many values, and each kind trades speed for features. Lists keep order and dictionaries look up by key. Sets keep unique values, and queues and stacks control the order of removal. Picking by how you will use the data, not by habit, often removes a whole class of slow code.

Real-world relevance

A report job loops over 50,000 orders and for each one calls blockedUsers.Contains(order.UserId) on a list. That is 50,000 scans of the list. Changing the list to a HashSet turns each check into one lookup. A job that took minutes finishes in seconds.

Key points

• Array versus List — An Array has a fixed size. A List<T> grows as you add, and is what you reach for by default.
• Dictionary: fast lookup by key — Dictionary<TKey,TValue> finds a value by key in about constant time, O(1). A List must scan from the start, which is O(n).
• What a key needs — A dictionary uses GetHashCode to pick a bucket and Equals to confirm the match. Keys must not change after you add them, or the lookup will fail.
• HashSet for uniqueness — HashSet<T> holds each value once and checks Contains in about O(1). List.Contains scans every item.
• Queue and Stack — A Queue is first in, first out, like a line of jobs. A Stack is last in, first out, like an undo history.
• The interface ladder — IEnumerable<T> can only be walked. ICollection<T> adds Count and Add, and IList<T> adds indexing. Each step up promises more.
• Accept wide, return narrow — Take the loosest type you need, often IEnumerable<T>, as a parameter. Return IReadOnlyList<T>, ideally from list.AsReadOnly(), so callers cannot cast it back and change your list.
• No edits inside foreach — Adding or removing items while you foreach a list throws InvalidOperationException. Loop over a copy, or use RemoveAll.

Code example

public record User(int Id, string Name);
public record Order(int UserId, decimal Total);

public static class Report
{
    // Slow: scans both lists for every order
    public static void Slow(List<Order> orders, List<User> users, List<int> blocked)
    {
        foreach (var order in orders)
        {
            if (blocked.Contains(order.UserId)) continue;
            var user = users.First(u => u.Id == order.UserId);
            Console.WriteLine($"{user.Name}: {order.Total}");
        }
    }

    // Fast: build the lookups once, then each check is one hash lookup
    public static void Fast(List<Order> orders, List<User> users, List<int> blocked)
    {
        var blockedIds = new HashSet<int>(blocked);
        var usersById = users.ToDictionary(u => u.Id);

        foreach (var order in orders)
        {
            if (blockedIds.Contains(order.UserId)) continue;
            if (usersById.TryGetValue(order.UserId, out var user))
                Console.WriteLine($"{user.Name}: {order.Total}");
        }
    }
}

Line-by-line walkthrough

1. 1. The records User and Order are small data shapes used by both methods.
2. 2. Slow calls blocked.Contains for every order. That scans the list each time.
3. 3. Slow also calls users.First for every order, which scans the users list each time. The work grows as orders times users.
4. 4. Fast builds a HashSet of blocked ids once, and a Dictionary of users by id once.
5. 5. Inside the loop, blockedIds.Contains and usersById.TryGetValue are each one hash lookup.
6. 6. TryGetValue also handles the missing-user case without throwing.

Spot the bug

var orders = new List<Order>
{
    new(1, "paid"), new(2, "cancelled"), new(3, "paid")
};

foreach (var order in orders)
{
    if (order.Status == "cancelled")
        orders.Remove(order);
}

public record Order(int Id, string Status);

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Collections in .NET (Microsoft Learn)
• Selecting a collection class (Microsoft Learn)