C# Reference ยท Collections
Collection complexity (Big-O)
A Big-O cheat sheet for .NET collections: List, Dictionary, HashSet, SortedSet, Queue, Stack, LinkedList and PriorityQueue, with a counting demo you can run.
Every .NET collection makes trade-offs between lookup, insertion, removal and memory. Big-O notation describes how the cost grows as the number of items n grows: O(1) stays flat, O(log n) grows slowly, O(n) grows in step with the size and O(nยฒ) explodes. Picking the right collection is usually worth more than tuning a loop.
The numbers below are the documented or well-known complexities for the standard implementations. Constant factors differ a lot: a List<T> scan of 20 items often beats a Dictionary lookup because the data sits in one block of memory.
The table
| Collection | Index / get by key | Search by value | Add | Insert / remove in the middle | Notes |
|---|---|---|---|---|---|
T[] |
O(1) | O(n) | fixed size | n/a | Fastest iteration, no growth |
List<T> |
O(1) | O(n) | O(1) amortized | O(n) | Add at the end is cheap; Insert(0, x) shifts everything |
LinkedList<T> |
O(n) | O(n) | O(1) at either end or at a node you hold | O(1) at a node you hold | Poor cache behavior, extra node allocation |
Dictionary<K,V> |
O(1) average | O(n) | O(1) amortized | O(1) average | Worst case O(n) with bad hash codes |
HashSet<T> |
O(1) average (Contains) |
O(1) average | O(1) amortized | O(1) average | No order |
SortedDictionary<K,V> |
O(log n) | O(n) | O(log n) | O(log n) | Red-black tree, ordered keys |
SortedSet<T> |
O(log n) | O(log n) | O(log n) | O(log n) | Ordered; Min/Max are O(log n) |
SortedList<K,V> |
O(log n) | O(n) | O(n) | O(n) | Two arrays, cheapest memory of the sorted types |
Queue<T> |
Peek O(1) |
O(n) | Enqueue O(1) amortized |
Dequeue O(1) |
Circular buffer |
Stack<T> |
Peek O(1) |
O(n) | Push O(1) amortized |
Pop O(1) |
Array-based |
PriorityQueue<E,P> |
Peek O(1) |
O(n) | Enqueue O(log n) |
Dequeue O(log n) |
4-ary heap; no fast removal of arbitrary items |
ImmutableList<T> |
O(log n) | O(n) | O(log n) | O(log n) | Balanced tree |
ImmutableArray<T> |
O(1) | O(n) | O(n) (copies) | O(n) | Thin wrapper over an array |
"Amortized" means that an occasional resize costs O(n), but spread over many adds the average is constant.
Try it
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.
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.
Usage notes
- Use a
HashSet<T>orDictionary<K,V>when you callContainsor look up by key repeatedly;List<T>.Containsin a loop is the classic accidental O(nยฒ). - Dictionary and hash set speed assume a good
GetHashCode. A constant hash code makes every lookup a linear scan. List<T>.Remove(x)is O(n) twice (find, then shift). Removing from the end withRemoveAt(Count - 1)is O(1).- LINQ operations add their own cost:
Count()on anIEnumerable<T>that is not a collection walks the whole sequence, andElementAton aLinkedList<T>is O(n). Enumerable.OrderByis O(n log n);Distinct,GroupByandToHashSetare O(n) on average using hashing.- Constant factors and memory locality matter: arrays and lists of structs are the fastest to scan, and tree-based collections allocate a node per item.
- Measure with a benchmark before replacing a simple
List<T>for performance reasons; smallnrarely cares.
Related
- List
- Dictionary<TKey,TValue>
- HashSet
- Capacity and resizing
- Choosing collections in the tutorial