Skip Lists -- ever used them? [closed]

Question

I'm wondering whether anyone here has ever used a skip list. It looks to have roughly the same advantages as a balanced binary tree but is simpler to implement. If you have, did you write your own, or use a pre-written library (and if so, what was its name)?

Answer 1

My understanding is that they're not so much a useful alternative to binary trees (e.g. red-black trees) as they are to B-trees for database use, so that you can keep the # of levels down to a feasible minimum and deal w/ base-K logs rather than base-2 logs for performance characteristics. The algorithms for probabilistic skip-lists are (IMHO) easier to get right than the corresponding B-tree algorithms. Plus there's some literature on lock-free skip lists. I looked at using them a few months ago but then abandoned the effort on discovering the HDF5 library.

literature on the subject:

Papers by Bill Pugh:

• A skip list cookbook
• Skip lists: A probabilistic alternative to balanced trees
• Concurrent Maintenance of Skip Lists

non-academic papers/tutorials:

• Eternally Confuzzled (has some discussion on several data structures)
• "Skip Lists" by Thomas A. Anastasio

Answer 2

Actually, for one of my projects, I am implementing my own full STL. And I used a skiplist to implement my std::map. The reason I went with it is that it is a simple algorithm which is very close to the performance of a balanced tree but has much simpler iteration capabilities.

Also, Qt4's QMap was a skiplist as well which was the original inspiration for my using it in my std::map.