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 , 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)|
|Number of pages||11|
|Journal||Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - May 1 1978|
|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