Here's the basic code.

 http://shofar.appliedreasoning.com/goodies/squeak/skipLists/

I tried to make Pugh's code (from his paper) more OO here.  I'm
finishing up implementing IntervalSkipLists to do spatial indexing for a
project I'm working on.  I'm going to try integrating IntervalSkipLists
with Morphic to see if it speeds it up any (it may reduce time for
Morph>>morphAt:, PasteUpMorph>>drawInvalidAreasOn:, and others by an
order of magnitude).

SkipListTests new test1 will show you a basic time trial.  They seem to
be significantly faster than linear searching arrays for more than 100
elements in the test (try it with 100000 elements for a real crushing
blow).  The test uses floating point numbers.  The type of comparison
will alter the number of items in the cutoff (a more complex comparison
will reduce the number below 100).

Mark G.: I met one of your students in an elevator at OOPSLA.  He said
that he had to implement SkipLists in Squeak in your class.  I'd be
interested to see your comments on my implementation.

-- Bill Burdick
bill at appliedreasoning.com