Immutable collections live in the System.Collections.Immutable namespace and follow one rule: once you create one, it never changes. Every operation that looks like a mutation, Add, Remove, SetItem, returns a brand new collection and leaves the original alone. That property turns out to be useful for multi-threaded code, for snapshots, and for any place where you want to hand a collection out and be certain the receiver can't change it under you.

Standard collections like List<T>, Dictionary<TKey, TValue>, HashSet<T>, Queue<T>, and Stack<T> are mutable. You add, you remove, you index, and the same instance changes. If two threads hold the same List<T> and one calls Add, the other sees the new state.

Immutable collections turn that off. Once an ImmutableList<Product> exists, no method on it can change it. The Add method exists, but it returns a new ImmutableList<Product> containing the original items plus the new one. The original list is unchanged. Same for Remove, Clear, Insert, and SetItem.

The variable cart still has two items after the Add call. The Add produced a different ImmutableList<string> that updated now points to. If you didn't capture the return value, the addition would be lost. This is the important shift in thinking when you move from List<T> to ImmutableList<T>. The methods don't fail. They don't mutate. You have to keep the return.

That distinction is what makes the type safe for concurrent reads. A reader holding a reference to cart will see the same two items forever, regardless of what any other thread does, because nothing can change the object that reference points to. There's no lock, no copy-on-read, no defensive coding. The guarantee is structural.

"Immutable" doesn't mean "free." Producing the new collection has a cost that depends on the implementation. ImmutableList<T> shares most of its internal tree with the original (cheap-ish per Add), while ImmutableArray<T> copies the whole backing array (O(n) per Add). Pick the type based on how often you mutate vs how often you read.

The System.Collections.Immutable namespace gives you a static factory class for each immutable type (ImmutableList, ImmutableArray, and so on, without the <T>) and the generic collection type itself (ImmutableList<T>, ImmutableArray<T>). You almost never call a constructor directly. Instead use Create, CreateRange, or one of the ToImmutable* extension methods.

There are five recipes in that snippet, and you'll use all of them at different times.

ImmutableList<T>.Empty is the canonical empty list. It's a singleton inside the BCL, so every ImmutableList<string>.Empty returns the same instance. That makes "start from empty and build up" cheap. It's also the value you should use to express "no items yet" rather than allocating a fresh empty collection each time.

ImmutableList.Create(...) is the params-style factory. The compiler picks the appropriate overload based on the number of arguments. Internally it uses an efficient path for small inputs and falls back to a general builder for larger ones.

ImmutableList.CreateRange(IEnumerable<T>) is the bulk variant. When you already have a sequence, it materializes the immutable in one shot instead of N separate Add calls. That matters because every individual Add would build a new tree if you did them one at a time.

ToImmutableList() (and ToImmutableArray, ToImmutableDictionary, etc.) are extension methods on IEnumerable<T> for the same job: turn anything iterable into an immutable copy. They're discoverable through normal LINQ-style chaining.

The same pattern repeats for every type in the namespace:

Two details. First, ImmutableSortedSet.Create(5, 3, 4, 5, 2) deduplicates and sorts the input, like SortedSet<T>. Second, ImmutableStack.Create("page-home", "page-cart") reads in order, so page-cart is on top (the last one pushed). That last point is easy to get wrong, so when in doubt, push items one at a time.

When you call Add on a List<T>, the method returns void. The list itself changes. When you call Add on an ImmutableList<T>, the method returns ImmutableList<T>. The receiver is unchanged.

Because everything returns, the natural style is chaining or reassignment:

Each method takes an immutable list and returns a new one. You can read the chain top to bottom as "start empty, add Keyboard, then Mouse, then Monitor, drop Mouse, replace position 0." The final list has two items. Four intermediate lists existed at some point during the chain. Most of their internal structure is shared with neighbors, so the cost isn't four full copies (we'll get to why under "Structural Sharing").

There's a separate SetItem method because the indexer is read-only:

The compiler stops you from writing items[1] = "Z". The indexer has no setter. The only way to "change" position 1 is to ask for a new list with that position changed, which is what SetItem does. The error code (CS0200, "Property or indexer cannot be assigned to, it is read-only") shows up at compile time, not at runtime.

The same shape applies to dictionaries. ImmutableDictionary<TKey, TValue> exposes Add(key, value), SetItem(key, value), Remove(key), SetItems(...), and RemoveRange(...). SetItem adds a new key or overwrites an existing one (mimicking dict[k] = v). Add throws if the key already exists, just like Dictionary<TKey, TValue>.Add.

The print uses afterRestock.Count, not the value at a key, so the output is the number of keys (3). The example below makes the chain clearer:

Now the chain is clear. stock keeps its original mapping (MSE-1 -> 8), afterSale has the value lowered to 7, and afterRestock adds HDM-1. Three distinct dictionaries coexist. Any code holding a reference to stock sees the original two entries and would see them six months from now.

ImmutableList<T> is not implemented as a copy-on-write array. Internally it's an AVL tree (a self-balancing binary tree), with the list's items laid out in in-order traversal order. When you Add an item, the tree adds a node and rebalances along the path from root to leaf. Every node on that path is recreated as a new node, but every node off that path is reused from the original tree.

That "reuse" is what makes immutability practical. If a fresh Add had to copy every existing item into a new collection, immutable lists would be a non-starter for anything bigger than a few items. The tree's height is O(log n), so an Add only allocates O(log n) new nodes. Everything else is the same memory the original list pointed to. Both lists are simultaneously valid, both are immutable, and most of their storage is the same physical objects.

The diagram is a simplified view. The original list (orange root) holds items 1 through 7 in in-order traversal. After Add(8), the new root (green) shares the entire left subtree (item 2 and its children) with the original tree. Only the path from new root down to the new node item 8 is recreated: a new root, a new item 6 node, a new item 7 node, and the brand-new item 8 node at the leaf. Three of the original seven nodes are reused, and only four new nodes are allocated. For a list of one million items, an Add allocates around 20 new nodes (height roughly log2(1,000,000) ≈ 20), not a million.

The cost profile follows from the structure:

That O(log n) indexer is unusual for a "list". A regular List<T> indexer is O(1) because it's array-backed. ImmutableList<T> trades constant-time random access for cheap mutation-returning. When you need both fast random access and immutability, use ImmutableArray<T> instead.

Don't loop through an ImmutableList<T> by index unless the list is small or you're benchmarking out of curiosity. Use foreach, which uses the enumerator and is O(n) total. Per-index access is O(log n), so an indexed loop over a million-item list is closer to O(n log n) than O(n).

ImmutableArray<T> is the other shape of immutable collection, and it's the opposite trade-off from ImmutableList<T>. Internally it's a plain array wrapped in a struct. The "wrap" is the part that gives it value semantics: an ImmutableArray<T> is a value type (struct) holding one field, a reference to the underlying T[]. Assignment copies the struct (and therefore the array reference), but the array itself is treated as logically immutable.

Reads are O(1) because the indexer is the array's indexer. Mutations (Add, Remove, SetItem) are O(n) because they allocate a brand-new array and copy all the elements. There's no tree, no structural sharing.

The output of prices[1] is $49.99. A cleaner trace separates the literal from the print:

The point stands: SetItem does not mutate prices. It allocates a new three-element array, copies positions 0 and 2 from the original, and writes the new value at position 1. The variable prices still references the original array, so it still reports $49.99 at index 1. The variable withDiscount references a different array and reports $39.99.

The struct-wrapper detail matters when you assign one ImmutableArray<T> to another:

Because the struct holds the array reference and nothing more, the wrapper itself is cheap (one machine word). The expensive part is b.Add(4), which allocates a four-element array and copies the three existing values across. For a million-item array, Add is a million-element copy. That's the cost of having O(1) reads.

The other place ImmutableArray<T> wins is interop. Many BCL APIs that consume read-only spans, ReadOnlySpan<T> and ReadOnlyMemory<T>, can be fed directly from ImmutableArray<T> with AsSpan() and AsMemory(), because the underlying buffer is a real array. ImmutableList<T> has no equivalent.

Chains of Add calls on an immutable collection are correct but allocate intermediate objects. If you build a 1,000-item collection by calling Add 1,000 times in a loop, you create 1,000 intermediate immutables. For ImmutableList<T> that's manageable because of structural sharing, but for ImmutableArray<T> it's a thousand array copies. Either way, there's a cleaner approach: use a builder.

Every immutable collection has a paired builder type that's mutable, designed for bulk construction or transformation. Call .ToBuilder() on an existing immutable to get a builder seeded with its contents, mutate the builder freely (with normal Add, Remove, etc. that return void), and then call .ToImmutable() to get a fresh immutable back.

