C# § data-structures

Data structures

C#‘s standard collections live in three namespaces: System.Collections.Generic for the conventional thread-unsafe collections; System.Collections.Concurrent for thread-safe variants designed for concurrent producers and consumers; System.Collections.Immutable for persistent collections that admit safe sharing across threads through structural sharing rather than locks. The conventional default for new code is the generic, type-safe collections in the first namespace; the others are reached for when the use case demands. Beyond the collections, the language provides arrays, Span<T> for non-allocating views, and the older non-generic System.Collections namespace (which modern code rarely uses).

This page covers the principal collection types, the choice among them, the iterator and enumeration model, and the conventions for using each. The query side — Where, Select, OrderBy, and the rest of the LINQ surface — is treated separately in LINQ.

The collections design

The .NET collections were designed in three layers:

The non-generic System.Collections (1.0) — ArrayList, Hashtable, Queue, Stack. These store object and box value types; modern code uses them rarely (mostly when interoperating with very old APIs).
The generic System.Collections.Generic (2.0) — List<T>, Dictionary<TKey, TValue>, HashSet<T>, etc. These are type-safe, avoid boxing for value types, and are the conventional default.
The concurrent and immutable namespaces — added subsequently for thread-safety and persistence.

The generic collections share a common interface model:

Interface	Purpose
`IEnumerable<T>`	Forward-only iteration
`ICollection<T>`	Counting, adding, removing, contains
`IList<T>`	Indexed access
`IReadOnlyCollection<T>`, `IReadOnlyList<T>`	Read-only views
`IDictionary<TKey, TValue>`	Key-value lookup
`ISet<T>`	Set operations

A type may implement several; List<T> implements IList<T>, ICollection<T>, IEnumerable<T>, plus the read-only variants. Code that takes an interface parameter accepts any concrete type satisfying it.

Sequence containers

`List<T>`

The conventional dynamic-array container. The principal operations:

var values = new List<int>();
values.Add(1);
values.Add(2);
values.AddRange(new[] { 3, 4, 5 });

values.Insert(0, 99);             // O(n)
values.RemoveAt(0);                // O(n)
values.Remove(2);                  // O(n) — by value

int first = values[0];             // O(1)
int count = values.Count;
bool has  = values.Contains(3);    // O(n)

List<T> is implemented as a backing array with a separate length; growth (typically doubling) reallocates the array. The capacity may be reserved or read explicitly:

var v = new List<int>(capacity: 1000);
v.Capacity = v.Count;              // shrink to fit

The principal performance characteristics:

Operation	Complexity
`Add(item)` (at end)	Amortised O(1)
`Insert(0, item)`	O(n)
`Remove(item)`	O(n)
`RemoveAt(i)`	O(n)
`this[i]`	O(1)
`IndexOf(item)` / `Contains(item)`	O(n)
`Sort()`	O(n log n)

List<T> is the default sequence container; the burden is on alternatives (LinkedList, Queue, Stack) to justify their use.

`T[]` (arrays)

Arrays are a fundamental type in the CLR; T[] is a reference type with fixed size:

int[]    a = new int[5];
int[]    b = { 1, 2, 3, 4, 5 };
int[]    c = new[] { 1, 2, 3 };          // type inferred
double[,] m = new double[3, 4];           // multi-dimensional
int[][]  jagged = new int[3][];           // jagged: array of arrays
jagged[0] = new int[] { 1, 2, 3 };

Arrays differ from List<T>:

Fixed length — set at construction.
Stored inline in the array allocation — value types are not boxed.
Multi-dimensional — int[3, 4] is genuinely two-dimensional (contrast with List<List<int>>, which is a list of lists).
Implements IList<T> — admits all the same interface-based operations.

The conventional choice: arrays for fixed-size data; List<T> for variable-size.

`LinkedList<T>`

A doubly-linked list:

var ll = new LinkedList<int>();
ll.AddLast(1);
ll.AddLast(2);
ll.AddFirst(0);

