From: Michael (f-boost_at_[hidden])
Date: 2001-11-05 14:48:52
--- In boost_at_y..., Beman Dawes <bdawes_at_a...> wrote:
> > 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 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk