A mutable object is a data structure whose contents can change after creation. Updating an integer array changes the existing storage without allocating another array. That is efficient when only the newest state matters, but retaining both old and new states requires copying the entire array. section 2.1.6
Mutation is convenient when construction naturally proceeds from the root toward the leaves. Trie nodes therefore keep mutable edge mappings and an end-of-word flag. Encapsulation still matters: operations such as HasEdge and FollowEdge expose node-and-edge behavior while hiding the dictionary implementation. section 5.2.1
Mutation becomes especially consequential when several states or reversals are required:
- Keeping original and changed versions of mutable state requires explicit copying. section 2.1.6
- Undo-redo over mutable program state requires command pairs that reverse and reapply every mutation, plus stacks for pending operations. section 2.6.2
- Immutable alternatives can share internal state through persistence, often making multiple versions easier to retain and reason about. section 2.1.6 section 2.8
Listing 5.2 A trie node
sealed class Node
{
private readonly Dictionary<char, Node> edges = [];
public bool IsEnd { get; set; }
public IEnumerable<char> EdgeLabels => edges.Keys;
public Node FollowEdge(char c) => edges [c]; #1
public Node? TryFollowEdge(char c) => #2
HasEdge(c) ? FollowEdge(c) : null;
public bool HasEdge(char c) => edges.ContainsKey(c);
public Node AddNewNode(char c) => edges [c] = new();
public Node TryAddNewNode(char c) =>
HasEdge(c) ? FollowEdge(c) : AddNewNode(c);
}
Inspect a compact C# trie node whose mutable dictionary stores outgoing edges and whose IsEnd property marks complete words. section 5.2.1
