C# Generic Collections: A Step‑by‑Step Guide

Are you still reaching for List<T> by habit? In about 7 of 10 code reviews I do, that one choice quietly slows the app, increases memory use, or makes code harder to read. The fix is simple: pick the right collection up front and stick to a small set of proven recipes. This guide gives you that set.

What you’ll learn (quick peek)

• A clear way to choose between List<T>, Dictionary<TKey,TValue>, HashSet<T>, Queue<T>, Stack<T>, and sorted/linked/immutable options.
• Copy‑paste recipes for adds, lookups, updates, and set ops.
• When to use custom equality or ordering, and how to write it.
• Simple performance rules that save time without premature tuning.

My rule of thumb from real projects: if you ask “Do I only need fast membership checks?” use HashSet<T>. If you ask “Do I need key→value lookups?” use Dictionary<TKey,TValue>. Otherwise, start with List<T> but keep an eye on the cost of Contains and Remove.

The 80/20 view

You can solve 80% of collection needs with five types:

• List<T> – ordered, index based, great for append-heavy work.
• Dictionary<TKey,TValue> – key→value lookups.
• HashSet<T> – unique values and fast membership checks.
• Queue<T> – FIFO processing (first in, first out).
• Stack<T> – LIFO processing (last in, first out).

Other useful options:

• SortedDictionary<TKey,TValue> / SortedList<TKey,TValue> – kept in key order.
• LinkedList<T> – fast insert/remove when you already hold a node.
• ConcurrentDictionary<,>, ConcurrentQueue<T> – threads share safely.
• System.Collections.Immutable – safe sharing without locks.

Big‑O cheat sheet (common ops)

You rarely need exact constants. Picking the right shape wins you most of the gain.

Step 1 – Choose the right collection (decision guide)

• Need key→value with fast lookups? Dictionary<TKey,TValue>.
• Need “is this item present?” fast? HashSet<T>.
• Need a simple ordered bag you iterate a lot? List<T>.
• Need first‑come, first‑served processing? Queue<T>.
• Need back‑tracking/undo style processing? Stack<T>.
• Need items in sorted order at all times? SortedDictionary or SortedList.
• Need to insert/remove in the middle a lot while holding pointers to nodes? LinkedList<T>.
• Need safe shared access across threads without your own locks? Concurrent* types.
• Need to share snapshots safely between threads or across layers? Immutable* types.

If you’re unsure, start with List<T>, add tests, and watch hotspots with a profiler. When you see O(n) Contains calls in loops, switch to HashSet<T>.

Step 2 – List<T>: bread‑and‑butter recipes

Pre‑sizing matters when you know the approximate size. This cuts reallocation.

var capacity = 10_000;
var users = new List<User>(capacity);

Add/Insert/Remove

users.Add(new User { Id = 1, Name = "Ana" });
users.Insert(0, new User { Id = 0, Name = "Root" }); // shifts tail
users.RemoveAll(u => u.Name == "Root");

Sort with key selectors

users.Sort((a, b) => string.Compare(a.Name, b.Name, StringComparison.Ordinal));

Capacity control

users.TrimExcess(); // shrink internal array if there’s slack

Common pitfall: modifying while iterating.

// BAD: will throw if Remove executes during foreach
// foreach (var u in users) if (u.IsInactive) users.Remove(u);

// GOOD: build a new list or collect indexes first
users.RemoveAll(u => u.IsInactive);

In my team, switching a hot path from repeated Add without capacity to a pre‑sized list shaved ~25% off request time. Cheap win.

Step 3 – Dictionary<TKey,TValue>: key→value lookups that fly

Safe add / upsert patterns

var map = new Dictionary<string, User>(StringComparer.OrdinalIgnoreCase);

// Add if missing
map.TryAdd("ana", new User { Id = 1, Name = "Ana" });

// Get or default
if (map.TryGetValue("ana", out var user))
{
    Console.WriteLine(user.Name);
}

// Upsert (replace if exists)
map["ana"] = new User { Id = 1, Name = "Ana Maria" };

Batch updates without tearing the table

// Reserve when you know the size
var expected = 50_000;
var dict = new Dictionary<int, string>(capacity: expected);
for (int i = 0; i < expected; i++) dict[i] = $"user-{i}";

Avoid key exceptions

if (!map.ContainsKey("bob"))
{
    map.Add("bob", new User { Id = 2, Name = "Bob" });
}

Custom key equality

Strings are special. Use built‑in comparers for case rules:

var headers = new Dictionary<string, string>(StringComparer.OrdinalIgnoreCase);

For complex keys, provide a comparer. This avoids slow string joins or tuples in hot paths.

