Title: Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure
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 easy. Jumplists are a compact data structure since they provide rank-based operations and forward iterators at a cost of three pointers/integers per node. Jumplists are trivially built in linear time from sorted linked lists.
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 13
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot