Beyond Linked Lists: The Skip List

Illustration of a skip list.  Note that the number of forward pointers per node is itself dynamically allocated.

Students who want exposure to data structures more advanced than a simple linked list might enjoy the skip list.  A skip list is a probabilistic data structure that looks a bit like a linked list, but behaves like a self-balancing binary tree that makes insertion and deletion relatively simple and fast.  If you want to know about a self-balancing tree that is challenging to implement, go try a red-black tree.  This spirit of the data structure turns up every now and then, such as in distributed hash tables used in peer-to-peer file sharing among other things.

"Skip Lists: A Probabilistic Alternative to Balanced Trees" by William Pugh, Communications of the ACM, June 1990.