Search code examples
data-structuresbinary-treeskip-lists

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

Solution

  • 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