--- goran.hultgren at 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 at 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