Re: Skip List

From: Michael (f-boost_at_[hidden])
Date: 2001-11-05 14:48:52

--- In boost_at_y..., Beman Dawes <bdawes_at_a...> wrote:
>  >http://unlikely.org/mike/outbox/2001/11/04/skip_list.hpp
>
> > This is a rather naive implementation of the skip list data 
> > structure.
> 
> Always hard to tell without docs, but it looks like whatever you 
> implemented is quite a bit different from Bill Pugh's original June,
> 1990, CACM description of this data structure.  The node structure
> looks way different, or am I just misreading your code?

No, it's probably way different.

> Do you have a reference to a description of your data structure and 
> how it differs from Pugh's?

I'm sorry, I've never read this and can't find it on ACM or Yahoo.

If we picture a skip list thusly:

1         9
1   4     9
1 3 4 5 8 9

I can perhaps explain it like so: my goal was to be able to associate
data with each instance of 1 in the list.

So.  That is probably the source of a great deal of the difference. 
Or maybe not.  I am guessing.  Anyhow, it's probably not worth either
of our time to come to an understanding.  As I said in the last post,
upon reflection, it is probably not a broad audience who will find
application for this thing.

> 
> --Beman