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.
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:
void type can be used, and no memory will be used for the associated data. While normally an iterator dereferences to the associated data, with a void type an iterator dereferences to the key,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.