data.deque

data.deque is a persistent deque for Clojure(Script). Deque(double-ended queue) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front or back.

The implementation of data.deque is based on a slightly modified version of Finger tree. It gives O(1) access to both ends and amortized O(1) for immutable insertion/deletion.

Example

(require '[data.deque :refer [deque]])

;; create an empty deque with `(deque)` or
(def dl (deque 5 4 3 2 1))

(peek-first dl)
;=> 1

(peek-last dl)
;=> 5

(-> dl
    (add-first 0)
    (add-last 6)
    seq)
;=> (0 1 2 3 4 5 6)

(-> dl
    (remove-first)
    (remove-last)
    seq)
;=> (1 2 3)

Differences from core.data.finger-tree

• ClojureScript support
• Better performance
• No unnecessary features for deque
  • Trees are not concatable / splittable
  • No measuring interfaces

Benchmark

Why Finger Tree?

Banker's Deque is also a purely functional data structure that guarantee amortized constant time but performs worse due to reverse operation. Real-Time Deque eliminates amortization by "Lazy Rebuilding" technique, but it also has some overhead due to its laziness. Finger Tree provides a balanced framework for building deque in terms of both time and space complexity.

Reference

• Ralf Hinze and Ross Paterson. Finger trees: a simple general-purpose data structure
• Chris Okasaki. Purely Functional Data Structures
• Haim Kaplan and Robert E. Tarjan. Purely Functional, Real-Time Deques with Catenation