C# Collections: Picking Between List, Dictionary and HashSet

Most C# code uses List<T> for everything. That is fine until a list gets big and a Contains check inside a loop turns a page load into a timeout. This post covers what each of the main collections actually does internally, what that costs, and how to choose. It leans on generics for the type safety, equality for how keys work, and IEnumerable for how they are iterated.

The four you need

Ninety percent of real code needs four collections, and each answers a different question.

Collection	The question it answers	Lookup	Add	Remove
List<T>	”what is at position 7, in order?”	O(1) by index, O(n) by value	O(1) amortised	O(n)
Dictionary<K,V>	”what is the value for this key?”	O(1)	O(1) amortised	O(1)
HashSet<T>	”have I seen this before?”	O(1)	O(1) amortised	O(1)
Queue<T> / Stack<T>	”what do I process next?“	n/a	O(1)	O(1)

The bold entries are the whole point. If you are searching by value rather than by position, a list is the wrong tool and the cost grows with your data.

List: an array that resizes itself

Internally a List<T> is a T[] plus a count. Adding beyond the array’s capacity allocates a new array of double the size and copies everything across.

var books = new List<Book>();     // capacity 0
books.Add(a);                     // allocates capacity 4
// ... 4 items later: allocate 8, copy 4
// ... 8 items later: allocate 16, copy 8

That doubling is why Add is amortised O(1): most adds are free, occasional ones copy everything, and the average works out constant. But the copies are real, and if you know the size up front you can skip all of them:

var books = new List<Book>(capacity: 10_000);   // one allocation, no copying

For a large, known size that is a genuine and free win.

Two other things follow from “it is an array”:

Indexing is O(1), the address is arithmetic. Everything by value is O(n), Contains, IndexOf, Remove and Find walk the array from the start. And Insert(0, x) or RemoveAt(0) shift every remaining element, so they are O(n) too.

Dictionary<K,V>: hashing, as covered

A Dictionary computes GetHashCode() on the key, uses it to pick a bucket, then compares with Equals inside that bucket. That is why a lookup does not depend on the number of items, and why the equality post matters so much: a broken GetHashCode produces a dictionary you cannot read back.

The API worth knowing, because the choice between these is a common review comment:

var byId = new Dictionary<int, Book>();

byId[1] = book;                              // add or overwrite
byId.Add(1, book);                           // throws if the key already exists
byId.TryAdd(1, book);                        // returns false instead of throwing

var b = byId[99];                            // throws KeyNotFoundException
if (byId.TryGetValue(99, out var found)) {}  // one lookup, no exception
if (byId.ContainsKey(99)) { b = byId[99]; }  // two lookups, avoid

TryGetValue is the right default: it does one hash lookup instead of two, and it makes “missing” a normal outcome rather than an exception. ContainsKey followed by the indexer is the single most common avoidable inefficiency in C# code.

Also worth knowing: dictionary enumeration order is not defined. It happens to reflect insertion order today in many cases, and relying on that is a bug waiting for a resize. If order matters, use SortedDictionary<K,V> (a tree, O(log n)) or sort at the point of display with OrderBy.

HashSet: a dictionary with no values

Same machinery, membership only.

var seen = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
if (!seen.Add(isbn))
    Console.WriteLine("duplicate");    // Add returns false if already present

Add returning a bool is a neat idiom: test and insert in one operation. HashSet<T> also does set algebra in place (UnionWith, IntersectWith, ExceptWith, IsSubsetOf), which is faster and clearer than the LINQ equivalents when you are mutating.

The O(n²) loop

This is the reason to know any of the above:

// bad: for every book, scan the whole banned list
var flagged = new List<Book>();
foreach (var book in books)                     // n
{
    if (bannedIsbns.Contains(book.Isbn))        // O(m), List.Contains scans
        flagged.Add(book);
}

With 10,000 books and 10,000 banned ISBNs, that is up to 100 million string comparisons. One line fixes it:

var banned = new HashSet<string>(bannedIsbns, StringComparer.OrdinalIgnoreCase);   // O(m) once

foreach (var book in books)
    if (banned.Contains(book.Isbn))             // O(1) each
        flagged.Add(book);

