Deterministic skip list

Back to Data structures

The deterministic skip list is a data structure which implements a dynamic ordered dictionary. From now on we shall abbreviate the deterministic skip list as a skip list. The truncated skip list is a skip list in which the height of the skip list is bounded from above by a constant.

Properties

Let be the number of stored elements, be the number of unique stored elements, and be the link-distance, along unique elements, between a given stored element and the searched element. Let be the maximum height of the skip-list. The implementation of the deterministic skip-list in Pastel has the following properties:

Property Complexity
Insert/remove an element.
Find the next/previous/equal element for a key.
Find the next/previous element, given an element.
Count the number of equivalent elements.
Space

Additional properties are as follows:

References

The probabilistic skip-list was introduced in

Skip Lists: A Probabilistic Alternative to Balanced Trees, W. Pugh, Communications of the ACM, vol. 33, no. 6, June 1990, pp. 668-676.

The deterministic skip-list was introduced in

Deterministic Skip Lists, J. Ian Munro, Thomas Papadakis, Robert Sedgewick, Proceedings of the ACM-SIAM Third Annual Symposium on Discrete Algorithms, January 1992.

Learn more

Files

Deterministic skip list

Skip list concepts

Skip list iterator

Skip list node

Skip-list element insertion

Skip-list element removal

Skiplist module

Testing for skip lists.