C# collections guide — List, Array, Dictionary, HashSet, Queue, Stack
Choosing the right collection is one of the most impactful decisions for correctness and performance. This guide covers every core collection type, when to use each one, and their time complexity characteristics.
Quick Selection Guide
| If you need… | Use |
|---|---|
| Ordered items, frequent add/remove at end | List<T> |
| Fixed-size, maximum performance reads | T[] (array) |
| Key → value lookups | Dictionary<TKey, TValue> |
| Unique items, fast contains/add/remove | HashSet<T> |
| First-in-first-out processing | Queue<T> |
| Last-in-first-out / undo history | Stack<T> |
| Frequent insert/delete in the middle | LinkedList<T> |
| Sorted key → value | SortedDictionary<TKey, TValue> |
| Sorted unique items | SortedSet<T> |
| Thread-safe concurrent access | ConcurrentDictionary / ConcurrentQueue |
List<T>
The everyday workhorse. Backed by a resizable array — random access is O(1), adding to the end is amortized O(1).
var list = new List<int> { 3, 1, 4, 1, 5 };
list.Add(9); // append
list.Insert(0, 0); // insert at index — O(n), shifts elements right
list.Remove(1); // removes first occurrence of value 1
list.RemoveAt(2); // removes element at index 2
Console.WriteLine(list.Count); // current count
Console.WriteLine(list[0]); // random access — O(1)
Console.WriteLine(list.Contains(5)); // O(n) linear scanBest for: General-purpose ordered collections where you mostly add to the end and access by index.
Array (T[])
Fixed size — length set at creation, can't grow. Fastest for reads and iteration because of cache locality.
int[] nums = new int[5]; // all zeros
int[] data = { 10, 20, 30 }; // initializer
Console.WriteLine(data[1]); // 20 — O(1)
Console.WriteLine(data.Length);
Array.Sort(data); // in-place sort
Array.Reverse(data);
int idx = Array.BinarySearch(data, 20); // O(log n) — array must be sortedBest for: Fixed-size buffers, high-frequency read loops, interop with C APIs.
Dictionary<TKey, TValue>
Hash-based key → value store. Average O(1) for add, lookup, and remove. Keys must be unique.
var scores = new Dictionary<string, int>
{
["Alice"] = 95,
["Bob"] = 87
};
scores["Charlie"] = 91; // add or update
if (scores.TryGetValue("Bob", out int s)) // safe lookup — no exception on miss
Console.WriteLine($"Bob: {s}"); // Bob: 87
scores.ContainsKey("Dave"); // false
scores.Remove("Bob");
foreach (var (name, score) in scores)
Console.WriteLine($"{name}: {score}");Best for: Lookup tables, caches, counting frequencies, grouping by key.
HashSet<T>
Stores unique elements. Backed by a hash table — O(1) average for add, remove, and contains. Order is not guaranteed.
var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5, 6 };
a.Add(2); // no-op — already exists
a.Add(5);
// Set operations
a.UnionWith(b); // a ∪ b
a.IntersectWith(b); // a ∩ b
a.ExceptWith(b); // a − b
bool has3 = a.Contains(3); // O(1)Best for: Deduplication, membership testing ("have I seen this before?"), set algebra.
Queue<T>
First-in, first-out. Enqueue adds to the back; Dequeue removes from the front. Both are O(1).
var queue = new Queue<string>();
queue.Enqueue("task-1");
queue.Enqueue("task-2");
queue.Enqueue("task-3");
Console.WriteLine(queue.Peek()); // "task-1" — look without removing
Console.WriteLine(queue.Dequeue()); // "task-1" — removed
Console.WriteLine(queue.Count); // 2
// Safe dequeue
if (queue.TryDequeue(out string? next))
Console.WriteLine(next); // "task-2"Best for: Task queues, breadth-first search, message processing pipelines.
Stack<T>
Last-in, first-out. Push adds to the top; Pop removes from the top. Both are O(1).
var stack = new Stack<string>();
stack.Push("page-1");
stack.Push("page-2");
stack.Push("page-3");
Console.WriteLine(stack.Peek()); // "page-3" — look without removing
Console.WriteLine(stack.Pop()); // "page-3" — removed
Console.WriteLine(stack.Count); // 2Best for: Undo/redo history, depth-first search, expression parsing, call stack emulation.
LinkedList<T>
Doubly-linked list. O(1) insert/delete anywhere given a node reference, but O(n) random access. Higher memory overhead per element.
var list = new LinkedList<int>(new[] { 1, 2, 3 });
LinkedListNode<int>? node2 = list.Find(2);
if (node2 != null)
{
list.AddBefore(node2, 10); // O(1) — insert before node
list.AddAfter(node2, 20); // O(1) — insert after node
list.Remove(node2); // O(1) — remove node
}
Console.WriteLine(string.Join(", ", list)); // 1, 10, 20, 3Best for: Frequent middle insertions/deletions with a node reference in hand. Rarely the best choice in practice — List<T> wins for most use cases.
Time Complexity Summary
| Operation | List<T> | T[] | Dictionary | HashSet | Queue | Stack |
|---|---|---|---|---|---|---|
| Add (end) | O(1) amort. | — | O(1) avg | O(1) avg | O(1) | O(1) |
| Insert (middle) | O(n) | — | — | — | — | — |
| Remove (by value) | O(n) | — | O(1) avg | O(1) avg | — | — |
| Access by index | O(1) | O(1) | — | — | — | — |
| Lookup / Contains | O(n) | O(n) | O(1) avg | O(1) avg | — | — |
| Iteration | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) |
Choosing by Scenario
// Deduplicate a list of IDs
var ids = new List<int> { 1, 2, 2, 3, 1, 4 };
var unique = new HashSet<int>(ids);
Console.WriteLine(string.Join(", ", unique)); // 1, 2, 3, 4
// Count word frequencies
var words = "the cat sat on the mat".Split(' ');
var freq = new Dictionary<string, int>();
foreach (var w in words)
freq[w] = freq.GetValueOrDefault(w) + 1;
// freq["the"] = 2
// Process in arrival order
var taskQueue = new Queue<string>();
taskQueue.Enqueue("email");
taskQueue.Enqueue("report");
string next = taskQueue.Dequeue(); // "email"
// Undo stack
var history = new Stack<string>();
history.Push("state-1");
history.Push("state-2");
string previous = history.Pop(); // "state-2" (undo)