100 million comparisons become 20,000 hash lookups. This exact shape (a Contains against a list, inside a loop) is worth grepping your codebase for. LINQ’s Join and GroupJoin do the same trick internally by building a lookup first, which is why books.Join(banned, ...) is fast while a nested Where(b => banned.Any(x => x == b.Isbn)) is not.

Queue, Stack and LinkedList

Queue<T> is FIFO: Enqueue at the back, Dequeue from the front, both O(1). Use it for work items, breadth-first traversal, or anything processed in arrival order. Note that Dequeue throws when empty; TryDequeue does not.

Stack<T> is LIFO: Push, Pop, both O(1). Use it for undo history, depth-first traversal, or unwinding nested structures.

LinkedList<T> is a doubly linked list. Textbooks love it because inserting in the middle is O(1). In practice it is almost always slower than List<T>, because every node is a separate heap allocation and traversal jumps around memory instead of streaming through a contiguous array: CPU caches punish that severely. You still pay O(n) to find the position you want to insert at. Reach for it only when you hold node references and splice frequently, which is rare.

SortedDictionary<K,V> / SortedList<K,V> / SortedSet<T> maintain order at O(log n) per operation. Use them when you genuinely need sorted iteration or range queries; otherwise a dictionary plus OrderBy at the end is faster.

Read-only, immutable and concurrent

Three families worth knowing exist, because returning the wrong one leaks control.

Read-only wrappers. IReadOnlyList<T> and IReadOnlyDictionary<K,V> say “you cannot change this through this reference”. They are views, not copies: the underlying list can still be modified by whoever owns it. Good for expressing intent on a return type; not a safety guarantee.

Immutable collections (ImmutableArray<T>, ImmutableList<T>, ImmutableDictionary<K,V>) genuinely cannot change. Every “modification” returns a new collection sharing most of its internal structure. They are the collection equivalent of the records post, and they solve the shallow-immutability hole records leave.

public record Order(int Id, ImmutableArray<Book> Items);   // actually immutable, and compares by value

Concurrent collections (ConcurrentDictionary<K,V>, ConcurrentQueue<T>, ConcurrentBag<T>) are safe for multiple threads. A plain Dictionary written from two threads does not just lose an entry: a concurrent resize can corrupt the internal buckets and send a later read into an infinite loop. ConcurrentDictionary.GetOrAdd is the standard cache idiom. Threading gets its own post later in this series.

Choosing, in four questions

1. Do I look things up by a key or an id? → Dictionary<K,V>.
2. Do I only need to know whether something is present, or to deduplicate? → HashSet<T>.
3. Does order of processing matter, first in, or last in? → Queue<T> or Stack<T>.
4. Otherwise → List<T>. It is the right default for an ordered sequence you mostly iterate.

And when you find yourself calling Contains, Any(x => x.Id == id) or FirstOrDefault(x => ...) on a list inside a loop, that is the signal to build a dictionary or set first.

One API-design note that ties to the IEnumerable post: accept the weakest type, return a concrete one. Take IEnumerable<T> as a parameter so callers can pass anything, and return IReadOnlyList<T> or List<T> so callers know the work is done and can safely enumerate it twice.

The same idea inside Java, Python and Go

The names change; the data structures do not.

Java (Netflix, Android). ArrayList is List<T>, HashMap is Dictionary, HashSet is HashSet, ArrayDeque covers both Queue and Stack. Java’s hashCode/equals contract is identical, and so is the bug. One notable difference: Java’s HashMap allows a null key, C#‘s Dictionary throws.

Python. list, dict and set are built into the language syntax, which is a strong hint about how often you need all three. Python guarantees dict preserves insertion order since 3.7, a guarantee C# deliberately does not make. collections.deque is the queue.

Go (Google). Slices and maps, built in, and that is nearly all of it. map[string]bool is the idiomatic set because Go has no set type. Go’s maps deliberately randomise iteration order to stop people depending on it, the same lesson C# teaches by leaving it undefined.

JavaScript (Meta). Arrays, plus Map and Set added in ES6 for exactly the reason above: people were using plain objects as dictionaries and hitting key coercion and prototype bugs. array.includes() inside a loop is the same O(n²) mistake, and swapping in a Set is the same fix.

