Fully Persistent Lists with Catenation

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

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

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)
Volume41
Issue number5
DOIs
StatePublished - Jan 9 1994

All Science Journal Classification (ASJC) codes

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

Keywords

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

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

  • Cite this