TY - JOUR
T1 - A representation for linear lists with movable fingers
AU - Brown, Mark R.
AU - Tarjan, Robert E.
N1 - Funding Information:
*-/ This research was supported in part by National Science Foundation grant MCS75-22870 and by Office of Naval Research contract NOOO14-76-C-O688.
Funding Information:
This research was supported in part by National Science Foundation grant MCS75-22870 and by Office of Naval Research contract N00014-76-C-0688.
Publisher Copyright:
© 1978 Association for Computing Machinery. All rights reserved.
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 -