Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 182 ยท Collections

Choosing the Right Collection

Pick the right C# collection for the job - List, Dictionary, HashSet, Queue, Stack, SortedSet, Frozen and Concurrent collections - with a decision table, Big O costs and runnable demos.

You now know a whole toolbox of collections: arrays, lists, dictionaries, sets, queues and stacks, sorted collections and immutable ones. The hard part in real programs is not using each one, it is picking the right one at the moment you type new. A wrong choice rarely breaks your program. It makes it slow in a way that only shows up when the data grows, and that is the worst kind of bug to find.

This lesson gives you a simple method: describe the operations you do most, then look up which collection makes those operations cheap. We will also read Big O notation without fear, see why memory layout matters as much as the algorithm, and preview the thread-safe collections that come later in the course.

Start with the question, not the type

Do not ask "should I use a List or a Dictionary?" Ask these questions about your data, in this order:

  1. Do I look things up by a key? (find the customer with id 42, the word "apple") If yes, you want a Dictionary.
  2. Do I only need to know whether something is present? (has this user already voted?) You want a HashSet.
  3. Does the order of arrival matter? First in, first out is a Queue. Last in, first out is a Stack.
  4. Do I need the smallest or largest item, again and again? That is a PriorityQueue.
  5. Do I need the items kept sorted at all times? SortedSet, SortedDictionary or SortedList.
  6. Do I just need a sequence I append to and loop over? List<T>. This is the answer far more often than beginners expect.
  7. Is the data fixed once it is built? Think about an array, ImmutableArray<T> or a FrozenDictionary.
  8. Will several threads touch it at the same time? Use a concurrent collection, or protect a normal one with a lock.

Here is the same table in one place. n is the number of items.

Need Collection Typical cost
Append and loop List<T> add at end O(1) amortized, loop O(n)
Fixed size, fastest access T[] index O(1)
Find by key Dictionary<K,V> lookup, add, remove O(1) average
Is it there? / no duplicates HashSet<T> contains, add, remove O(1) average
First in, first out Queue<T> enqueue, dequeue O(1)
Last in, first out Stack<T> push, pop O(1)
Always the smallest next PriorityQueue<T,P> enqueue, dequeue O(log n), peek O(1)
Sorted at all times SortedSet<T>, SortedDictionary<K,V> O(log n)
Sorted, built once, read often SortedList<K,V> lookup O(log n), insert O(n)
Insert/remove at a known node LinkedList<T> O(1), but rarely the best choice
Read-only, many lookups FrozenDictionary, FrozenSet fastest lookups, slow to build

When in doubt, start with List<T> and Dictionary<K,V>. They are the best general-purpose choices, they are heavily optimized in the runtime, and you can always change the type later because you will hide it behind an interface such as IReadOnlyList<T> (see IEnumerable, ICollection and IList).

Big O in plain words

Big O notation answers one question: if I make the data 10 times bigger, how much slower does this operation get?

  • O(1), constant: no slower. Reading array[5000] takes the same time as array[5].
  • O(log n), logarithmic: barely slower. Doubling the data adds one extra step. A sorted tree with a million items needs about 20 steps.
  • O(n), linear: 10 times the data, 10 times the work. Looking through a List for a value.
  • O(n log n): sorting.
  • O(n squared): 10 times the data, 100 times the work. Usually a loop inside a loop, and the thing to avoid.

Words like "average" and "amortized" matter. A dictionary lookup is O(1) on average because a good hash spreads keys evenly, but a terrible GetHashCode can degrade it. Adding to a List is O(1) amortized: usually it just writes into a free slot, occasionally it copies the whole array into a bigger one, and averaged over many adds the cost per add is constant.

Seeing the difference without a stopwatch

Timings are noisy, so let us count work instead. List.Exists calls our test once per item it looks at, so we can count how many items it inspected. A HashSet jumps straight to the right bucket.

C# Counting the work of a lookup

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

One lookup is cheap either way. A thousand lookups in a list turn into about ten million comparisons, and a hundred thousand lookups into a thousand times more. This is the classic accident: a method that is "fine" on 100 test rows and unusable on 100,000 production rows. If you call Contains in a loop on a List, you almost certainly want a HashSet.

Memory matters too

Big O hides constants, and constants are decided largely by memory.

  • An array or List<T> stores items next to each other. The CPU loads memory in chunks called cache lines, so walking such a sequence is very fast. A List<int> of a million numbers is about 4 MB of tightly packed data.
  • A LinkedList<T> allocates one object per item, each with two extra references. Walking it jumps around memory. Even operations that are O(1) on paper are often slower in practice than the O(n) shifting of a List, which is why LinkedList is rarely the right answer.
  • A Dictionary stores an array of buckets and an array of entries. It uses noticeably more memory than a list of the same items, which is the price for fast lookup.
  • SortedDictionary allocates a tree node per entry, so it uses the most memory.
  • Value types such as int or a small struct are stored inline, but a List<object> or List<string> stores references to separate objects.

