Simple confluently persistent catenable lists

Haim Kaplan, Chris Okasaki, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive - each operation produces a new list incorporating the change, while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues (deques) with catenation that supports all deque operations in constant amortized time. Our implementation is functional if we allow memoization.

Original languageEnglish (US)
Pages (from-to)965-977
Number of pages13
JournalSIAM Journal on Computing
Issue number3
StatePublished - 2000

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


  • Data structures
  • Double-ended queue (deque)
  • Functional programming
  • Memoization
  • Persistent data structures
  • Queue
  • Stack
  • Stack-ended queue (steque)


Dive into the research topics of 'Simple confluently persistent catenable lists'. Together they form a unique fingerprint.

Cite this