Hi visitor! Apparently, this is the #1 Google result if you are searching for a "javascript skiplist" and "javascript skip list" This is a reference implementation that was written, jeez, close to a decade ago now.
As you can see, if you look at the code, it's quite minimal and a bit archaic, (this vs object literal) but on the bright side, is completely standalone, and pretty easy to understand. The only other version I could find is this old Dojo 0.4 version, but is AFL licensed.
If you have a better version, please drop me a line and I'll point to it.
.lhl, 2011-11-18
Now, you might be saying to yourself, "Ahh, a skip list, one of my favorite data structures!" However, much more likely, you're probably wondering WTF a skip list (NIST reference) is.
A skip list is a randomized variant of an ordrered linked list with additional, parallel lists.
This is a probabilistic alternative to balanced trees that in general practice gives O(log n) searching w/ easy inserts and deletions (no tree reshuffling).
This OOP JavaScript implementation was created almost entirely from Pugh's original publication, Skip Lists: A Probabilistic Alternative to Balanced Trees.
Additional reference URLs are included with the documentation. (The University of Melbourne has this neat Java animated demo).
Here's an example of how to use it:
var sl = new SkipList(5, 0.5); // 5 level, 0.5 probability sl.Insert(10, "ten"); // Insert a key, value var v = sl.Search(10); // Return the value searching by key sl.Delete(10); // Delete key
Code licensed under the GPL (any version).
Available at Github:
For more some interesting recent discussion on skiplists, you may want to check out this discussion on StackOverflow.