Skip Lists -- ever used them?

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

I implemented a variant that I termed a Reverse Skip List for a rules engine a few years ago. Much the same, but the reference links run backwards from the last element.

This is because it was faster for inserting sorted items that were most likely to towards the back-end of the collection.

It was written in C# and took a few iterations to get working successfully.

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 because 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 is a skiplist as well which was the original inspiration for my using it in my std::map.

Answer 3

Years ago I implemented my own for a probabilistic algorithms class. I'm not aware of any library implementations, but it's been a long time. It is pretty simple to implement. As I recall they had some really nice properties for large data sets and avoided some of the problems of rebalancing. I think the implementation is also simpler than binary tries in general. There is a nice discussion and some sample c++ code here:

http://www.ddj.us/cpp/184403579?pgno=1

There's also an applet with a running demonstration. Cute 90's Java shininess here:

http://www.geocities.com/siliconvalley/network/1854/skiplist.html

Answer 4

Java 1.6 (Java SE 6) introduced ConcurrentSkipListSet and ConcurrentSkipListMap to the collections framework. So, I'd speculate that someone out there is really using them.

Skiplists tend to offer far less contention for locks in a multithreaded situation, and (probabilistically) have performance characteristics similar to trees.

See the original paper [pdf] by William Pugh

Answer 5

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