You can reduce growth costs by telling a list how many items you expect. A List<T> doubles its capacity when full, copying everything each time. new List<T>(capacity) or list.EnsureCapacity(n) avoids those copies. The same constructor argument exists on Dictionary, HashSet, Queue and Stack.

C# Watching a list grow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Each growth step allocates a new array twice the size and copies the old items across. Starting with a sensible capacity, as in the pre-sized list, removes all of that work when you know the size.

Matching the collection to a real task

Let us solve five small tasks and notice that each one has an obvious collection once you name the operation.

C# Five tasks, five collections

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Notice what is not in this program: nobody loops through a List to find a price, and nobody sorts a list over and over to find the most urgent ticket. Naming the operation chooses the type.

Sorted, but how often?

"I need my data sorted" has two quite different meanings.

Sorted once, at the end (print a report): put items in a List<T> and call Sort() or LINQ's OrderBy once. That is O(n log n) one time and no special collection.

Sorted all the time (a live leaderboard where scores keep arriving and you read the top 3 after each one): use SortedSet<T> or a PriorityQueue, which keep order cheaply as items arrive.

C# Sort at the end or keep sorted

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

If you only read the sorted result once, style B does extra work for nothing. If you read it after every insert, style A would re-sort on every read and be much slower. Match the structure to the read pattern.

Read-only data: freeze it

Lookup tables such as country codes or configuration are built once and read millions of times. For those, FrozenDictionary and FrozenSet (in System.Collections.Frozen, .NET 8+) spend extra time at construction to pick the fastest internal layout for exactly your keys. You cannot add or remove afterwards, and that restriction is the point.

C# A frozen lookup table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Building a frozen collection is slower than building a normal one, so use it only for data that lives for a long time (application start-up, then reads forever).

A preview of thread-safe collections

The collections above are not thread-safe for concurrent writes. If two threads call Add on the same List<T> at once, items can be lost or the list can become corrupt. The System.Collections.Concurrent namespace has replacements: ConcurrentDictionary, ConcurrentQueue, ConcurrentStack and ConcurrentBag. We cover them properly in the async and concurrency chapter; here is a taste.

C# ConcurrentDictionary counting in parallel

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The order in which iterations run is not guaranteed, but the totals are always exact, because AddOrUpdate is atomic. Concurrent collections cost more per operation than plain ones, so never use them "just in case". Use them only when threads really share the collection.

Common mistakes

  • List.Contains in a loop. Turn the list into a HashSet first.
  • list.Remove(0) style queues. Removing from the front of a List shifts every item (O(n)). Use a Queue.
  • Sorting inside a loop. Sort once outside, or use a sorted collection.
  • Mutable keys. Changing an object after using it as a dictionary key breaks lookups. Use immutable keys such as strings, ints, records or enums.
  • Exposing the internal List. Return IReadOnlyList<T> so callers cannot change your data behind your back.
  • Guessing instead of measuring. For big data, count operations as we did here, or use a profiler. A simple List often beats a clever structure for fewer than a few hundred items.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. You must check whether each of 100,000 incoming ids was already seen. Which collection is the best fit?

    HashSet.Contains is O(1) on average, so 100,000 checks are cheap. List.Contains scans the whole list each time, giving about n squared work overall.
  2. 2. A background worker must process jobs in the order they arrived. Which collection fits?

    A queue is first in, first out. A stack would process the newest job first.
  3. 3. What does O(log n) mean for a sorted tree with a million items?

    Logarithmic growth means doubling the data adds only one step. The base-2 logarithm of a million is about 20.
  4. 4. Why use FrozenDictionary instead of Dictionary for a lookup table built at start-up?

    Frozen collections analyze the keys once to choose a faster layout. They cannot be modified afterwards.
  5. 5. Which statement about ConcurrentDictionary is true?

    Concurrent collections make individual operations atomic, which adds overhead. Use them only when threads genuinely share the data.

Summary

  • Choose a collection by the operations you perform most, not by habit.
  • List<T> for sequences, Dictionary for lookup by key, HashSet for membership and uniqueness, Queue/Stack for ordering rules, PriorityQueue for "most urgent next", sorted collections for always-sorted data.
  • Big O tells you how cost grows with data. Watch out for O(n) operations inside loops.
  • Contiguous memory (arrays, lists) is faster in practice than the diagram suggests; pre-size collections when you know the size.
  • Freeze read-only lookup tables; hide collections behind read-only interfaces.
  • Plain collections are not thread-safe. Concurrent collections are for shared data only.

Next: Classes and Objects