3 An immutable deque
This chapter introduces the challenge of implementing an immutable double-ended queue, or deque: a sequence that supports pushing, popping, and peeking from both the left and right ends. Although the interface is simple, a straightforward recursive linked-list-like implementation performs poorly because operations can rebuild large portions of the structure, leading to linear time and memory costs. The chapter motivates the need for a more persistent and efficient representation that reuses most of the old structure when producing new versions.
The main solution developed is a finger-tree-style deque. Instead of storing single items at the ends and another deque in the middle, the structure stores small fixed-size “mini-deques” at the left and right, with a middle deque containing chunks of items. Most pushes and pops modify only a small mini-deque at the edge, while occasional overflows move chunks into deeper levels. This creates a tree where the leftmost and rightmost elements remain close to the root, while the middle grows deeper only gradually. As a result, pushes and pops have amortized constant cost, logarithmic worst-case cost, reasonable memory overhead, and strong persistence.
The chapter also extends the structure to support efficient concatenation. By relaxing the internal invariant so middle deques may contain chunks of size two or three, two deques can be joined recursively without flattening either structure. Empty and single-item cases are simple, while multi-item concatenation combines boundary mini-deques into valid chunks and recursively joins the middles. This preserves the desirable asymptotic behavior: pushes and pops remain cheap, and concatenation runs in logarithmic time and space. The chapter concludes by explaining that this deque is a specific example of a broader finger tree technique, useful for efficient immutable sequence-like data structures.
Two immutable deques, before and after pushing 9 onto the right. Deques are represented by ovals containing the left and right values, or the single value for a singleton deque. Each deque points to its center deque.
An eight-item deque can have four items in the left mini, four in the right mini, and the middle is empty.
First, a nine-item deque after pushing Q onto the left. The left mini containing RSTU cannot grow further to hold the Q, so we push a Three containing STU into the middle, which is a deque of minis, not a deque of chars. Second, when we push Z onto the right, the mini containing VWXY cannot grow, so we push a Three containing VWX into the middle. When we’re all done, the middle deque has two Threes in it: a One containing a Three on the left, an empty middle, and a One containing a Three on the right.
A 21-item deque: every time we push an item on the left of the topmost deque, if it is not a Four then the size of the left mini gets bigger and everything else stays the same. When we try to put a fifth item into a Four, we instead make a Two and push a Three into the middle. The deque of minis in the middle then puts that into its left mini, which is itself now quite full.
A 22-item deque: the left mini on the second level has overflowed, so we’ve made a single-item deque-of-minis-of-minis to hold three Threes. Notice how the number of arrows traversed from the root to any given leaf is shallowest at the left and right edges, and deepest in the middle.
A scenario for concatenating together two 13-item deques.
Turn the two Fours into a Two, a Three and a Three
The result of pushing the sequence of Twos and Threes into the middle of the left deque.
We’ve reduced the concatenation problem to a smaller problem which we can solve recursively
Break up a Four and a One to turn them into a Two and a Three
Our second intermediate deque is the result of pushing the Three and the Two into the middle of the first intermediate deque, which is empty. The result is a two-item deque.
This is the solution to the concatenation problem shown in Figure 3.9. We’ve taken the deque from Figure 3.11 for the middle, and the left and right sides of the two deques being concatenated.
The solution to the concatenation problem given in Figure 3.6.
Summary
- It’s quite easy to accidentally design an immutable data structure that works, but accidentally lacks the persistence needed to make it efficient. To build a proper immutable double-ended queue with good performance we need to stop trying to use linked lists and start taking advantage of the power of trees.
- Finger trees make some nodes – the “fingers” – in a tree very shallow, and the farther you get from them, the deeper the tree is. This data structure is surprisingly well suited to lists because it is immutable, persistent, and cheap. Most operations are O(1) on average and since the tree is O(log n) deep, even the worst cases that have to change a leaf end up only costing O(log n) in time and extra memory.
- A useful trick when designing data structures is to solve a much more restricted version of the problem in the most straightforward way possible and then leverage that into an elegant solution to the larger problem. Solving the problem of deques restricted to sizes one, two, three and four items with easy code that just handled every possible case explicitly was a key step.
- Languages with truly generic type systems have a lot of power that often goes untapped. Being able to code up a data structure with an unbounded recursion on types and have the compiler and runtime ensure type safety is an amazing tool to have in your toolbox.
- Cheap concatenation is a nice property to have on lists. Though there are quite a few cases to consider, the recursive concatenation algorithm is conceptually straightforward: if we’re not in a trivial case, solve the smaller problem of recursively concatenating the middles. This is very useful when building lists out of many smaller lists.
FAQ
What is an immutable deque?
An immutable deque, or double-ended queue, is a list-like abstract data type that supports adding, removing, and peeking at both ends. In this chapter the main operations are PushLeft, PushRight, PopLeft, PopRight, Left, Right, and IsEmpty. Because the deque is immutable, operations that would normally mutate the structure instead return a new deque.
How is a deque different from a stack or a queue?
A stack pushes and pops items from the same end, while a queue usually enqueues at one end and dequeues from the other. A deque generalizes both: it allows pushing, popping, and peeking from both the left and right ends.
Why is a naïve linked-list-like immutable deque implementation inefficient?
The naïve recursive implementation stores a left item, a middle deque, and a right item. Although this seems natural, every push or pop may rebuild a large portion of the structure. It is not very persistent because new versions fail to reuse enough of the old version. Push and pop operations can require O(n) time and extra memory, and the recursive enumerator can be O(n) in stack space and O(n²) in time.
What is a finger tree?
A finger tree is a tree organized so that selected nodes, called “fingers,” are always close to the root and therefore cheap to access. In the deque implementation, the leftmost and rightmost ends are the fingers. Items near the ends remain shallow in the tree, while items closer to the middle may be deeper.
Why are finger trees useful for implementing immutable deques?
Finger trees provide cheap access to both ends of the sequence, which is exactly what a deque needs. They allow most pushes and pops to update only a small part of the structure, while reusing most existing nodes. This gives the deque good persistence, amortized O(1) push and pop operations, and logarithmic worst-case behavior rather than linear worst-case behavior.
What is a mini-deque in this chapter?
A mini-deque, or “mini,” is a small helper structure that contains exactly one, two, three, or four items. It supports pushing and popping on both ends, but pushing a four-item mini or popping a one-item mini is an error. Minis act as small buffers at the left and right ends of each deque level.
How does the improved deque structure use minis?
The improved deque is recursively defined as either empty, a single item, or a left mini followed by a middle deque of minis followed by a right mini. The key idea is that the middle is not a deque of individual items; it is a deque of chunks. This makes the structure “chunky,” so overflows happen less often and move multiple items at once.
What happens when a mini overflows during a push?
If the left or right mini has fewer than four items, the push simply creates a new, slightly larger mini and reuses the rest of the deque. If the mini already has four items, three of its items are grouped into a Three and pushed into the middle deque, while the new edge mini becomes a Two. This preserves cheap access to the edge while moving a larger chunk toward the middle.
What are the performance characteristics of the finger-tree deque?
Most pushes and pops update only the top-level mini and are very cheap. Occasionally an operation overflows into the middle, and rarely it overflows through multiple levels. The worst-case cost of a push or pop is O(log n) time and extra space, but the amortized cost is O(1). The structure also uses O(n) total extra storage overall, or O(1) overhead per stored item on average.
How does concatenation work for two finger-tree deques?
Concatenation is made efficient by slightly weakening the invariant so that middle deques may contain both Twos and Threes, not just Threes. To concatenate two multi-item deques, the left side of the left deque and the right side of the right deque are reused. The right mini of the left deque and the left mini of the right deque are converted into a short sequence of Twos and Threes, pushed into the middle, and the middle deques are concatenated recursively. The resulting concatenation runs in O(log n) time and extra space.
Fabulous Adventures in Data Structures and Algorithms ebook for free
