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.
Extended abstract. Due to space limitations, all proofs have been omitted. Refer to [1] for the full paper.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hervé Brönnimann, Frédéric Cazals and Marianne Durand. Randomized jumplists: A jump-and-walk dictionary data structure. Research Report RR-xxxx, INRIA, 2003.
M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover, 1973. A reprint of the tenth National Bureau of Standards edition, 1964.
N. Amenta, S. Choi, T. K. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 213–222, 2000.
Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom., 22(4):481–504, 1999.
C. Aragon and R. Seidel. Randomized search trees. In Proc. 30th Annu. IEEE Sympos. Found. Comput. Sci., pages 540–545, 1989.
Jean-Daniel Boissonnat and Frédéric Cazals. Smooth surface reconstruction via natural neighbour interpolation of distance functions. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 223–232, 2000.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106–115, 1998.
P. Flajolet and A. M. Odlyzko. Singularity analysis of generating functions. SIAM J. Disc. Math., 3(2):216–240, 1990.
G. H. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures. Addison-Wesley, 1991.
D. H. Greene and D. E. Knuth. Mathematics for the analysis of algorithms. Birkhäuser, Boston, 1982.
H.-K. Hwang. Théorèmes limites pour les structures combinatoires et les fonctions arithmetiques. PhD thesis, Éecole Polytechnique, Palaiseau, France, December 1994.
Donald E. Knuth. The Art of Computer Programming, Vol 3., @nd Edition. Addison-Wesley, 1998.
H. M. Mahmoud. Evolution of random search trees. Wiley, 1992.
C. Martínez and S. Roura. Randomized binary search trees. J. Assoc. Comput. Mach., 45(2), 1998.
J. I. Munro, T. Papadakis, and R. Sedgewick. Deterministic skip lists. In SODA, Orlando, Florida, United States, 1992.
W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM, 33(6):668–676, 1990.
S. Roura. An improved master theorem for divide-and-conquer recurrences. J. Assoc. Comput. Mach., 48(2), 2001.
R. Sedgewick. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching. Addison-Wesley, third edition, 1998.
R. Sedgewick and P. Flajolet. An Introduction to the Analysis of algorithms. Addison-Wesley, 1996.
R. Sedgewick and P. Flajolet. Analytic combinatorics-symbolic combinatorics. To appear, 2002.
R. Seidel and C. R. Aragon. Randomized search trees. Algorithmica, 16:464–497, 1996.
D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652–686, 1985.
J. S. Vitter and P. Flajolet. Average-case analysis of algorithms and data structures. In J. van Leeuwen, editor, Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science, pages 432–524. Elsevier, Amsterdam, 1990.
N. Wirth. Algorithms + Data Structures = Programs. Prentice-Hall, 1975.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brönnimann, H., Cazals, F., Durand, M. (2003). Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure. In: Alt, H., Habib, M. (eds) STACS 2003. STACS 2003. Lecture Notes in Computer Science, vol 2607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36494-3_26
Download citation
DOI: https://doi.org/10.1007/3-540-36494-3_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00623-7
Online ISBN: 978-3-540-36494-8
eBook Packages: Springer Book Archive