Deterministic skip lists

J. Ian Munrot, Thomas Papadakis, Robert Sedgewick

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

65 Scopus citations


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


Other3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


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

Cite this