Skip Lists?!

goran.hultgren at bluefish.se goran.hultgren at bluefish.se
Wed Sep 26 09:51:55 UTC 2001


"Andreas Raab" <Andreas.Raab at gmx.de> wrote:
> Folks,
> 
> I noticed them coming into Squeak a while ago and always since I wanted to
> ask this question: What the heck are they good for?! ;-) I don't see them

Well, I was also implementing them for fun and there are some nice pdfs
on the net somewhere (Google ought to find them for you) explaining them
in detail - including a revised concurrent version (which the
implementation in Squeak is not I assume). Note: there might be factual
errors here - I am no expert:

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

As far as I can tell it is a very good alternative to balanced binary
trees (much easier implementation being prime advantage I believe) -
performance wise they are much the same. I read somewhere that database
implementations still might prefer Btrees because of some property that
make them more efficient when it comes to distribution on secondary
memory - but I don't know the details on that.

So... seems like a good structure to have in Squeak - even if nobody
uses it yet! :-)

regards, Göran

> used anywhere and I've never heard of 'em before (yeah, well, my
> introductory courses in algorithms and data structures were plenty of years
> back ;-) but somebody found them important enough to write and include them.
> Since I like data structures (in particular efficient ones) I'd like to hear
> more about the places in which SkipLists could and should be used instead of
> other approaches. Pointers to comparisons would be nice, examples in Squeak
> even nicer ;-)
> 
> 
> Cheers,
>   - Andreas




More information about the Squeak-dev mailing list