Rust. Vec<T>, HashMap<K,V>, HashSet<T>, VecDeque<T>, same four, and the Hash and Eq traits must be derived together, so the broken-key bug is much harder to write.

Summary

• List<T> is a self-resizing array: O(1) by index, O(n) by value. Pre-size it with a capacity when you know the count.
• Dictionary<K,V> and HashSet<T> are hash-based: O(1) lookup, at the cost of a correct GetHashCode/Equals on the key.
• Contains on a list inside a loop is O(n²). Build a HashSet first and it becomes linear.
• Prefer TryGetValue over ContainsKey plus the indexer, one lookup instead of two, and no exception.
• Dictionary enumeration order is undefined; use a sorted collection or OrderBy when order matters.
• Queue<T> is FIFO, Stack<T> is LIFO, both O(1). LinkedList<T> is nearly always slower than a list in practice because of allocation and cache behaviour.
• Immutable collections give real immutability and structural sharing; read-only interfaces only express intent.
• A plain Dictionary accessed from multiple threads can corrupt itself; use ConcurrentDictionary.
• Accept IEnumerable<T>, return IReadOnlyList<T>.

---

Interview questions and answers

1. What is the difference between an array and a List?

An array has a fixed length set at creation. List<T> wraps an array and grows it by allocating a larger one and copying when capacity is exceeded, so it supports Add and Remove. Both give O(1) indexing; the list trades a small overhead for a resizable API.

2. How does List grow, and what does that cost?

When the backing array is full, it allocates a new array of double the capacity and copies the existing elements. Individual adds are therefore O(n) occasionally and O(1) usually, giving amortised O(1). Supplying an initial capacity avoids the intermediate allocations and copies entirely.

3. How does a Dictionary achieve O(1) lookup?

It calls GetHashCode() on the key to select a bucket, then compares candidates in that bucket with Equals. The number of items in a bucket stays small as the dictionary resizes, so lookup time does not grow with the total count. Correct hashing is essential; a key type whose hash does not match its equality breaks lookups.

4. What is the difference between Dictionary and HashSet?

HashSet<T> stores only keys, answering membership questions and deduplicating. Dictionary<K,V> stores a value alongside each key. They use the same hashing machinery and have the same performance characteristics and the same requirements on the key type.

5. When would you use a Queue or a Stack?

Queue<T> for first-in-first-out processing: work items, message handling, breadth-first search. Stack<T> for last-in-first-out: undo history, expression evaluation, depth-first traversal. Both give O(1) add and remove at their respective ends, which a List<T> cannot for the front.

6. Why is LinkedList rarely the right choice?

Its O(1) insertion only applies once you already hold the node, and finding that node is O(n). Every node is a separate heap allocation, so traversal jumps around memory and defeats CPU caching, which usually makes it slower than an array-backed list even where the Big-O looks better.

7. What is wrong with calling Contains on a list inside a loop?

List<T>.Contains scans linearly, so a loop over n items each doing an O(m) scan is O(n·m). Converting the searched collection to a HashSet<T> once makes each check O(1) and the whole operation linear. It is a one-line change with an order-of-magnitude effect on large data.

8. Is Dictionary enumeration order guaranteed?

No. The documented behaviour is that order is unspecified and may change, particularly after a resize or removals. If you need ordering, sort explicitly with OrderBy when consuming, or use SortedDictionary<K,V>, which maintains key order at O(log n) per operation.

9. What is the difference between IReadOnlyList and ImmutableList?

IReadOnlyList<T> is a read-only view: the caller cannot modify it through that reference, but the underlying collection can still be changed by its owner. ImmutableList<T> genuinely cannot change; operations return a new instance that shares internal structure with the original.

10. Why can’t you use a Dictionary from multiple threads?

Reads and writes are not synchronised, and a concurrent write during an internal resize can leave the bucket structure inconsistent, historically producing corrupted state or a read that never terminates. Use ConcurrentDictionary<K,V>, whose GetOrAdd and AddOrUpdate are atomic, or guard a plain dictionary with a lock.