Simple confluently persistent catenable lists

Haim Kaplan, Chris Okasaki, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 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 with catenation that supports all deque operations in constant amortized time.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsStefan Arnborg, Lars Ivansson
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540646825, 9783540646822
StatePublished - 1998
Event6th Scandinavian Workshop on Algorithm Theory, SWAT 1998 - Stockholm, Sweden
Duration: Jul 8 1998Jul 10 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th Scandinavian Workshop on Algorithm Theory, SWAT 1998

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this