Skip Lists

Monday, October 13, 2003, 8:21 p.m.

Patrick Logan posted a link to Bill Pugh's Skip List Cookbook. I think they're great data structures, too.

A skip list is a probabilistic alternative to balanced tree. In its most basic form, it is easy to implement. The list contains nodes with a value and varying numbers of forward links; the number of links determines the size. The nodes are in sorted order and each node of size n has links to the next nodes of size 1 through n.

Practical implementations of skip lists can get more complicated. Josh MacDonald and Ben Zhao did a nice comparison of skiplists and b+-trees for a class project. They implemented a deterministic variant of the skip list (see J. Ian Munro, Thomas Papadakis, and Robert Sedgewick. Deterministic skip lists. In Proceedings of the third annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1992) and found the performance competitive and the implementation simpler.

The Chord algorithm for doing lookups in a peer-to-peer distributed hash table has some high-level similarities to a skip list. The problem is to locate a node in the network given a key. The nodes are arranged in a ring, and each node maintains a finger table that points to other nodes at various distances around the ring (increasing powers of two). The finger table is a bit like the table of forward pointers in a skip list, although each node in a Chord rind has the same number of forward pointers.

James Aspnes and Gauri Shah presented a paper at SODA '03 on skip graphs. I haven't read it yet, but it sounds interesting. A skip graph extend the distributed hash table algorithm with operations based on the ordering of the keys. Apparently a similar data structure is used in SkipNet.