Choosing a collection

Costs

Data structure	Add	Remove	Access (by index or key)	Search (by value or key)
T[]	O(n) (if resize or shift)	O(n) (if shift)	O(1)	O(n)
List<T>	O(1) (amortized at end), O(n) (mid)	O(n) (mid)	O(1)	O(n)
LinkedList<T>	O(1) (ends), O(n) (mid by index)	O(1) (ends), O(n) (mid by index)	O(n)	O(n)
Dictionary<TKey, TValue>	O(1) (avg), O(n) (worst)	O(1) (avg), O(n) (worst)	O(1) (avg, by key)	O(1) (avg, by key)
HashSet<T>	O(1) (avg), O(n) (worst)	O(1) (avg), O(n) (worst)	N/A (use Contains)	O(1) (avg, Contains)
Stack<T>	O(1) (Push)	O(1) (Pop)	O(1) (Peek)	O(n)
Queue<T>	O(1) (Enqueue)	O(1) (Dequeue)	O(1) (Peek)	O(n)

Typical use

Data structure	Typical use case
T[]	Fixed-size collections, fast indexed access.
List<T>	Dynamic-size ordered collection, frequent additions or removals at the end, indexed access.
LinkedList<T>	Frequent insertions or deletions at the ends or at specific nodes (if the reference is known).
Dictionary<TKey, TValue>	Fast key-based lookups, additions and removals.
HashSet<T>	Storing unique items, fast existence checks, set operations.
Stack<T>	LIFO scenarios: call stacks, undo operations.
Queue<T>	FIFO scenarios: task scheduling, breadth-first search.

Choosing

The choice of data structure is a critical performance decision. Using a LinkedList<T> for frequent indexed access is far less performant than using a List<T>. Conversely, many insertions and deletions in the middle of a large List<T> can be slow.

Hash-based collections like Dictionary<TKey, TValue> offer average O(1) performance, but that relies on good hash functions. Poor implementations can degrade performance to O(n).

Similarly, LINQLINQ: query syntax and method syntaxOne SQL-like way to query many kinds of data, written in two equivalent forms.Opens in a new tab to Objects is convenient, but on performance-critical paths, manual iteration with an optimal data structure might be necessary.

Each structure has its own note: arrays, lists and linked listsArrays, lists and linked listsThree ways to keep items in order, and what each one costs.Opens in a new tab, Dictionary and HashSetDictionary and HashSetTwo hash-based collections: one maps keys to values, the other keeps unique items.Opens in a new tab, and Stack and QueueStack and QueueLast in, first out and first in, first out.Opens in a new tab.