An immutable deque needs cheap pushes and pops at both ends. A linked list is a tempting starting point, but it does not provide the desired performance. A finger tree takes a different approach: it keeps chosen nodes—the fingers—near the root. For a deque, the fingers are at the left and right ends. Items farther toward the middle can sit deeper in the tree. section 3.0 section 3.3
The deque has small left and right buffers, each holding one to four items, and a recursively structured middle. An ordinary push grows an end buffer. When that buffer is full, the operation leaves items at the end and moves a group of three into the middle. That middle is itself a deque, but of grouped items rather than individual items. Its buffers can overflow in turn, making the structure deeper only where necessary. At successive levels, each buffered group represents more original items, so the tree deepens slowly. section 3.3 section 3.4
Figure 3.5 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.
Follow the arrows from the root after an overflow reaches a third level: the edges remain shallow while the middle gains depth. section 3.4
The payoff is persistence without a linear-time worst case for end operations. Most operations cost O(1) on average; operations that must reach deeper into the tree cost O(log n) time and extra memory in the worst case. Implementing the one- through four-item buffers as explicit cases keeps the small boundary problem manageable, while recursive generic types express the larger deque safely in C#. section 3.10 section 3.0
Concatenation shows why the grouping invariant matters. Copying one deque into another by repeated pushes takes linear time. Instead, adjoining end buffers can be repacked into groups of two or three and placed in the middle; concatenation then recurses on the smaller middle deques. Allowing both two- and three-item groups is the deliberate relaxation that makes genuinely sublinear concatenation possible, rather than merely deferring a linear copy. section 3.7 section 3.0
Listing 3.7 Implementing concatenation of multiple-item deques
public sealed class Deque<T> : IDeque<T>
{
[…]
public IDeque<T> Concatenate(IDeque<T> items) =>
right is Deque<T> r ?
new Deque<T>(
left,
middle.PushRightMany(right.TwosAndThrees(r.left))
.Concatenate(r.middle),
r.right) :
this.PushRightMany(items);
}
static class Extensions
{
public static IDeque<T> PushRightMany<T>(
this IDeque<T> deque, IEnumerable<T> items) =>
items.Aggregate(deque, (d, item) => d.PushRight(item));
}
The C# implementation packs the adjoining buffers, then calls Concatenate on the middle deques; the trivial case pushes items directly. section 3.7
More generally, a finger tree reorganizes a tree around chosen fingers: work near a finger has amortized cost proportional to the logarithm of its distance from that finger. End fingers suit a deque because access to its middle is less important. Size tracking and splitting could extend this design toward other persistent structures, such as priority queues and interval trees; those extensions are separate from the deque implementation here. section 3.9
