A representation for linear lists with movable fingers

Mark R. Brown, Robert E. Tarjan

Research output: Contribution to journalConference article

2 Scopus citations

Abstract

This paper describes a data structure which is useful for representing linear lists when the pattern of accesses to a list exhibits a (perhaps time-varying) locality of reference. The structure has many of the properties of the representation proposed by Guibas, McCreight, Plass, and Roberts [4], but is substantially simpler and may be practical for lists of moderate size. The analysis of our structure includes a general treatment of the worst-case node splitting caused by consecutive insertions into a 2-3 tree.

Original languageEnglish (US)
Pages (from-to)19-29
Number of pages11
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - May 1 1978
Externally publishedYes
Event10th Annual ACM Symposium on Theory of Computing, STOC 1978 - San Diego, United States
Duration: May 1 1978May 3 1978

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'A representation for linear lists with movable fingers'. Together they form a unique fingerprint.

  • Cite this