Deterministic skip lists

J. Ian Munrot, Thomas Papadakis, Robert Sedgewick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Scopus citations

Abstract

We explore techniques based on the notion of a skip list to guarantee logarithmic search, insert and delete costs. The basic idea is to insist that between any pair of elements above a given height are a small number of elements of precisely that height. The desired behaviour can be achieved by either using some extra space for pointers, or by adding the constraint that the physical sizes of the nodes be exponentially increasing. The first approach leads to simpler code, whereas the second is ideally suited to a buddy system of memory allocation. Our techniques are competitive in terms of time and space with balanced tree schemes, and, we feel, inherently simpler when taken from first principles.

Original languageEnglish (US)
Title of host publicationProceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
PublisherAssociation for Computing Machinery
Pages367-375
Number of pages9
ISBN (Electronic)089791466X
StatePublished - Sep 1 1992
Event3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992 - Orlando, United States
Duration: Jan 27 1992Jan 29 1992

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
VolumePart F129721

Other

Other3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
CountryUnited States
CityOrlando
Period1/27/921/29/92

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Deterministic skip lists'. Together they form a unique fingerprint.

Cite this