--- goran.hultgren@bluefish.se wrote:
Basically it is a list with overlayed pointers that you can use to "skip ahead" in the list. These pointers are created using randomness and thus you end up with searchproperties etc much like a balanced binary tree - but you don't have to worry about balancing etc. and insertions/deletions and so forth are much easier implemented. It is a damn clever and rather "obvious" solution, but who would even think of using randomness in a datastructure? :-)
Well... The original "skip list" solution did use fixed intervals between node instead of random ones. But then insertion was a nightmare and pretty inefficient. It was just like managing a completely balanced tree. So a guy named Pugh came up with the idea of having random intervals to facilite insertions and keep logarithmic search time...
Do I have any example of a "good reason to use a skip list" instead of (Insert favorite data structure here) ? No! But there conceptually so cool! But if you find any, let me know!!!
===== ---------------------- Benoit St-Jean bstjean@yahoo.com ICQ: 130611319 / Yahoo Mssngr: bstjean http://cactus.swiki.net "We're only immortal for a limited time", Neil Peart ----------------------
__________________________________________________ Do You Yahoo!? Get email alerts & NEW webcam video instant messaging with Yahoo! Messenger. http://im.yahoo.com