Simple confluently persistent catenable lists

Haim Kaplan, Chris Okasaki, Robert Endre Tarjan

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

3 Scopus citations

Abstract

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
Pages119-130
Number of pages12
ISBN (Print)3540646825, 9783540646822
DOIs
StatePublished - Jan 1 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)
Volume1432
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th Scandinavian Workshop on Algorithm Theory, SWAT 1998
CountrySweden
CityStockholm
Period7/8/987/10/98

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this