The builder is a normal mutable collection. Its Add returns void. Its indexer has a setter. Its Remove returns bool. You can treat it like a List<T> and stop worrying about reassignment until you're done. The ToImmutable() call at the end snapshots the builder's contents into a fresh ImmutableList<string>, which is what we return or hand to other code.

The builder also keeps the original cart untouched. The builder copies the necessary internal structure when it's modified (the immutable namespace's implementation is careful to copy lazily, only when needed). The original two-item cart is still around and still valid.

The same shape works for every other immutable type:

ImmutableDictionary.CreateBuilder<string, int>() returns a fresh builder, not seeded from anything. The loop sets five entries using the builder's indexer setter (which is mutable, since this is a builder). The Remove deletes the cable entry, and ToImmutable() produces the final dictionary. None of the intermediate builder states is observable from outside this code.

Builders are useful whenever you have more than one mutation to apply in a row, especially in hot paths. The performance gap can be large for ImmutableArray<T>:

Output (approximate, varies by machine):

The chained version does 1,000 array copies of sizes 1, 2, 3, ..., 1,000. The total work is quadratic: roughly 500,000 element copies. The builder does one growth-and-copy pattern internally, total work is linear. For small N the gap is invisible, but at scale it matters.

Use a builder whenever you make more than two or three sequential mutations to an ImmutableArray<T>. For ImmutableList<T>, the per-Add cost is already O(log n), so the gap is smaller, but builders are still cleaner for code that reads like ordinary mutable code.

The two immutable sets mirror HashSet<T> and SortedSet<T>. ImmutableHashSet<T> is unordered with O(log n) add/remove/contains. ImmutableSortedSet<T> keeps items in sorted order, also with O(log n) operations.

Adding a duplicate returns the same instance, not a new one. The immutable types are careful to avoid allocations when nothing actually changes. The ReferenceEquals check confirms it: tags.Add("electronics") returns tags itself because the set already contains the item. That's a small optimization, but it makes "set if absent" patterns nearly free.

Second, the hash-set is O(log n) rather than O(1), which is the usual cost of structural sharing. The internal layout is a tree of hash buckets, not a flat array. If you need true O(1) and don't need immutability, use HashSet<T>.

ImmutableSortedSet<T> adds ordering:

Duplicates are dropped (the input had two 5s, the set has one). Min and Max are O(log n) because they walk to the leftmost or rightmost node, which is cheap on a balanced tree. Set operations (Union, Intersect, Except) are available on both immutable sets and return new sets without mutating either input.

Output (hash-set order is not stable, your output may differ in order):

The operations return new sets and leave both originals unchanged. That's the pattern across the immutable namespace: nothing mutates, everything returns.

ImmutableSortedDictionary<TKey, TValue> is the immutable counterpart to SortedDictionary<TKey, TValue>. It keeps keys in sorted order, supports an IComparer<TKey>, and gives you O(log n) lookups, adds, and removes.

The keys come out in alphabetical order because that's the default string comparison. The unsorted ImmutableDictionary<TKey, TValue> makes no order guarantee.

Use ImmutableSortedDictionary<TKey, TValue> when you need iteration in key order or you need to query ranges. Use ImmutableDictionary<TKey, TValue> when you only need point lookups by key, because its hash-based lookup, while still O(log n) formally, has a smaller constant factor in practice.

The queue and stack are the immutable equivalents of Queue<T> and Stack<T>. Both expose a Peek for the front/top element and return a new collection from Enqueue/Dequeue or Push/Pop.

Dequeue here has an overload that returns the new queue and also outputs the dequeued item. There's a parameterless overload too that just returns the new queue without telling you what was removed (useful when you've already called Peek). The original queue still holds all three orders because immutability is unconditional.

Stacks work the same way, just with LIFO semantics:

The push/pop pattern works well for browser-style history or undo stacks, especially when you want to keep prior states around for redo. Every push and pop produces a new stack, but the older stacks remain valid history. Internally, ImmutableStack<T> is implemented as a singly-linked list, so a push allocates one new node that points to the existing stack. That's the lowest-cost structural sharing of any immutable type.