public sealed class UserKey : IEquatable<UserKey>
{
    public string Country { get; }
    public int Number { get; }

    public UserKey(string country, int number)
        => (Country, Number) = (country, number);

    public bool Equals(UserKey? other)
        => other is not null && Number == other.Number &&
           string.Equals(Country, other.Country, StringComparison.Ordinal);

    public override bool Equals(object? obj) => obj is UserKey k && Equals(k);

    public override int GetHashCode()
        => HashCode.Combine(Number, StringComparer.Ordinal.GetHashCode(Country));
}

var index = new Dictionary<UserKey, User>();
index[new UserKey("bg", 42)] = new User { Id = 42, Name = "Niki" };

If a key’s GetHashCode changes after insertion, all bets are off. Make key types immutable.

Step 4 – HashSet<T>: fast membership & de‑dupe

Typical uses

• Remove duplicates while keeping order
• Quick “have we seen this?” checks
• Set operations: union, intersect, except

Recipes

var emails = new[] { "a@x.com", "b@x.com", "a@x.com" };
var unique = new HashSet<string>(emails, StringComparer.OrdinalIgnoreCase);
Console.WriteLine(unique.Count); // 2

// Set ops
var left = new HashSet<int> { 1, 2, 3, 4 };
var right = new HashSet<int> { 3, 4, 5 };
left.IntersectWith(right); // left = {3,4}

Custom equality (structural compare without allocations):

public record Email(string Local, string Domain);

public sealed class EmailComparer : IEqualityComparer<Email>
{
    public bool Equals(Email? x, Email? y)
        => x is not null && y is not null &&
           string.Equals(x.Local, y.Local, StringComparison.OrdinalIgnoreCase) &&
           string.Equals(x.Domain, y.Domain, StringComparison.OrdinalIgnoreCase);

    public int GetHashCode(Email obj)
        => HashCode.Combine(
            StringComparer.OrdinalIgnoreCase.GetHashCode(obj.Local),
            StringComparer.OrdinalIgnoreCase.GetHashCode(obj.Domain));
}

var set = new HashSet<Email>(new EmailComparer())
{
    new("me", "site.com"), new("ME", "SITE.com")
};
Console.WriteLine(set.Count); // 1

Step 5 – Queue<T> and Stack<T>: simple workflows

Queue works well for background work. Pair it with a timer or a worker.

var q = new Queue<Job>();

void Enqueue(Job j) => q.Enqueue(j);

void Drain()
{
    while (q.Count > 0)
    {
        var job = q.Dequeue();
        job.Run();
    }
}

Stack is great for undo, DFS, or parsers.

var stack = new Stack<char>();
foreach (var ch in "(a+(b*c))")
{
    if (ch == '(') stack.Push(ch);
    if (ch == ')') stack.Pop();
}
Console.WriteLine(stack.Count == 0 ? "balanced" : "unbalanced");

ASCII mental models

Queue:  [head] -> [A] -> [B] -> [C] -> [tail]
Stack:  top -> [C]
               [B]
               [A]

Step 6 – Sorted and Linked options (when order matters)

SortedDictionary<TKey,TValue> keeps a balanced tree. Adds/gets are O(log n), always ordered by key. Good when you insert and remove often and still need order.

SortedList<TKey,TValue> stores keys in arrays. It shines when you have many lookups and few inserts/removes; lower memory than SortedDictionary.

LinkedList<T> is niche but handy. If you already hold a LinkedListNode<T>, you can insert or remove in O(1) with no shifting. It’s great for LRU caches (see later) and for splicing.

var sorted = new SortedDictionary<string, int>(StringComparer.Ordinal);
sorted["a"] = 1; sorted["c"] = 3; sorted["b"] = 2;
foreach (var (k,v) in sorted) Console.WriteLine($"{k}:{v}"); // a,b,c

Step 7 – Concurrency: share without drama

ConcurrentDictionary<,> and friends remove most manual locking for common cases.

Memoization / cache pattern

var cache = new ConcurrentDictionary<string, Task<string>>(
    StringComparer.Ordinal);

Task<string> GetDataAsync(string id)
    => cache.GetOrAdd(id, _ => FetchSlowAsync(id));

Producer–consumer with ConcurrentQueue<T> + SemaphoreSlim:

var cq = new ConcurrentQueue<Job>();
var gate = new SemaphoreSlim(0);

void Produce(Job j)
{
    cq.Enqueue(j);
    gate.Release();
}

async Task ConsumeAsync()
{
    while (true)
    {
        await gate.WaitAsync();
        if (cq.TryDequeue(out var job)) await job.RunAsync();
    }
}

If you need ordering and back‑pressure, consider Channel<T> from System.Threading.Channels.

