"I have a mind like a steel... uh... thingy." Patrick Logan's weblog.

Search This Blog

Wednesday, October 08, 2003

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.

No comments:

Blog Archive

About Me

Portland, Oregon, United States
I'm usually writing from my favorite location on the planet, the pacific northwest of the u.s. I write for myself only and unless otherwise specified my posts here should not be taken as representing an official position of my employer. Contact me at my gee mail account, username patrickdlogan.