Hash-based and sort-based immutables let you supply custom IEqualityComparer<T> or IComparer<T> implementations using WithComparer and WithComparers methods. That's how you get case-insensitive keys in an ImmutableDictionary<string, T>, or reverse-sorted keys in an ImmutableSortedSet<int>.

The default ImmutableDictionary<string, TValue> uses the default string equality, which is case-sensitive. Constructing one with ImmutableDictionary.Create<string, TValue>(StringComparer.OrdinalIgnoreCase) swaps in a case-insensitive comparer, and the lookup at "kbd-1" finds the entry stored as "KBD-1".

You can change the comparer of an existing immutable dictionary with WithComparers, which rebuilds the internal structure (an O(n) operation):

The same approach works on ImmutableSortedSet<T> and ImmutableSortedDictionary<TKey, TValue> for ordering. Calling WithComparer(myComparer) produces a new collection with the keys re-sorted under the new comparer.

C# has three different shapes for "safe sharing of a collection," and they solve different problems. The _ReadOnly Collections_ lesson covers read-only wrappers in detail, and the _Concurrent Collections_ lesson already covered concurrent collections, but here's the side-by-side that matters when you're picking one:

The distinction between the first two: an ImmutableList<T> is truly immutable. There's no underlying collection that can change. A ReadOnlyCollection<T> is a view that lacks mutation methods, but the underlying IList<T> it wraps can still be mutated by anyone holding that underlying reference. If you hand a ReadOnlyCollection<T> to a consumer and then Add to the underlying List<T>, the consumer sees the new item.

In the immutable case, the only thing the holder can do is read, and the data itself can't change. In the read-only case, the holder is fenced off from mutation, but the underlying List<T> (red) is still mutable, and anyone with the other reference can change it. That's why immutability is the stronger guarantee.

When you need cross-thread reads and the producer is also publishing updates as snapshots, immutables fit. The producer publishes a new immutable reference, readers see either the old version or the new version, never an in-progress state. This is the Redux/Elm style of state management, which works well in C# even for non-UI code.

The Snapshot() method returns the current ImmutableList<string> reference. The caller can read it at leisure, and even if the producer later replaces the field with a new immutable, the snapshot the caller already holds doesn't change. The Add method uses a lock-free compare-and-swap (Interlocked.CompareExchange) to publish the new state atomically: any reader either sees the old reference or the new one, never a half-built collection.

That pattern, "publish snapshots, read without locking," is the canonical use case for immutables. Compare it with ConcurrentBag<T> or ConcurrentDictionary<TKey, TValue>: those let you mutate concurrently, but they don't give you a snapshot. If you call bag.ToArray() to get a snapshot, that's a real copy, with all the cost of one. Immutables provide snapshot semantics without a copy, because every reference is a snapshot.

Every immutable collection implements IEnumerable<T>, so they all work with foreach and the full LINQ surface (Where, Select, OrderBy, Aggregate, and so on). Enumeration is O(n) total, same as any other collection.

LINQ over an immutable returns the standard LINQ types (IEnumerable<T> or IOrderedEnumerable<T>), not another immutable. If you want a new immutable as the output, call the appropriate ToImmutable* at the end:

The chain filters by price, applies a 10% discount, and materializes the result back into an ImmutableList<decimal>. There's nothing immutable-specific about the LINQ chain itself, the immutability only re-enters when you call ToImmutableList().

Pulling the pieces together: a typical use case for immutables is keeping a history of states for auditing or undo, without paying the cost of copying mutable collections at every step.

Output (timestamps will vary):

Each Record call stores the current ImmutableList<string> reference. Later changes to cart allocate a new immutable; the older references stored in _history aren't affected. Audit logs that capture state at a moment in time fit immutables well. With a mutable List<T> you'd have to clone the list at every record point, doubling the memory each step.

The structural sharing makes this realistic at scale. If the cart has 100 items and you record 100 snapshots over the user's session, you don't hold 10,000 strings in memory. You hold 100 strings plus a small set of tree nodes per snapshot, which is much closer to a few hundred extra references than to 10,000.

The full menu of immutable collections, with their cost profiles and typical use cases:

Two patterns to follow. First, always assign the return of any "mutation" call back to a variable; the original is unchanged. Second, use a builder whenever you have more than two or three sequential changes. The rest of the API matches your intuition from the mutable List<T>, Dictionary<TKey, TValue>, HashSet<T>, Queue<T>, and Stack<T> collections, with the "I never change" promise on top.