Article

Free access

A new representation for linear lists

Authors:

Leo J. Guibas,

Edward M. McCreight,

Michael F. Plass,

Janet R. RobertsAuthors Info & Claims

STOC '77: Proceedings of the ninth annual ACM symposium on Theory of computing

Pages 49 - 60

https://doi.org/10.1145/800105.803395

Published: 04 May 1977 Publication History

PDF eReader

Abstract

We present a new data structure for maintaining a set of records in a linear list according to their key values. This data structure has the property that we can keep a number of fingers at points of interest in the key space (e.g., the beginning or the end of the list), so that access and modification in the neighborhood of a finger is very efficient.

In the Section 2 we discuss the general structure of our B-tree. Since we propose to search the tree from a leaf upwards, additional links need to be introduced. In Section 3 we show how to obtain our result for the case of one finger. A key idea is the construction of a number representation behaving as described above, which we can use to model the propagation of modifications in the B-tree along the finger path. In Section 4 we generalize the structure so that several fingers in the key space can be maintained, with the advantage that access is cheap in the neighborhood of each finger. Finally in Section 5 we present some implementation notes and applications, mostly to sorting.

References

[1]

R. Bayer and E. McCreight, "Organization and Maintainance of Large Ordered Indexes", Acta Informatica 1 (1972), 173-189

Digital Library

Google Scholar

[2]

J. Bitner, G. Ehrlich, and E. Reingold, "Efficient Generation of Binary Reflected Gray Code and Its Applications", CACM, 19, (1976), 517-521

Digital Library

Google Scholar

[3]

M. Fredman, "Sorting X + Y and Building Balanced Search Trees", Proc. 7-th Ann. ACM Symp. Theor. Comp (1975), 240-244

Digital Library

Google Scholar

[4]

D. Knuth, The Art of Computer Programming, vol. III, Sorting and Searching, Addison-Wesley (1975)

Digital Library

Google Scholar

[5]

D. Knuth, Unpublished CS204 Lecture Notes, Stanford University, 1976. (See also The State of the Art of Computer Programming, STAN-CS-76-551, 292 and 358).

Digital Library

Google Scholar

[6]

N. Wirth, Algorithms + Data Structures &equil; Programs, Prentice Hall (1975), 246-257

Digital Library

Google Scholar

[7]

H. Rademacher, "On the Partition Function p(n)", Proc. London Math. Soc. 43, 241-254

Google Scholar

Cited By

View all

Bai XCoester COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Sorting with predictionsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667277(26563-26584)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667277
Moine ACharguéraud APottier FPopescu AZdancewic S(2022)Specification and verification of a transient stackProceedings of the 11th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3497775.3503677(82-99)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1145/3497775.3503677
Nekrich YKhuller SVassilevska Williams V(2021)Dynamic planar point location in optimal timeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451100(1003-1014)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451100
Show More Cited By

Index Terms

A new representation for linear lists

Recommendations

A representation for linear lists with movable fingers
STOC '78: Proceedings of the tenth annual ACM symposium on Theory of computing

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 ...
A new data structure for representing sorted lists

In this paper we explore the use of weak B -trees to represent sorted lists. In weak B -trees each node has at least a and at most b sons where 2 a b . We analyse the worst case cost of sequences of insertions and deletions in weak B -trees. ...
Hands-free Selection in Scroll Lists for AR Devices
MuC '24: Proceedings of Mensch und Computer 2024

While desktops and smartphones have established user interface standards, they are still lacking for virtual and augmented reality devices. Hands-free interaction for these devices is desirable. This paper explores utilizing eye and head tracking for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '77: Proceedings of the ninth annual ACM symposium on Theory of computing

May 1977

318 pages

ISBN:9781450374095

DOI:10.1145/800105

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1977

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

STOC '77 Paper Acceptance Rate 31 of 87 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

94
Total Citations
View Citations
1,059
Total Downloads

Downloads (Last 12 months)111
Downloads (Last 6 weeks)12

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bai XCoester COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Sorting with predictionsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667277(26563-26584)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667277
Moine ACharguéraud APottier FPopescu AZdancewic S(2022)Specification and verification of a transient stackProceedings of the 11th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3497775.3503677(82-99)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1145/3497775.3503677
Nekrich YKhuller SVassilevska Williams V(2021)Dynamic planar point location in optimal timeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451100(1003-1014)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451100
Elmasry AKatajainen J(2021)Regular numeral systems for data structuresActa Informatica10.1007/s00236-021-00407-959:2-3(245-281)Online publication date: 25-Jul-2021
https://doi.org/10.1007/s00236-021-00407-9
Nipkow TEberl MHaslbeck M(2020)Verified Textbook AlgorithmsAutomated Technology for Verification and Analysis10.1007/978-3-030-59152-6_2(25-53)Online publication date: 12-Oct-2020
https://doi.org/10.1007/978-3-030-59152-6_2
Tangwongsan KHirzel MSchneider S(2019)Optimal and general out-of-order sliding-window aggregationProceedings of the VLDB Endowment10.14778/3339490.333949912:10(1167-1180)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.14778/3339490.3339499
Elmasry AKahla MAhdy FHashem M(2019)Red---black trees with constant update timeActa Informatica10.1007/s00236-019-00335-956:5(391-404)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00236-019-00335-9
Bille PChristiansen ACording PGØrtz I(2018)Finger Search in Grammar-Compressed StringsTheory of Computing Systems10.1007/s00224-017-9839-962:8(1715-1735)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s00224-017-9839-9
Kaler THe YElnikety SScheideler CHajiaghayi M(2017)Optimal Reissue Policies for Reducing Tail LatencyProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3087556.3087566(195-206)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3087556.3087566
Elmasry A(2015)Counting inversions adaptivelyInformation Processing Letters10.5555/2793734.2794048115:10(769-772)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.5555/2793734.2794048
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A representation for linear lists with movable fingers

A new data structure for representing sorted lists

Hands-free Selection in Scroll Lists for AR Devices