5 Skip Lists
| (require data/skip-list) | package: data-lib |
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.
procedure
(make-skip-list [ ord #:key-contract key-contract #:value-contract value-contract]) → skip-list? ord : order? = datum-order key-contract : contract? = any/c value-contract : contract? = any/c
> (define skip-list (make-skip-list real-order)) > (skip-list-set! skip-list 3 'apple) > (skip-list-set! skip-list 6 'cherry) > (dict-map skip-list list) '((3 apple) (6 cherry))
> (skip-list-ref skip-list 3) 'apple
> (skip-list-remove! skip-list 6) > (skip-list-count skip-list) 1
procedure
(make-adjustable-skip-list [ #:key-contract key-contract #:value-contract value-contract]) → adjustable-skip-list? key-contract : contract? = any/c value-contract : contract? = any/c
procedure
(skip-list? v) → boolean?
v : any/c
procedure
v : any/c
procedure
(skip-list-ref skip-list key [default]) → any/c
skip-list : skip-list? key : any/c default : any/c = (lambda () (error ....))
procedure
(skip-list-set! skip-list key value) → void?
skip-list : skip-list? key : any/c value : any/c
procedure
(skip-list-remove! skip-list key) → void?
skip-list : skip-list? key : any/c
procedure
(skip-list-count skip-list) → exact-nonnegative-integer?
skip-list : 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.
procedure
(skip-list-remove-range! skip-list from to) → void?
skip-list : skip-list? from : any/c to : any/c
This operation takes probabilistic O(log N) time.
procedure
(skip-list-contract! skip-list from to) → void?
skip-list : adjustable-skip-list? from : exact-integer? to : exact-integer?
This operation takes probabilistic O(log N) time.
procedure
(skip-list-expand! skip-list from to) → void?
skip-list : adjustable-skip-list? from : exact-integer? to : exact-integer?
This operation takes probabilistic O(log N) time.
procedure
(skip-list-iterate-first skip-list) → (or/c skip-list-iter? #f)
skip-list : skip-list?
procedure
(skip-list-iterate-next skip-list iter)
→ (or/c skip-list-iter? #f) skip-list : skip-list? iter : skip-list-iter?
procedure
(skip-list-iterate-key skip-list iter) → any/c
skip-list : skip-list? iter : skip-list-iter?
procedure
(skip-list-iterate-value skip-list iter) → any/c
skip-list : skip-list? iter : skip-list-iter?
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.
procedure
(skip-list-iterate-least/>? skip-list key)
→ (or/c skip-list-iter? #f) skip-list : skip-list? key : any/c
procedure
(skip-list-iterate-least/>=? skip-list key)
→ (or/c skip-list-iter? #f) skip-list : skip-list? key : any/c
procedure
(skip-list-iterate-greatest/<? skip-list key) → (or/c skip-list-iter? #f) skip-list : skip-list? key : any/c
procedure
(skip-list-iterate-greatest/<=? skip-list key) → (or/c skip-list-iter? #f) skip-list : skip-list? key : any/c
procedure
(skip-list-iterate-least skip-list) → (or/c skip-list-iter? #f)
skip-list : skip-list?
procedure
(skip-list-iterate-greatest skip-list)
→ (or/c skip-list-iter? #f) skip-list : skip-list?
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.
procedure
(skip-list-iter? v) → boolean?
v : any/c
procedure
(skip-list-iter-valid? iter) → boolean?
iter : skip-list-iter?
procedure
(skip-list->list skip-list) → (listof pair?)
skip-list : skip-list?
This operation takes O(N) time, where N is the number of entries in the skip-list.