Skip Lists are Fascinating

<p><pre><code> for (int R = _rand.Next(); (R &#38; 1) == 1; R &#62;&#62;= 1) </code></pre> For C# on .NET, this may work fine, but in general, this is a bad way of extracting a 0/1 choice from a pseudo-random number generator (PRNG). Many PRNGs use linear congruential generators, which are just a multiply and an add, and have highly predictable low bits as a result (frequently just a repeating pattern with a short period, as short as 4 or 8).<p>Safer:<p><pre><code> while (_rand.Next(2) == 0) </code></pre> - or even simply reading the bits off the other end.<p>Another nice thing about skip lists is that they are relatively easy to make into cheap persistent structures (aka functional structures), that is, structures where operations return a new immutable copy of the structure, but share most of the substructure with the previous version.

They are indeed fascinating, and Erik Demaine's MIT OCW lecture on it is amazing [1]. The analogy between the NYC subway system (express and local trains) and skip lists is brilliant.<p>[1] <a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-12-skip-lists" rel="nofollow">http://ocw.mit.edu/courses/electrical-engineering-and-comput...</a>

I don't find skip lists to be simpler than AVL trees, but it's my understanding I'm in the minority on this issue.<p>What I do find very interesting about skip lists is that they support fingers - pointers to locations in the structure that allow fast modification nearby. As a very simple example, prepending an item to a skip list (this cons) is O(1) expected.<p>Getting this property for AVL or red-black trees is possible, but much more difficult, and requires fundamental changes to the structural invariants and representations.<p>For more on the uses of finger search, see:<p><a href="http://www.cs.au.dk/~gerth/pub/finger05.html" rel="nofollow">http://www.cs.au.dk/~gerth/pub/finger05.html</a>

They are very interesting but in practice often preform poorly due to the cpu not being able to figure out what to cache.

I think the original paper is very readable: ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

i've always preferred treaps to skiplists as far as probabilistic data structures are concerned. that could be partially due to the fact that i felt aragon and seidel's paper on treaps to be fundamentally better that pugh's paper on skiplists, which i recall being kind of hand-wavy with respect to the analysis.<p>i've had to implement both and replace many of the java collections interfaces with them as the backing store for various projects or coursework. i find the structure of the skiplists intricate and fascinating as a thought experiment, but i feel they difficult for certain things, like implementing an iterator over them. treaps, if i recall correctly, just use the normal BST traversals.<p>would be curious to hear comparisons on the two, being probably the most popular of the probabilistic data structures.<p>performance wise, i've found both to have their strengths and weaknesses under various load testing scenarios. i have some stats around here somewhere.<p>of course the downside with any probabilistic data structure is that you're counting on the amortized bounds, but could end up with the absolute worst case performance at times. there are so many well-documented and well-implemented libraries out there for red-black trees (the gold standard in my opinion) that it's hard to find compelling reasons besides curiosity to use them in practice.<p>the original papers for both of them are here (treaps):<p><a href="http://faculty.washington.edu/aragon/pubs/rst89.pdf" rel="nofollow">http://faculty.washington.edu/aragon/pubs/rst89.pdf</a><p>and here (skiplists) :<p>ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

IIRC, Redis uses skip lists in its implementation of sorted sets. Good rundown of the data structure.

An interesting supplemental reading is the "two bowling balls" interview puzzle -- <a href="http://20bits.com/articles/interview-questions-two-bowling-balls/" rel="nofollow">http://20bits.com/articles/interview-questions-two-bowling-b...</a><p>It's essentially a 2 level skip list (but could be generalized where you get one extra level per bowling ball), and brings out some basic calculus to optimize lookup performance even further.

The creator of Io created a kv db based on skip lists called skipdb that is worth a look.