Skip List: A Probabilistic Alternative to Balanced Trees

- an interactive Demo-Applet -

Skip Lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforcing balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees. Skip lists have first been published by William Pugh.

This interactive Java applet allows the user to experiment on the behaviour of skip lists.
The functions offered should be self explaining.
Author: Thomas Wenger, University of Berne, Switzerland


 Jan-2-1997, Thomas Wenger