5 Skip Lists🔗ℹ

Skip-lists are a simple, efficient data structure for mutable dictionaries with totally ordered keys. They were described in the paper “Skip Lists: A Probabilistic Alternative to Balanced Trees” by William Pugh in Communications of the ACM, June 1990, 33(6) pp668-676.

A skip-list is an ordered dictionary (dict? and ordered-dict?). It also supports extensions of the dictionary interface for iterator-based search and mutation.

Operations on skip-lists are not thread-safe. If a key in a skip-list is mutated, the skip-list’s internal invariants may be violated, causings its behavior to become unpredictable.

Time complexities are given for many of the operations below. With a few exceptions, the time complexities below are probabilistic and assume that key comparison is constant-time. N refers to the number of elements in the skip-list.

The skip-list-ref, skip-list-set!, and skip-list-remove! operations take O(log N) time. The skip-list-count operation takes constant time.

This operation takes probabilistic O(log N) time.

This operation takes probabilistic O(log N) time.

This operation takes probabilistic O(log N) time.

A skip-list iterator is invalidated if the entry it points to is deleted from the skip-list (even if another entry is later inserted with the same key). The skip-list-iterate-key and skip-list-iterate-value operations raise an exception when called on an invalidated iterator, but skip-list-iterate-next advances to the next undeleted entry that was visible to iter when it was valid.

These operations take constant time.

See notes on iterators at skip-list-iterate-first.

The skip-list-iterate-least operation takes constant time; the rest take O(log N) time.

This operation takes O(N) time, where N is the number of entries in the skip-list.