Jump list

From Wikipedia, the free encyclopedia

In computer science, a jump list is a data structure which resembles an ordered doubly linked list. Instead of only next and previous links, several nodes contain links to nodes farther away, with the distance increasing geometrically. This allows the dictionary operations search, insert and delete to be executed in O(³√n) time.

[edit] See also

• Dictionary
• Linked list
• Skip list

[edit] References

• Paul E. Black, jump list at the NIST Dictionary of Algorithms and Data Structures.
• Arne Andersson and Thomas Ottmann, New Tight Bounds on Uniquely Represented Dictionaries, SIAM Journal of Computing, 24(5):1091-1103, 1995.