Skip Lists -- ever used them?

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)?

From stackoverflow

• 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.

  oɔɯǝɹ : Couldn't you invert the comparison for the type, and use a standard skiplist to achieve the same result?

• 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.

  : Evan, have you made your skiplist code available anywhere? Thanks

  Evan Teran : not quite yet, but things are almost to the point where i may release my STL. But there is plenty of example skip list implementations out there.

  : Yes, there is plenty of skip list code available. I was looking for something that specifically complies with std::map<> interface. QMap looks quite close, so I'll give that a try. Thank-you

• 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

  Head Geek : I'm accepting this one because of the DDJ article it references. Apologies to Even and Steve, I'd accept all three answers if I could.

• 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

• 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