chapter three

3 An immutable deque

 

This chapter covers

  • Combining stacks and queues into one type, the double-ended queue, or deque
  • Comparing the performance of a linked list implementation to that of a finger tree
  • Extending the deque to implement cheap concatenation

The interface of an immutable double-ended queue, or deque, is a straightforward extension of the single-ended queue data type, but finding a data structure that lets us cheaply add and remove items from both ends of the list isn’t easy. The naïve approach of building a linked list that can be linked in two directions is tempting, but we’ll see that its performance is poor. Also, it would be nice if we could somehow reduce the O(n) worst case for dequeuing, which our queue implementation in chapter 2 demonstrates. In short, we have to be smarter about choosing a data structure to implement these abstract data types. The data structure we’ll use in this chapter is considerably more complex than any we’ve seen so far.

3.1 An immutable deque abstract data type

3.2 A bad naïve implementation

3.3 A finger tree

3.3.1 The mini-deque

3.3.2 A new definition of a deque

3.4 Visualizing the data structure

3.5 Amortized performance of the deque

3.6 Are we abusing the type system?

3.7 Concatenation of deques

3.8 Performance after adding concatenation

3.9 Why is this tree called a finger tree?

Summary