▼Data:   Data Structures
On this page:
make-skip-list
make-adjustable-skip-list
skip-list?
adjustable-skip-list?
skip-list-ref
skip-list-set!
skip-list-remove!
skip-list-count
skip-list-remove-range!
skip-list-contract!
skip-list-expand!
skip-list-iterate-first
skip-list-iterate-next
skip-list-iterate-key
skip-list-iterate-value
skip-list-iterate-least/  >?
skip-list-iterate-least/  >=?
skip-list-iterate-greatest/  <?
skip-list-iterate-greatest/  <=?
skip-list-iterate-least
skip-list-iterate-greatest
skip-list-iter?
skip-list-iter-valid?
skip-list->list
6.5
  top  ← prev  up  next → 

5 Skip Lists

Ryan Culpepper <ryanc@racket-lang.org>

 (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
Makes a new empty skip-list. The skip-list uses ord to order keys; in addition, the domain contract of ord is combined with key-contract to check keys.

Examples:
> (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
Makes a new empty skip-list that permits only exact integers as keys (in addition to any constraints imposed by key-contract). The resulting skip-list answers true to adjustable-skip-list? and supports efficient key adjustment; see skip-list-contract! and skip-list-expand!.

procedure

(skip-list? v) → boolean?

  v : any/c
Returns #t if v is a skip-list, #f otherwise.

procedure

(adjustable-skip-list? v) → boolean?

  v : any/c
Returns #t if v is a skip-list that supports key adjustment; see skip-list-contract! and skip-list-expand!.

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?
Implementations of dict-ref, dict-set!, dict-remove!, and dict-count, respectively.

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
Removes all keys in [from, to); that is, all keys greater than or equal to from and less than to.

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?
Like skip-list-remove-range!, but also decreases the value of all keys greater than or equal to to by (- to from).

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?
Increases each key greater than or equal to from by (- to from).

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?
Implementations of dict-iterate-first, dict-iterate-next, dict-iterate-key, and dict-iterate-value, respectively.

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?
Implementations of dict-iterate-least/>?, dict-iterate-least/>=?, dict-iterate-greatest/<?, dict-iterate-greatest/<=?, dict-iterate-least, and dict-iterate-greatest, respectively.

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
Returns #t if v represents a position in a skip-list, #f otherwise.

procedure

(skip-list-iter-valid? iter) → boolean?

  iter : skip-list-iter?
Returns #t if the iterator is valid, or #f if invalidated by deletion; see skip-list-iterate-first for details about invalidation.

procedure

(skip-list->list skip-list) → (listof pair?)

  skip-list : skip-list?
Returns an association list with the keys and values of skip-list, in order.

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

  top  ← prev  up  next →