LinkedListNode<int>? node = ll.First;
ll.AddAfter(node!, 99);
ll.Remove(node!);

Linked lists are rarely the right choice in modern C#: cache-unfriendliness, allocation per node, and the overhead of node references usually make List<T> faster for typical workloads, even when the asymptotic complexity favours the list. The list is appropriate only when constant-time insertion and removal at any position (given a node reference) is genuinely critical, or when iterator stability across modifications is required.

Associative containers

`Dictionary<TKey, TValue>`

The conventional hash table:

var ages = new Dictionary<string, int>();
ages["alice"] = 30;
ages.Add("bob", 28);
ages["alice"] = 31;                          // overwrite

bool has  = ages.ContainsKey("alice");
bool got  = ages.TryGetValue("carol", out int age);

int  count = ages.Count;
ages.Remove("bob");

The dictionary stores key-value pairs in a hash table; lookup, insertion, and removal are average O(1). The key’s GetHashCode() and Equals determine bucket placement.

For user-defined key types, override GetHashCode and Equals (records do this automatically) or supply an IEqualityComparer<TKey>:

var caseInsensitive = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
caseInsensitive["Alice"] = 30;
bool found = caseInsensitive.ContainsKey("ALICE");    // true

The TryGetValue pattern is the conventional safe lookup:

if (ages.TryGetValue(key, out var value)) {
    Use(value);
}

Dictionary iteration produces KeyValuePair<TKey, TValue> (or, with structured bindings, (key, value)):

foreach (var (key, value) in ages) {
    Console.WriteLine($"{key}: {value}");
}

C# 9 admitted dictionary[key] = value initialisation through the […] indexer in object initialisers:

var ages = new Dictionary<string, int> {
    ["alice"] = 30,
    ["bob"]   = 28,
};

`SortedDictionary<TKey, TValue>` and `SortedList<TKey, TValue>`

Two ordered key-value containers:

SortedDictionary<TKey, TValue> — backed by a red-black tree; O(log n) operations.
SortedList<TKey, TValue> — backed by parallel sorted arrays; O(log n) lookup, O(n) insertion in the middle.

Both maintain ordering by key; iteration produces entries in sorted-by-key order. The choice between them depends on workload: SortedDictionary is faster for insertion-heavy workloads; SortedList is more memory-efficient and faster for iteration.

var sd = new SortedDictionary<int, string>();
sd[3] = "three";
sd[1] = "one";
sd[2] = "two";

foreach (var (k, v) in sd) {
    Console.WriteLine($"{k}: {v}");
    // 1: one
    // 2: two
    // 3: three
}

`HashSet<T>`

A hash-based set:

var primes = new HashSet<int> { 2, 3, 5, 7, 11 };
primes.Add(13);
bool has5 = primes.Contains(5);

primes.UnionWith(new[] { 17, 19 });
primes.IntersectWith(new[] { 5, 7, 11, 13, 17 });
primes.ExceptWith(new[] { 11 });

The set stores unique elements; insertion of a duplicate is a no-op. Average O(1) for the principal operations.

HashSet<T> admits the conventional set operations: UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith, IsSubsetOf, IsSupersetOf, Overlaps. The mechanism is the conventional way to compute set differences, intersections, and unions.

`SortedSet<T>`

A tree-backed ordered set:

var sorted = new SortedSet<int> { 5, 2, 8, 3, 1 };
foreach (var n in sorted) Console.Write($"{n} ");
// 1 2 3 5 8

Like HashSet<T>, but iteration produces elements in order. O(log n) for the principal operations.

Adaptors

`Stack<T>` and `Queue<T>`

LIFO and FIFO containers:

var stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);

int top = stack.Pop();           // 3
int peek = stack.Peek();          // 2

var queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

int first = queue.Dequeue();      // 1
int peekFront = queue.Peek();     // 2

Both are O(1) for their principal operations. They are array-backed with growth on overflow.

`PriorityQueue<TElement, TPriority>`

Added in .NET 6: a min-heap-based priority queue:

var pq = new PriorityQueue<string, int>();
pq.Enqueue("low", 1);
pq.Enqueue("high", 10);
pq.Enqueue("mid", 5);

while (pq.TryDequeue(out var item, out var priority)) {
    Console.WriteLine($"{priority}: {item}");
    // 1: low
    // 5: mid
    // 10: high
}

The priority is a separate value (unlike languages where the priority is derived from the element). Enqueue/Dequeue are O(log n); Peek is O(1).

For a max-heap behaviour, use a comparer that inverts the order:

var maxHeap = new PriorityQueue<string, int>(Comparer<int>.Create((a, b) => b - a));

Concurrent collections

System.Collections.Concurrent provides thread-safe collections optimised for concurrent producers and consumers:

Type	Purpose
`ConcurrentDictionary<TKey, TValue>`	Thread-safe dictionary
`ConcurrentQueue<T>`	Thread-safe FIFO
`ConcurrentStack<T>`	Thread-safe LIFO
`ConcurrentBag<T>`	Thread-safe unordered collection
`BlockingCollection<T>`	Bounded, blocking producer-consumer queue

using System.Collections.Concurrent;

var counts = new ConcurrentDictionary<string, int>();

counts.AddOrUpdate(
    key: "request",
    addValue: 1,
    updateValueFactory: (_, current) => current + 1
);

if (counts.TryGetValue("request", out int n)) {
    Console.WriteLine($"requests: {n}");
}

The conventional uses are producer-consumer patterns and shared caches. The performance characteristics differ from the non-concurrent counterparts: the concurrent versions are faster than locking around a Dictionary<TKey, TValue> for the high-contention case, but slower for single-threaded use.

BlockingCollection<T> is a higher-level wrapper that supports bounded capacity and blocking on empty/full; the conventional pattern for producer-consumer queues with backpressure.

Immutable collections

System.Collections.Immutable provides persistent collections — every modification produces a new collection, and the old one remains valid:

using System.Collections.Immutable;

var list1 = ImmutableList<int>.Empty.Add(1).Add(2).Add(3);
var list2 = list1.Add(4);             // list1 is unchanged

var dict1 = ImmutableDictionary<string, int>.Empty.Add("a", 1);
var dict2 = dict1.SetItem("b", 2);    // dict1 is unchanged

The collections share structure where possible; an Add to an ImmutableList<T> of size n is O(log n) (not O(n)), and the new list shares most of its internal nodes with the old one. The result is that immutable collections are practical for use cases where copy-on-write semantics are desired without the cost of copying everything.

The principal types:

Type	Mutable counterpart
`ImmutableList<T>`	`List<T>`
`ImmutableArray<T>`	`T[]`
`ImmutableDictionary<TKey, TValue>`	`Dictionary<TKey, TValue>`
`ImmutableSortedDictionary<TKey, TValue>`	`SortedDictionary<TKey, TValue>`
`ImmutableHashSet<T>`	`HashSet<T>`
`ImmutableSortedSet<T>`	`SortedSet<T>`
`ImmutableStack<T>`	`Stack<T>`
`ImmutableQueue<T>`	`Queue<T>`

The conventional uses:

Configuration values that should not change after construction.
Snapshot-based read-only sharing across threads.
Functional-style code where each operation produces a new value.

The trade-off: immutable collections allocate on every modification. For workloads with many modifications, mutable collections are faster.

The Builder pattern admits efficient bulk modification:

var builder = ImmutableList.CreateBuilder<int>();
for (int i = 0; i < 1000; i++) builder.Add(i);
ImmutableList<int> result = builder.ToImmutable();

The builder is internally mutable; the final ToImmutable produces the persistent result without copying.

Views: `Span<T>` and `ReadOnlySpan<T>`

Span<T> is a stack-only view over contiguous memory — an array, a portion of an array, a string, or stack-allocated memory:

int[] arr = { 1, 2, 3, 4, 5 };
Span<int> all  = arr;
Span<int> mid  = arr.AsSpan(1, 3);          // {2, 3, 4} — no allocation

