Collections

What it is and why it exists

A collection stores values of a common type in one object that can be enumerated. It does more than hold elements: it defines how you locate them, whether duplicates are allowed, whether order is maintained, and what mutation means. Choosing a collection means choosing those behaviors, not just another container spelling.

The usual default is List<T>. It fits indexed access, sequential iteration, and appending at the end. Use Dictionary<TKey, TValue> when you locate a value by a domain key. Use HashSet<T> when you care only whether a value occurs or need operations such as union and intersection.

Access order can itself be part of the contract. Queue<T> processes work first in, first out; Stack<T> keeps undo records last in, first out; and PriorityQueue<TElement, TPriority> removes the element whose priority is smallest according to its comparer. Use SortedDictionary<TKey, TValue> or SortedSet<T> when keys or values must remain sorted.

Generic collections constrain element types at compile time. Unlike the older ArrayList and Hashtable, they don’t force callers to cast values through object, and storing value types usually doesn’t box every element. New code normally chooses from System.Collections.Generic, System.Collections.Concurrent, or System.Collections.Immutable.

Collections appear at model boundaries, in caches, batch jobs, schedulers, and API return values. The concrete type is only part of the decision there. Equality, mutability, ownership, and concurrency together determine whether the code is correct.

How it works

Interfaces describe the capability a caller needs

IEnumerable<T> promises only that elements can be obtained in sequence. It doesn’t promise indexed access, repeatable enumeration, resident in-memory data, or even the same results on two passes. A function accepting this interface shouldn’t quietly assume that its argument is a list.

ICollection<T> adds Count and common mutation operations. IList<T> adds indexed access, ISet<T> expresses unique elements and set operations, and IDictionary<TKey, TValue> expresses a key-value mapping. Read-only interfaces remove mutation members from the caller’s view, but they don’t automatically freeze the backing object.

Use the narrowest parameter interface that supports the algorithm. Accept IEnumerable<T> when you only enumerate, and require IReadOnlyList<T> only when you need a stable count and indexing. A return type must also express ownership: a live read-only view, an independent snapshot, and an immutable value are different contracts.

Concrete types determine access cost

List<T> uses contiguous storage to provide O(1) indexing. When spare capacity remains, Add writes one new position. When capacity is exhausted, the list must allocate larger storage and copy elements. Individual appends therefore vary in cost, but a sequence has amortized O(1) cost .

Dictionary<TKey, TValue> and HashSet<T> are based on a hash table . They first use a hash code to narrow the candidates and then confirm a match with equality. Lookup is usually close to O(1), but that depends on comparer quality, load, and input. It isn’t a worst-case guarantee for every call.

Sorted collections maintain order through a comparer, with typical O(log n) lookup and update. They solve “the stored data stays sorted,” while LINQ OrderBy solves “produce a sorted sequence for this result.” If you sort only before output, don’t change the primary storage structure just to gain ordering.

Three kinds of order aren’t interchangeable

“Preserve insertion order,” “remain sorted by value,” and “remove only the next highest-priority element” are different requirements. Calling all of them “ordered” produces plausible implementations that expose the wrong operations.

PriorityQueue guarantees only that Dequeue or TryDequeue removes the element whose priority is smallest according to the comparer. Equal-priority elements aren’t guaranteed to be first in, first out. Include a monotonically increasing sequence number in a compound priority when stability is part of the contract.

When the same data needs several access paths, keep one authoritative store and build indexes around it. For example, a list can preserve display order while a dictionary locates objects by ID. Update logic must maintain both structures, or derived indexes must be rebuilt from authoritative data at a boundary.

Equality is part of the collection contract

Dictionaries and hash sets use IEqualityComparer<T>. If you don’t supply one, they use EqualityComparer<T>.Default, which follows the type’s equality implementation. When domain rules differ—for example, when SKUs are case-insensitive—pass an explicit equality comparer to the collection constructor.

The comparer must implement one coherent relation: two equal values must produce the same hash code. Data involved in hashing and equality must also remain stable while an element is in the collection. Otherwise, the object can remain in one bucket while its changed key can no longer locate it.

Records commonly generate structural equality from their contents. That doesn’t prove every field belongs in a domain identity. A collection key should still be a small, stable identifier, or the collection should receive a comparer that considers only that identifier.

Examples

All four examples use one inventory domain, but each collection serves a different access pattern. When output needs stable order, the code sorts explicitly instead of relying on hash enumeration details.

Keep order in a list and build a dictionary index

Products enter a List<Product> because entry order matters. A dictionary provides a second access path by SKU and fixes the case rule at construction.

TryAdd treats “the key already exists” as an ordinary result, while Add throws ArgumentException for a duplicate key. TryGetValue performs one lookup and makes the missing branch visible in control flow. The bySku[key] indexer is better when the caller has already established an invariant that the key exists.

StringComparer.OrdinalIgnoreCase supplies both hashing and equality, so "BK-1" and "bk-1" are the same key. Ordinal rules are appropriate for protocol identifiers because they don’t depend on the current culture.

Express uniqueness and set operations with a hash set

Warehouse permissions have no business order, and each permission should occur once. Both sets share a comparer, and the intersection keeps the comparer from the copied left-hand set.

using System;
using System.Collections.Generic;
using System.Linq;

