A Skip List Cookbook
William Pugh, Department of Computer Science
and Institute for Advanced Computer Studies,
University of Maryland, College Park
Overview
Skip lists are a probabilistic list-based data structure that are a
simple and efficient substitute for balanced trees. Probabilistic
balancing also can be used for tree based data structures. Previously,
we showed how skip lists could be used to implement a dictionary
abstract data type (i.e., implement search, insertion and deletion). In
this paper, we show that skip lists are as versatile as balanced trees.
We describe and analyze algorithms to:
* use search fingers so that searching for an element k away from the
last element searched for takes O(log k) expected time,
* merge, split and concatenate skip lists, and
* implement linear list operations using skip lists (e.g., "insert this
after the kth element of the list").
These operations have been described for balanced trees. However, the
skip list versions of these algorithms are simpler and at least as fast,
and often cannot be easily adapted directly from the balanced trees
algorithms. The analysis techniques required for the skip list versions
are radically different from the techniques used to analyze their
balanced tree cousins.
The merge algorithm we describe has better asymptotic time
complexity than any previously described merge algorithm (such as Brown
and Tarjan's). This claim may seem ludicrous, since the O(m + m log n/m)
upper bound of Brown and Tarjan was proven to be a lower bound. But that
lower bound only holds for the worst-case input (uniformly distributed
merges). Our algorithm is optimal for all inputs. If two data structures
simply need to be concatenated, our algorithm runs in O(log n) expected
time, while that of Brown and Tarjan runs in O(m + log n) time. Of
course, there are algorithms that concatenate two balanced trees in
O(log n) time. However, our algorithm optimally handles both uniformly
distributed merges and concatenation, as well as everything in between.
Our strategy for merging skip lists can be applied to balanced trees,
providing merge algorithms for balanced trees that are optimal for all
inputs (although the algorithms would be prohibitively complicated).
We also describe and analyze variations that noticeably simplify or
improve skip list algorithms.
This paper will appear in Distributed Computer. It is also available as
Tech Report CSPTRP2286.1, Dept. of Computer Science, University of
Maryland, College Park, July 1989. A Postscript format version of this
paper is available for anonymous ftp from mimsy.cs.umd.edu.
The author can be contacted at pugh@cs.umd.edu.