There are a number of purely functional deques that support $O(1)$ operations at each end. None that I know of are "uniquely represented" - deques with the same number of items can have different shapes.

In the imperative case, doubly-linked lists are uniquely represented deques with constant-time operations.

Hoogerwoord, in "A Logarithmic Implementation of Flexible Arrays", showed that Braun trees have logarithmic deque operations, and they are purely functional and uniquely represented.

Is there a deterministic uniquely represented purely functional deque with $o(\log n)$ operations?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.