var granted = new HashSet<string>(StringComparer.OrdinalIgnoreCase)
{
    "catalog.read",
    "stock.write",
    "audit.read"
};

bool firstAdd = granted.Add("CATALOG.READ");
var required = new HashSet<string>(StringComparer.OrdinalIgnoreCase)
{
    "catalog.read",
    "orders.write"
};

var available = new HashSet<string>(granted, granted.Comparer);
available.IntersectWith(required);

Console.WriteLine($"new permission added: {firstAdd}");
Console.WriteLine($"available: {string.Join(", ", available.Order())}");
Console.WriteLine($"all required: {required.IsSubsetOf(granted)}");

new permission added: False
available: catalog.read
all required: False

The Boolean result from Add combines the membership test and insertion, so no preceding Contains call is needed. IntersectWith mutates its receiver, which is why the example copies granted first. If the original belongs to the caller, permission for in-place mutation must be part of the method contract.

The call to Order() exists only to produce deterministic text. The algorithm doesn’t depend on HashSet<T> enumeration order. If order is a domain requirement, store it separately or choose an ordered structure.

Schedule with a queue and undo with a stack

Pending restock requests need first-in-first-out processing, while the most recently processed record must be the first one undone. A queue and stack state those rules directly, without index conventions at each call site.

using System;
using System.Collections.Generic;

var pending = new Queue<RestockRequest>();
var completed = new Stack<RestockRequest>();

pending.Enqueue(new("BK-1", 5));
pending.Enqueue(new("PN-2", 12));
pending.Enqueue(new("NB-3", 4));

while (completed.Count < 2 && pending.TryDequeue(out RestockRequest? request))
{
    completed.Push(request);
    Console.WriteLine($"restocked {request.Sku}: {request.Quantity}");
}

if (completed.TryPop(out RestockRequest? undone))
{
    Console.WriteLine($"undo {undone.Sku}");
}

Console.WriteLine($"next: {pending.Peek().Sku}");

public sealed record RestockRequest(string Sku, int Quantity);

restocked BK-1: 5
restocked PN-2: 12
undo PN-2
next: NB-3

TryDequeue and TryPop make an empty collection an ordinary branch. The final line uses Peek because the preceding flow guarantees that one element remains. If that invariant isn’t clear, use TryPeek there too.

The two collections preserve work order; they don’t provide transactional compensation. A real undo operation must also record enough information to reverse external state and handle failure of the undo itself.

Distinguish a read-only view from an immutable snapshot

AsReadOnly() wraps an existing list. A caller can’t mutate the list through that wrapper, but it sees later changes made by the owner. ToImmutableArray() creates an immutable snapshot at the time of the call.

using System;
using System.Collections.Generic;
using System.Collections.Immutable;

var names = new List<string> { "Book" };
IReadOnlyList<string> liveView = names.AsReadOnly();
ImmutableArray<string> snapshot = names.ToImmutableArray();

names.Add("Pen");

Console.WriteLine($"view: {string.Join(", ", liveView)}");
Console.WriteLine($"snapshot: {string.Join(", ", snapshot)}");

ImmutableArray<string> revised = snapshot.Add("Notebook");
Console.WriteLine($"original snapshot count: {snapshot.Length}");
Console.WriteLine($"revised count: {revised.Length}");

view: Book, Pen
snapshot: Book
original snapshot count: 1
revised count: 2

liveView is a read-only collection , not a snapshot. snapshot.Add doesn’t modify the original value either; it returns a new immutable array. If the caller ignores the return value, that logical update is lost.

Neither choice promises deep immutability. If an element is mutable, a view and snapshot can still point to that same element. Element types also need a suitable immutable contract when published state must remain stable.

Pitfalls

Looking up a dictionary twice

Fix: use TryGetValue for reads, TryAdd for insertion, and the single operation whose semantics match an update. This doesn’t make an ordinary Dictionary thread-safe. Reconsider the synchronization boundary when writes can be concurrent.

Mutating a hashed key

Fix: use immutable scalars, value objects, or records as keys, and include only stable identity in equality. If you must index a mutable object by one field, build a dictionary keyed by an immutable identifier. An identity change requires explicit removal and reinsertion.

Mutating an ordinary collection during enumeration

Fix: use RemoveAll for list filtering, or collect keys to remove before applying changes. When iteration really consumes elements, choose Queue<T>, Stack<T>, or a concurrent structure with explicit consuming semantics instead of depending on ordinary enumerator details.

Mistaking a read-only interface for an immutable value

Fix: state whether an API returns a live view, independent copy, or immutable value. Copy to an array or immutable collection for a stable snapshot. For a live view, document who can mutate it, when changes become visible, and how access is synchronized.

Depending on unspecified enumeration order

Fix: use an explicit OrderBy when order belongs to the output contract, and a sorted collection or separate order structure when it belongs to storage. Tests of set content should assert set semantics instead of accidentally comparing hash-enumeration text.

Mistaking thread-safe calls for an atomic workflow

Fix: make value factories repeatable and free of irreversible side effects. When a rule means “charge exactly once” or spans several keys, use a lock, transaction, or dedicated coordinator that matches the business boundary, then verify it with contention tests.

Further reading

• C# collections reference
• .NET collections and data structures
• Dictionary<TKey, TValue> API
• HashSet<T> API
• .NET thread-safe collections
• System.Collections.Immutable namespace