2 Immutable stacks and queues

This chapter introduces immutable data structures as a practical alternative to mutable ones, arguing that immutability improves correctness, makes past states easy to preserve, reduces security risks such as TOCTOU bugs, and simplifies multithreaded code. It also explains that immutable structures can still be efficient because they are persistent, meaning new versions can share most of their internal structure instead of copying everything. Along the way, the chapter emphasizes a functional-programming mindset while showing that these ideas can be very useful in object-oriented languages too.

The chapter then builds an immutable stack from a linked-list-like design, starting from an abstract data type rather than from the implementation. The stack uses a singleton empty object and a nonempty node type, with operations such as push, peek, pop, and emptiness checks implemented so that no mutation occurs. This design avoids null references, supports covariance by moving push into an extension method, and demonstrates how the stack’s persistent structure lets multiple variables share nodes safely while keeping operations like push, pop, peek, and enumeration efficient.

From there, the chapter develops an immutable queue using two stacks, one for enqueues and one for dequeues, and analyzes both worst-case and amortized performance. It also shows how immutable data structures make undo-redo logic much simpler by wrapping them in a mutable interface that stores previous versions, then extends the idea to the Hughes list, a function-based list representation that makes push, append, and concatenation cheap by deferring work into closures. The Hughes list reveals that the “data” is hidden in captured state inside delegates, and the chapter closes by noting its strengths for building lists incrementally, its expensive access operations, and the tradeoff between delayed work and immediate efficiency.

Each variable in the example code references a particular immutable stack. Stacks with the same tail can refer to the same immutable object.

The example includes six immutable queues and six immutable stacks. Because the data structures are persistent and immutable, objects can be reused across different queues.

 A Hughes list is secretly a binary graph. Delegates created from lambda bodies have automatically created closure classes with fields hl1 and hl2 that refer to the left and right lists being concatenated.

• Immutable data structures are easier to reason about and often safer than the equivalent mutable data structure.
• Persistence makes immutable data structures efficient in space.
• Immutable data structures can be made time-efficient as well, though there are pitfalls to be wary of when some operations are expensive.
• Undo-redo operations are straightforward when program state is immutable.
• The Hughes list shifts the performance costs of seemingly expensive operations by performing them in the optimal order later, but it makes some normally cheap operations, such as Pop, expensive. There’s no free lunch, but costs can be pushed into the future.

FAQ