Randomized jumplists - a Jump-and-Walk Dictionary Data Structure

• Version appeared at STACS 2003.  
• Latest version of the paper.  
• The code which was used to perform the experiments in the paper. (Note: this code is not complete, in particular it does not handle deletions well, but it is sufficient to reproduce the tables on your machine). (Zipped file; jumplist.zip) (Tar gzipped; jumplist.tar.gz)

Abstract: This paper presents a data-structure providing the usual dictionary
operations, i.e. Contains, Insert, Delete.  This data structure named
Jumplist is a linked list whose nodes are endowed with an additional
pointer, the so-called jump pointer.  Algorithms on jumplists are based
on the jump-and-walk strategy: whenever possible use to the jump pointer
to speed-up the search, and walk along the list otherwise.

The main features of jumplists are the following. They perform
within a constant factor of binary search trees.
Randomization makes their dynamic maintenance very easy.  Jumplists are
a compact data structure. (To the best of our knowledge, jumplists are
the only data structure providing rank-based operations and iterators at
a cost of 12 bytes per node.) Jumplists are trivially built in linear
time from sorted linked lists.

In addition to the presentation of jumplists and the probabilistic
analysis of their expected performances, the paper presents a detailed
experimental study of jumplists against Red-Black trees, randomized BSTs,
and splay trees.