ReadOnlySpan<char> str = "hello".AsSpan();
ReadOnlySpan<char> first = str.Slice(0, 3); // "hel"

The treatment is in Memory and the CLR. The principal point: Span<T> is a non-owning, stack-only view, suitable for slicing and zero-copy processing.

Choice of container

The conventional decision tree:

Need	Collection
Default sequence	`List<T>`
Fixed-size sequence	`T[]` (array)
Frequent insertion at both ends	`Queue<T>` (one end) or hand-roll
Iterator stability across modifications	`LinkedList<T>`
Lookup by key	`Dictionary<TKey, TValue>`
Lookup by key, ordered iteration	`SortedDictionary<TKey, TValue>`
Set membership	`HashSet<T>`
Set membership, ordered iteration	`SortedSet<T>`
LIFO	`Stack<T>`
FIFO	`Queue<T>`
Min/max element	`PriorityQueue<TElement, TPriority>`
Thread-safe key-value	`ConcurrentDictionary<TKey, TValue>`
Producer-consumer	`BlockingCollection<T>`
Snapshot-shared	`ImmutableList<T>` (or another immutable variant)
Slice of contiguous memory	`Span<T>` / `ReadOnlySpan<T>`

The default for “I need a collection” is List<T>; the burden is on the alternative to justify itself.

Iterator invalidation

Modifications to a collection during iteration may invalidate the enumerator; foreach over a modified collection throws InvalidOperationException:

var list = new List<int> { 1, 2, 3, 4, 5 };

foreach (var x in list) {
    if (x == 3) list.Remove(x);    // throws on the next iteration
}

The conventional defences:

Build a separate list of items to add or remove, then apply after the loop.
Use RemoveAll(Predicate<T>) or RemoveAt/Remove with index-based iteration (which the iterator does not track).
Use LINQ’s Where(...).ToList() to produce a filtered copy.

list.RemoveAll(x => x == 3);
// or
var filtered = list.Where(x => x != 3).ToList();

The concurrent collections have different rules: ConcurrentDictionary<,> admits modification during iteration, but the iteration may or may not see the modifications.

Common patterns

Building up a list with a known size

var list = new List<int>(capacity: expectedSize);
for (int i = 0; i < expectedSize; i++) {
    list.Add(/* ... */);
}

Pre-sizing avoids repeated reallocations as the list grows.

Counting occurrences

var counts = new Dictionary<string, int>();
foreach (var word in words) {
    counts[word] = counts.GetValueOrDefault(word) + 1;
}

// or, using LINQ:
var counts2 = words.GroupBy(w => w).ToDictionary(g => g.Key, g => g.Count());

GetValueOrDefault (.NET Core 2.1+) is the conventional way to handle the absent-key case.

Conditional add

dict.TryAdd(key, value);                  // adds only if not present
dict[key] = value;                         // adds or overwrites

TryAdd (.NET Standard 2.1+) returns true if added, false if the key was already present.

Atomic update

dict.AddOrUpdate(
    key,
    addValueFactory: () => 1,
    updateValueFactory: (_, current) => current + 1
);

Available on ConcurrentDictionary<,>. For the non-concurrent Dictionary<,>, the conventional pattern is TryGetValue plus update.

Removal during iteration

list.RemoveAll(item => item.IsExpired);

RemoveAll is O(n) and avoids the iterator-invalidation problem.

Snapshot for thread-safe iteration

List<int> snapshot;
lock (syncRoot) {
    snapshot = sourceList.ToList();   // copy under the lock
}

foreach (var x in snapshot) {
    /* iterate without holding the lock */
}

The pattern admits iterating a thread-shared collection without holding the lock for the entire iteration; the cost is the per-iteration copy.

Composing with LINQ

var result = items
    .Where(IsValid)
    .Select(Transform)
    .ToList();

LINQ operates on IEnumerable<T>, which every collection implements. The ToList, ToArray, ToDictionary, and ToHashSet materialisation methods admit converting the query result back to a concrete collection. The full LINQ surface is in LINQ.