Fully Persistent Lists with Catenation

James R. Driscoll, Daniel D.K. Sleator, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O1994 time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.

Original languageEnglish (US)
Pages (from-to)943-959
Number of pages17
JournalJournal of the ACM (JACM)
Issue number5
StatePublished - Jan 9 1994

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • LISP
  • amortization
  • catenation
  • concatenation
  • data structures
  • functional programming
  • list
  • queue
  • stack


Dive into the research topics of 'Fully Persistent Lists with Catenation'. Together they form a unique fingerprint.

Cite this