Step 8 – Immutable collections: safe sharing

Immutable collections give you copy‑on‑write behavior. Each change returns a new instance; the old one stays valid.

using System.Collections.Immutable;

var list = ImmutableList<int>.Empty;
var list2 = list.Add(1).Add(2);
// list is still Empty, list2 is [1,2]

When to use:

• You pass a collection to other layers and want no accidental edits.
• You need thread safety without locks.
• You want value‑like semantics for state snapshots.

Cost: extra allocations. Use in state management or public APIs; keep hot loops on mutable types.

Step 9 – LINQ vs direct ops (and tiny perf checks)

LINQ reads well but adds iterator overhead and allocations. In low‑level loops, direct methods win.

// Clear intent, low overhead
var active = new List<User>(users.Count);
foreach (var u in users) if (u.Active) active.Add(u);

// Nice but allocates an iterator + new list
var active2 = users.Where(u => u.Active).ToList();

Membership: List<T>.Contains vs HashSet<T>

var items = Enumerable.Range(0, 100_000).ToList();
var set = new HashSet<int>(items);
var sw = Stopwatch.StartNew();
for (int i = 0; i < 100_000; i++) items.Contains(i);
sw.Stop();
Console.WriteLine($"List.Contains: {sw.ElapsedMilliseconds} ms");

sw.Restart();
for (int i = 0; i < 100_000; i++) set.Contains(i);
sw.Stop();
Console.WriteLine($"HashSet.Contains: {sw.ElapsedMilliseconds} ms");

On typical hardware you’ll see an order of magnitude gap. I show this snippet to juniors on day one.

Step 10 – Two practical mini‑patterns

10.1 Case‑insensitive email index (no duplicates)

public sealed class EmailIndex
{
    private readonly HashSet<string> _emails =
        new(StringComparer.OrdinalIgnoreCase);

    public bool Add(string email) => _emails.Add(email);
    public bool Exists(string email) => _emails.Contains(email);
}

10.2 Simple LRU cache (Dictionary + LinkedList)

public sealed class LruCache<TKey, TValue>
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Val)>> _map;
    private readonly LinkedList<(TKey Key, TValue Val)> _list = new();

    public LruCache(int capacity, IEqualityComparer<TKey>? cmp = null)
    {
        _capacity = capacity;
        _map = new Dictionary<TKey, LinkedListNode<(TKey, TValue)>>(cmp);
    }

    public void Set(TKey key, TValue value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            node.Value = (key, value);
            _list.Remove(node); _list.AddFirst(node);
            return;
        }
        if (_map.Count == _capacity)
        {
            var last = _list.Last!;
            _map.Remove(last.Value.Key);
            _list.RemoveLast();
        }
        var newNode = new LinkedListNode<(TKey, TValue)>((key, value));
        _list.AddFirst(newNode);
        _map[key] = newNode;
    }

    public bool TryGet(TKey key, out TValue value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            _list.Remove(node); _list.AddFirst(node);
            value = node.Value.Val;
            return true;
        }
        value = default!;
        return false;
    }
}

Pitfalls and guardrails

• Don’t modify during foreach. Use RemoveAll, or collect and remove after.
• Use the right comparer. Culture‑sensitive compares in keys can create odd bugs. Prefer Ordinal/OrdinalIgnoreCase for protocol and IDs.
• Don’t let GetHashCode depend on mutable fields. Keys must act like stones, not clay.
• Avoid ToList() unless you truly need a list. It hides allocations.
• Prefer IReadOnlyList<T> or IEnumerable<T> in public APIs. Keep freedom to change internals.
• Pre‑size big List<T> and Dictionary<,>. It avoids repeated growth.
• Be careful with struct as T. Boxing happens if you use non‑generic APIs.
• SortedList<,> vs SortedDictionary<,> choice. Many lookups/few writes: SortedList. Many writes: SortedDictionary.

A compact decision map (text form)

Key lookup? -> Dictionary<TKey,TValue>
Membership fast? -> HashSet<T>
Order by insertion and indexing? -> List<T>
FIFO processing? -> Queue<T>
LIFO processing? -> Stack<T>
Always sorted by key? -> SortedDictionary / SortedList
Hold node and splice often? -> LinkedList<T>
Thread sharing? -> Concurrent*
Safe snapshots / sharing? -> Immutable*

FAQ: Generic collections in real life

Conclusion: Pick once, move fast

Choosing the proper collection saves CPU, memory, and review time. Keep a short list of defaults, learn a few comparers, and reuse the patterns above. Your code stays clear, bugs drop, and performance gains come for free.

What collection swap gave you the biggest win? Share a case from your project-others will learn from it.