REPRESENTATION FOR LINEAR LISTS WITH MOVABLE FINGERS.

Mark R. Brown; Robert E. Tarjan

REPRESENTATION FOR LINEAR LISTS WITH MOVABLE FINGERS.

Research output: Contribution to conference › Paper › peer-review

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 language	English (US)
Pages	19-29
Number of pages	11
State	Published - 1978
Event	Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp - San Diego, CA, USA Duration: May 1 1978 → May 3 1978

Other

Other	Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp
City	San Diego, CA, USA
Period	5/1/78 → 5/3/78

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@conference{4955a15891a44691b5a39290144dcdd3,

title = "REPRESENTATION FOR LINEAR LISTS WITH MOVABLE FINGERS.",

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

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

year = "1978",

language = "English (US)",

pages = "19--29",

note = "Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp ; Conference date: 01-05-1978 Through 03-05-1978",

}

TY - CONF

T1 - REPRESENTATION FOR LINEAR LISTS WITH MOVABLE FINGERS.

AU - Brown, Mark R.

AU - Tarjan, Robert E.

PY - 1978

Y1 - 1978

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

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

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

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

M3 - Paper

AN - SCOPUS:0018054426

SP - 19

EP - 29

T2 - Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp

Y2 - 1 May 1978 through 3 May 1978

ER -

REPRESENTATION FOR LINEAR LISTS WITH MOVABLE FINGERS.

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this