chapter two

2 Immutable stacks and queues

 

This chapter covers

  • 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

We’ll expand upon the immutable linked list in Chapter 1 to build lists that illustrate diverse concepts. These ideas might already be familiar if you have a background in functional languages; I’ve found they’re less familiar to OO programmers, but they’re powerful tools to add to your problem-solving toolbox.

We’ll start with building an immutable stack by making marginal improvements to our linked list. Once we have immutable stacks we can build an immutable queue, which will show how worst-case performance and average performance amortized over time can be very different. We’ll explore how immutable data structures enable undo-redo logic, and how you can build a mutable interface on top of an immutable data structure. Finally, we’ll look at the Hughes list, a bizarre stack implementation which at first glance appears to contain no actual data and has very different performance characteristics than our run-of-the-mill stack.

In each section we’ll first define the problem we’re attempting to solve with the data structure, create an interface, make some attempts at implementation, and finish up with an informal performance analysis.

2.1 Why immutability?

2.1.1 Correctness

2.1.2 Historical preservation

2.1.3 Security: TOCTOU me about it

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.2.1 A covariant immutable stack

2.3 A queue, a queue, an immutable queue

2.4 Mutable wrappers

2.5 Undo and redo

2.5.1 Create an army of clones

2.5.2 Use a different data structure and the command pattern

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

2.6 The Hughes List: build it for cheap, pay for it later

2.6.1 Reverse redux

2.6.2 Currying and partial application

2.6.3 Implementing the Hughes list

2.6.4 Complexity of the Hughes list

2.6.5 Where is the data in this data structure?

2.6.6 A couple more performance considerations

2.6.7 Reverse a linked list

2.7 Summary