Chapter 3: An immutable deque

Introduction

This chapter introduces immutable deques, motivates replacing naïve linked-list approaches with finger trees, and previews sublinear deque concatenation.

• Immutable deque requirements: Describe an immutable double-ended queue as an extension of a single-ended queue that must support adding and removing items cheaply at both ends. Explain why choosing a suitable underlying data structure is the central challenge.
  Why it matters: A deque’s interface is simple, but its performance depends heavily on how the data is represented.
• Finger tree performance strategy: Explain that a finger tree keeps designated nodes called fingers close to the root, placing them at the left and right sides and representing the deque’s center recursively. State that this design gives deque operations O(log n) worst-case time rather than O(n).
  Why it matters: Keeping both ends near the root avoids the linear worst cases that make simpler immutable deque designs unattractive.
• Sublinear deque concatenation: Contrast the Hughes list’s apparent O(1) concatenation, which defers an O(n) concatenation operation, with the chapter’s goal of concatenating two deques in sublinear time.
  Why it matters: The distinction shows why postponing linear work is different from designing a structure that combines deques in genuinely sublinear time.

Key terms: immutable double-ended queue, deque, single-ended queue, finger tree, fingers, root, recursively, O(log n), O(n), Hughes list

3.1 An immutable deque abstract data type

Defines the immutable deque interface as an enumerable double-ended sequence with cheap operations at both ends.

• Deque end operations: Describe a deque as a sequence that supports pushing, peeking, and popping at both its left and right ends. State the interface names PushLeft, PushRight, PopLeft, PopRight, Left, and Right.
  Why it matters: A deque’s defining feature is efficient access and updates at either end rather than at only one fixed end.
• Immutable operation results: Explain that operations normally regarded as mutations, such as pushing or popping, return a new deque object because the deque is immutable. Distinguish this from changing the existing deque in place.
  Why it matters: Returning new values preserves the old deque while still allowing code to express updates.
• Constant-cost deque requirements: State that every deque end operation, including pushes, pops, and peeks, should be cheap regardless of the number of items in the deque. Include the ability to test whether the deque is empty.
  Why it matters: This performance requirement is the standard by which the later deque implementations are judged.
• Left-to-right enumeration: Describe the deque as an IEnumerable<T> sequence and state that its chosen natural enumeration order is from left to right.
  Why it matters: A fixed enumeration direction makes the deque’s sequence behavior unambiguous to its users.

Key terms: deque, PushLeft, PushRight, PopLeft, PopRight, Left, immutable types, new object, empty, cheap

3.2 A bad naïve implementation

This section presents a plausible recursive immutable deque implementation and shows that, despite cheap-looking end access, it rebuilds the whole structure and performs disastrously.

• Naïve recursive deque structure: Describe the naïve deque representation as either empty, a single item, or a left item and right item surrounding a middle deque, and explain how the middle stores the remaining items.
  Why it matters: The representation explains why operations can appear to have direct access to both ends while still hiding expensive reconstruction.
• Whole-structure reconstruction: Explain why pushing or popping at either end creates a new deque through the nested structure rather than reusing most of the old one, so the implementation is not persistent.
  Why it matters: Immutable structures are useful only when new versions can share substantial existing structure instead of copying it all.
• Recursive enumeration costs: State that the naïve recursive GetEnumerator uses O(n) stack space and takes O(n²) time because O(n) items are copied up a call stack of depth O(n).
  Why it matters: Even reading all the elements can become unnecessarily expensive when recursion repeatedly copies partial results.

Key terms: deque, empty deque, single-item deque, left item, middle deque, right item, persistent, immutable data structure, reuse, push

3.3 A finger tree

This section introduces the finger-tree idea as a way to make immutable deque operations near either end cheap by keeping the ends close to the root and making costly overflows less frequent.

• Finger tree end accessibility: Explain how a finger tree keeps designated finger nodes close to the root, so nodes nearer a finger are shallower and cheaper to reach. For a deque, identify the leftmost and rightmost nodes as the fingers, with middle items deeper in the tree.
  Why it matters: This layout is the central idea behind making operations at both ends of an immutable deque efficient.
• Overflow frequency strategy: Describe why the naïve deque is expensive when pushes overflow repeatedly into nested middle deques, and explain the proposed strategy of giving the left and right ends more room so expensive overflows happen less often. State that the helper structure will also be used to make the middle cheaper.
  Why it matters: Reducing how often overflow cascades occur is what turns the promising end-and-middle design into an efficient deque.

Key terms: finger tree, fingers, root, leftmost node, rightmost node, deque, overflow, middle, left end, right end

3.3.1 The mini-deque

This subsection defines the bounded immutable mini-deque helper used to create space at both ends of the finger-tree deque.

• Mini-deque size contract: Describe the mini-deque as a deque-like immutable helper that holds from one to four items and supports pushes and pops at both the left and right ends.
  Why it matters: The mini’s fixed nonempty size range is the constraint that makes it suitable as a building block for the finger-tree deque.
• Boundary operation failures: State that popping a one-item mini or pushing onto a four-item mini produces an error, because minis may never become empty or exceed four items.
  Why it matters: These explicit boundary failures enforce the mini-deque’s contract rather than silently turning it into an ordinary deque.
• Dedicated mini interface: Explain why minis have their own interface with a size operation: their contract differs from the main deque, and callers need to determine a mini’s size quickly.
  Why it matters: A separate interface makes the bounded helper’s different guarantees visible in the code.
• Record-based mini representation: Describe the straightforward implementation as records representing tuples of one, two, three, or four items, with the helper code nested inside the main class.
  Why it matters: This representation directly matches the mini’s four possible valid sizes and keeps implementation helpers localized.

Key terms: mini-deque, mini, deque, immutable, one-item mini, four-item mini, pop, push, error, interface

3.3.2 A new definition of a deque

This section redefines an immutable deque as edge mini-deques around a recursive middle deque of chunks, and explains the push and pop cases that preserve its chunk invariant.

• Recursive deque representation: Describe the new recursive definition of a deque: it is empty, contains one item, or consists of a left mini, a middle deque of minis, and a right mini. Explain that the middle holds mini-deques rather than individual items.
  Why it matters: This recursive representation is what lets the deque keep its ends cheap to manipulate while organizing larger chunks toward the middle.
• Chunking strategy and invariant: Explain why the deque manipulates items in mini-deques of one to four at the edges and chunks in the middle. State the initial invariant that the middle deque contains only Threes, so no one-item chunk is ever placed in the middle.
  Why it matters: Keeping multi-item chunks in the middle makes most end operations cheap and persistent while allowing chunk sizes to grow recursively inward.
• Left-side push cases: Trace a push onto the left of a multiple-element deque. Explain that a nonfull left mini is enlarged and the middle and right are reused; when the left mini is a Four, three old items are pushed as a Three into the middle and the new item plus the remaining old item form a Two at the left.
  Why it matters: These two cases show how an overflowing edge is repaired without violating the middle-contains-Threes invariant.
• Left-side pop cases: Trace the four cases for popping from the left of a multiple-element deque: shrink a left mini with at least two items; replace a left One from a popped middle Three; borrow one item from a non-One right mini when the middle is empty; or return a Single when both edge minis are Ones and the middle is empty. State that right-side operations are the reversed counterpart.
  Why it matters: The pop cases preserve valid edge minis and correctly collapse the representation when only two items remain.

Key terms: deque of items, mini, middle deque of minis, EmptyDeque, SingleDeque, Threes, deque of minis, chunk, persistence, O(1)

3.4 Visualizing the data structure

This section visualizes how an immutable finger-tree deque grows at its edges by overflowing fixed-size minis into recursively deeper middle deques.

• Edge overflow into middle: Trace what happens when adding an item to a full left or right Four: three items are packaged into a Three and pushed into the middle deque, while the new item remains available in the edge mini.
  Why it matters: This explains how the deque can accept edge insertions without rebuilding all of its contents.
• Recursive deque levels: Describe how the deque's middle is itself a deque whose items are minis from the level above, so an overflow at one level can cause another overflow and create a deeper level.
  Why it matters: The recursive levels are the structural reason this deque is a finger tree rather than a single flat buffer.
• Exponentially growing edge buffers: Explain why deeper levels represent increasingly large edge buffers: top-level minis hold one to four characters, while a next-level mini of Threes represents three, six, nine, or twelve characters, so deeper levels overflow much less often.
  Why it matters: Slow deepening is the intuition behind the deque's efficient edge operations.

Key terms: Four, Three, mini, middle, EmptyDeque, SingleDeque, finger tree, deque of minis, Three of Threes, level

3.5 Amortized performance of the deque

This section analyzes the finger-tree deque’s update-cost distribution to show constant amortized operations, logarithmic worst cases and depth, reasonable storage overhead, and efficient persistence.

• Update-cost distribution: Trace how left pushes, and likewise pops, propagate through deque levels: two out of three affect one level, two out of nine affect two levels, and in general two out of 3^d affect d levels.
  Why it matters: This distribution explains why occasional multi-level updates do not make ordinary deque operations expensive.
• Amortized and worst-case costs: Explain that push and pop have O(1) amortized time, while an individual worst-case operation takes O(log_3 n) time and extra space because it can update one path through the levels.
  Why it matters: The deque improves on the earlier immutable queue by making even its rare worst-case operations cheap.
• Storage overhead bound: Describe the storage overhead of nested Threes: a tree holding 3^d items has (3^d-1)/2 extra objects, so additional storage is less than half the item count and is O(1) per item or O(n) overall.
  Why it matters: The performance claim includes space as well as time, showing that the recursive representation does not impose excessive overhead.
