Carleton University - School of Computer Science Honours Project
Winter 2021
An Analysis and Implementation of the Jumplist Data Structure
Roman Ranallo
SCS Honours Project Image
ABSTRACT
A Jumplist is a data structure introduced by Hervé Brönnimann, Frédéric Cazals, and Marianne Durand in 2003. It augments a sorted linked list by adding an additional "jump" pointer to each node, that points to a subsequent node uniformly at random, preserving the O(n) space complexity of the list. However, this improves the runtimes of each of the search, insert, and delete operations from O(n) in a sorted linked list to O(log n) expected time in the Jumplist. In this project, pseudocode and a formal analysis is given for each of the operations, and an implementation was done in Java to test the results experimentally.