REPRESENTATION FOR LINEAR LISTS WITH MOVABLE FINGERS.

Mark R. Brown, Robert E. Tarjan

Research output: Contribution to conferencePaper

11 Scopus citations

Abstract

A data structure is described 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 L. J. Guibas et al. , but is substantially simpler and may be practical for lists of moderate size. The analysis of this structure includes a general treatment of the worst-case node splitting caused by consecutive insertions into a 2-3 tree.

Original languageEnglish (US)
Pages19-29
Number of pages11
StatePublished - Jan 1 1978
EventConf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp - San Diego, CA, USA
Duration: May 1 1978May 3 1978

Other

OtherConf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp
CitySan Diego, CA, USA
Period5/1/785/3/78

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'REPRESENTATION FOR LINEAR LISTS WITH MOVABLE FINGERS.'. Together they form a unique fingerprint.

  • Cite this

    Brown, M. R., & Tarjan, R. E. (1978). REPRESENTATION FOR LINEAR LISTS WITH MOVABLE FINGERS.. 19-29. Paper presented at Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp, San Diego, CA, USA, .