A representation for linear lists with movable fingers

Mark R. Brown; Robert E. Tarjan

doi:10.1145/800133.804328

A representation for linear lists with movable fingers

Mark R. Brown, Robert E. Tarjan

Research output: Contribution to journal › Conference article › peer-review

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 language	English (US)
Pages (from-to)	19-29
Number of pages	11
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/800133.804328
State	Published - May 1 1978
Externally published	Yes
Event	10th Annual ACM Symposium on Theory of Computing, STOC 1978 - San Diego, United States Duration: May 1 1978 → May 3 1978

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/800133.804328

Cite this

@article{3fee9004262b4ef69a3102ca38154e28,

title = "A representation for linear lists with movable fingers",

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.",

author = "Brown, {Mark R.} and Tarjan, {Robert E.}",

note = "Publisher Copyright: {\textcopyright} 1978 Association for Computing Machinery. All rights reserved.; 10th Annual ACM Symposium on Theory of Computing, STOC 1978 ; Conference date: 01-05-1978 Through 03-05-1978",

year = "1978",

month = may,

day = "1",

doi = "10.1145/800133.804328",

language = "English (US)",

pages = "19--29",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - A representation for linear lists with movable fingers

AU - Brown, Mark R.

AU - Tarjan, Robert E.

PY - 1978/5/1

Y1 - 1978/5/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85034645994&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034645994&partnerID=8YFLogxK

U2 - 10.1145/800133.804328

DO - 10.1145/800133.804328

M3 - Conference article

AN - SCOPUS:85034645994

SN - 0737-8017

SP - 19

EP - 29

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 10th Annual ACM Symposium on Theory of Computing, STOC 1978

Y2 - 1 May 1978 through 3 May 1978

ER -

A representation for linear lists with movable fingers

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this