chapter two

2 Immutable stacks and queues

 

This chapter covers

  • Discovering the compelling benefits and small costs of immutable data structures
  • Implementing stacks and queues
  • Exploring ways to build an undo-redo stack
  • Analyzing time and space complexity
  • Implementing the Hughes list

This chapter expands on the immutable linked list in chapter 1 to build lists that illustrate diverse concepts. These ideas may be familiar if you have a background in functional languages. I’ve found that they’re less familiar to object-oriented programmers, but they’re powerful tools to add to your problem-solving toolbox.

We’ll start by building an immutable stack, making marginal improvements to our linked list. After we have immutable stacks, we can build an immutable queue, which shows how different worst-case performance and average performance amortized over time can be. We’ll explore how immutable data structures enable undo-redo logic and how to build a mutable interface on top of an immutable data structure. Finally, we’ll look at the Hughes list, a stack implementation that at first glance appears to contain no data and has very different performance characteristics from our run-­of-the-mill stack. In each section, we’ll define the problem we’re attempting to solve with the data structure, create an interface, make some attempts at implementation, and finish with an informal performance analysis.

2.1 Why immutability?

2.1.1 Correctness

2.1.2 Historical preservation

2.1.3 Security

2.1.4 Safer multithreading

2.1.5 Memoization for time performance

2.1.6 Persistence for space performance

2.1.7 The functional programming attitude

2.2 An immutable stack

2.3 A covariant immutable stack

2.4 A queue, a queue, an immutable queue

2.5 Mutable wrappers

2.6 Undo and redo

2.6.1 Create an army of clones

2.6.2 Use a different data structure and the command pattern

2.6.3 Undo and redo with mutable-over-immutable data structures

2.7 The Hughes list: Build it cheap, pay for it later