• Persistence and shallow recursion: Explain that the deque remains persistent because most updates rebuild only the affected end minis while sharing the unchanged middle and opposite side, and that O(log_3 n) depth keeps recursive call-stack use small without complex balancing invariants.
  Why it matters: Structural sharing preserves old deques cheaply, while shallow depth makes recursive operations practical even for very large deques.

Key terms: left push, pop, level, left mini, middle, Three, amortized cost, worst case, O(1), O(log3 n)

3.6 Are we abusing the type system?

This section explains why the finger tree’s increasingly nested generic types are safe and practical in C# and Java.

• Nested generic middle types: Explain why a deque’s middle has a more deeply nested generic type at each tree level rather than the exact same deque type, and why this does not create an unbounded practical problem in C# or Java.
  Why it matters: Understanding the nested types shows why the recursive deque representation remains implementable as the structure grows.

Key terms: middle, IDeque, IMini, generic types, templates, O(log3 n)

3.7 Concatenation of deques

This section adds efficient concatenation to immutable finger-tree deques by allowing middle deques to contain Two and Three mini-deques and recursively joining their middles.

• Concatenation interface and base cases: Describe the Concatenate operation added to the deque interface and explain how concatenation works when the left deque is empty or contains one item.
  Why it matters: The simple cases establish the identity and single-item behavior needed by the general concatenation algorithm.
• Two-and-Three middle invariant: Explain why the middle deque invariant is weakened from only Threes to a mixture of Twos and Threes, and describe how concatenating mini-deques produces a sequence of valid Twos and Threes.
  Why it matters: Allowing Twos as well as Threes makes it possible to rearrange boundary mini-deques during genuinely cheap concatenation.
• Recursive multi-deque concatenation: Trace concatenation of two multiple-item deques: retain the outer left and right mini-deques, turn the adjacent inner boundary minis into Twos and Threes, push those onto the left middle, and recursively concatenate that result with the right middle.
  Why it matters: This recursive restructuring is the central technique that joins two finger-tree deques without traversing all of their stored items.
• Non-multiple right operand handling: Describe the second multiple-item concatenation case: when the left deque has multiple items but the right deque is not multiple-item, push every item of the right deque onto the left side of the left deque.
  Why it matters: This case completes concatenation behavior when only one operand has the full left-middle-right finger-tree representation.

Key terms: Concatenate, EmptyDeque, SingleDeque, mini-deque, Two, Three, middle deque, invariant, Deque, middle

3.8 Performance after adding concatenation

This section shows that allowing Twos in a finger tree’s middle preserves efficient deque operations while enabling logarithmic-time concatenation.

• Weakened invariant performance: Explain how permitting Twos in the middle deque changes the tree depth and bad-case frequency without meaningfully changing the deque’s asymptotic push and pop performance.
  Why it matters: The relaxed invariant buys efficient concatenation while retaining the deque’s low-cost end operations.
• Concatenation cost analysis: Describe the empty, single-item, and multiple-item concatenation cases, and trace why concatenating two multiple-item deques has O(log n) time and extra-space cost in the worst case.
  Why it matters: Concatenation is the new capability enabled by weakening the invariant, and its logarithmic cost makes the deque practical for composition.
• Concatenation performance trade-off: Justify why the weakened invariant is worthwhile: it preserves a highly persistent deque with amortized O(1) pushes and pops while adding similarly low-cost concatenation.
  Why it matters: This trade-off explains the design decision rather than treating the relaxed invariant as an arbitrary implementation change.

Key terms: invariant, Twos, middle deque, O(log3 n), O(log2 n), amortized cost, concatenation, TwosOrThrees, PushRightMany, intermediary deque

3.9 Why is this tree called a finger tree?

This section identifies the chapter’s deque as a finger tree and explains why fingers at both ends make it suitable for efficient sequence operations.

• Finger tree structure: Explain what a finger tree is: a tree with selected nodes called fingers that is reorganized so operations near a finger have amortized cost proportional to the logarithm of the distance to the nearest finger.
  Why it matters: This explains the general data-structure idea behind the deque developed in the chapter.
• Deque endpoint fingers: Describe why the chapter’s immutable deque uses its leftmost and rightmost nodes as fingers: a deque needs guaranteed cheap access at both ends and does not especially need cheap access to the middle.
  Why it matters: Choosing the two ends as fingers matches the performance priorities of a double-ended queue.
• Broader finger-tree applications: State that adding capabilities such as tracking deque size and splitting a deque can support efficient persistent immutable finger-tree implementations of other structures, including priority queues and interval trees.
  Why it matters: The deque is one specialized instance of a more general persistent sequence technique.

Key terms: finger tree, fingers, amortized cost, leftmost node, rightmost node, double-ended queue, persistent, immutable, priority queues, interval trees

3.10 Summary

This summary recaps how finger trees provide an efficient persistent immutable deque, the design techniques behind them, and their cheap concatenation.