chapter three

3 An immutable deque

 

This chapter covers

  • A double-ended queue, or “deque”, is easy to envision but harder to implement
  • Using linked lists is tempting, but impractical
  • A better data structure is the finger tree
  • Finger trees are also cheap to concatenate

The immutable deque interface is a straightforward extension of the single-ended queue data type, but coming up with the data structure that allows us to cheaply add and remove items from both ends of the list is not so easy. The naïve approach of building a linked list that can be linked in two directions is tempting, but we’ll see that the performance is bad. And it would be really nice if we could somehow reduce the O(n) worst case for dequeuing that our previous queue implementation suffers from. In short, we need to be smarter about choosing a data structure to implement these abstract data types.

3.1 An immutable deque ADT

3.2 A bad naïve implementation

3.3 A finger tree

3.3.1 Step one: 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.7.1 Performance after adding concatenation

3.8 Why is this called a “finger tree”?

3.9 Summary