Deterministic jumplists
Amr Elmasry · Nordic journal of computing · 2005
We give a deterministic version of the randomized jumplists recently introduced by Bronnimann et al. [2003]. The new structure supports searches in worst-case logarithmic time, insertions and deletions in amortized logarithmic time (versus expected logarithmic time for the randomized version), and the successor of an element can be accessed in worst-case constant time (similar to the randomized version). As for the randomized version, our deterministic counterpart does not involve duplicate indexing information or extra pointers to access the successor, in contrast with other known dictionary structures. A Jumplist is basically an ordered linked list with an extra jump pointer per node to speed up the search, using a total of two pointers and two integers per node. All dictionary operations are implemented in an easy, efficient and compact way.