Skiplist Cookbook

The skiplist is my favorite data structure (PDF). So simple and efficient.

I have implemented it several times in Smalltalk, Java, and Scheme. The linked cookbook is very straightforward, but even without it, the concept is what allows the implementation this quality.

The idea begins with a linked list. But each node may have more than one forwarding pointer. The number of pointers in a node is based on a random number and they form a tree shape. So you end up with easy code to write for searches, adds, and deletes, but you also end up with tree shaped performance, i.e. O(log n).

Moreover since the tree shape is based on a random number instead of the data in the nodes, there is no need to "rebalance" the tree on adds or deletes.

The paper does a good job of illustrating this concept and has all the source, so I won't even try to cover the details.