Finger Tree!
A persistent, purely functional workhorse. Amortized O(1) access at both ends, O(log n) concatenation/splitting.
It generalizes elegantly to build sequences, priority queues, and more. Powers Haskell's main Data.Sequence. A functional programmer's secret weapon.
@Vorpal
Totally fair point, thanks for calling that out.
When I mentioned finger trees I was thinking more about the *functional* side (persistence, elegant composition, Haskell/Data.Sequence style usage) than raw performance on real hardware.
In performance‑critical code your argument for cache‑friendly linear structures and wide trees absolutely makes sense, and I appreciate the reminder to think about actual access patterns and hardware effects, not just asymptotic complexity.