3 An immutable deque

This chapter introduces an immutable deque, a sequence that supports efficient access at both ends. It starts by defining the deque API in terms of push, pop, peek, emptiness checks, and enumeration, with all updates returning new versions rather than modifying existing ones. A simple linked structure might seem like an obvious implementation, but the chapter shows that this approach quickly becomes inefficient, especially when trying to preserve immutability and keep operations cheap.

To solve that problem, the chapter builds up to a finger tree–based deque. First it introduces a small helper structure that can hold one to four items, which serves as a flexible buffer at the ends of the deque. Then it defines the deque recursively as left and right buffers surrounding a middle deque of smaller buffered chunks. This design makes most pushes and pops touch only a small part of the structure, while occasional overflows move grouped items inward, keeping the outer edges shallow and fast to access.

The chapter then analyzes why this structure performs well: pushes and pops are amortized O(1), with worst-case cost only logarithmic in the size of the deque, and the structure remains highly persistent because most of it is reused across versions. It also explains that the nested generic types are not a problem in C# because generics are handled efficiently at runtime. Finally, the chapter extends the deque with concatenation by relaxing one invariant slightly, allowing both two-item and three-item chunks in the middle so that two deques can be joined in sublinear time while preserving the same overall performance benefits.

Two immutable deques, before and after pushing 9 onto the right. Deques are represented by ovals containing the left and right values or a 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 and four in the right mini; the middle is empty.

A nine-item deque after we push Q onto the left. The left mini containing R, S, T, U couldn’t grow to hold Q, so we pushed a Three containing S, T, U onto the middle, which is a deque of minis, not a deque of chars. Second, when we push Z onto the right, the mini containing V, W, X, Y couldn’t grow, so we pushed a Three containing V, W, X onto the middle. When we’re 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 onto the left of the topmost deque, if it isn’t a Four, 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 onto the middle. Then the deque of minis in the middle puts that Three in its left mini, which is quite full now.

 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 that 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 two 13-item deques

Turning the two Fours into a Two, a Three, and a Three

The result of pushing the sequence of Twos and Threes onto the middle of the left deque

We’ve reduced the concatenation problem to a smaller problem that we can solve recursively.

 Breaking up a Four and a One to turn them into a Two and a Three

 Our second intermediate deque results from pushing the Three and the Two onto the middle of the first intermediate deque, which is empty. The result is a two-item deque.

 The solution to the concatenation problem shown in figure 3.9. We’ve taken the deque from figure 3.11 for the middle, along with the left and right sides of the two deques being concatenated.

 The solution to the concatenation problem in figure 3.6

• It’s easy to accidentally design an immutable data structure that works but lacks the persistence required to be efficient. To build a proper immutable double-­ended queue with good performance, we have to stop trying to use linked lists and start taking advantage of the power of trees.
• Finger trees make some nodes (the fingers) shallow, and the farther you get from them, the deeper the tree is. This data structure is surprisingly well suited to lists because it’s immutable, persistent, and cheap. Most operations are O(1) on average, and because the tree is O(log n) deep, even the worst cases that have to change a leaf end up costing only O(log n) in time and extra memory.
• A useful trick when designing data structures is solving a much more restricted version of the problem in the most straightforward way possible and then use that version to build 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 handles every possible case explicitly is a key step.
• Languages with truly generic type systems have a lot of power that often goes untapped. Being able to code a data structure with unbounded recursion on types and having the compiler and runtime ensure type safety is an amazing tool to have in your toolbox.
• Cheap concatenation is a nice property to have for lists. Though there are quite a few cases to consider, the recursive concatenation algorithm is conceptually straightforward: if you’re not dealing with a trivial case, solve the smaller problem of recursively concatenating the middles. This technique is useful for building lists from many smaller lists.

FAQ