SkipList.js - A JS Skip List Class

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.