Abstract
We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l..l + n − 1], of fixed-size elements, as elements are added to or removed from one or both ends. Our structures also support access to the element in position i. All operations are performed in constant time. The extra space (i.e., the space used past storing the n current elements) is O(√n) at any point in time. This is shown to be within a constant factor of optimal, even if there are no constraints on the time. If desired, each memory block can be made to have size 2k − c for a specified constant c, and hence the scheme works effectively with the buddy system. The data structures can be used to solve a variety of problems with optimal bounds on time and extra storage. These include stacks, queues, randomized queues, priority queues, and deques.
This is a preview of subscription content, log in via an institution to check access.
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
A. Brodnik. Computation of the least significant set bit. In Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia, 1993.
A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro, and R. Sedgewick. Resizable arrays in optimal time and space. Technical Report CS-99-09, U. Waterloo, 1999.
M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SICOMP, 23(4):738–761, Aug. 1994.
M. L. Fredman and D. E. Willard. Surpassing the information theoretic bound with fusion trees. JCSS, 47(3):424–436, 1993.
M. T. Goodrich and J. G. Kloss II. Tiered vector: An efficient dynamic array for JDSL. This volume.
D. E. Knuth. The Art of Computer Programming. Addison-Wesley, 1968.
M. K. McKusick, K. Bostic, M. J. Karels, and J. S. Quarterman. The Design and Implementation of the 4.4 BSD Operating System. Addison-Wesley, 1996.
R. Motwani and P. Raghavan. Randomized Algorithms. Camb. Univ. Press, 1995.
W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. Numerical Recipes in C: The Art of Scientific Computing. Camb. Univ. Press, 2nd ed., 1992.
R. Sedgewick. Algorithms in C. Addison-Wesley, 3rd ed., 1997.
B. Stroustrup. The C++ Programming Language. Addison-Wesley, 3rd ed., 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brodnik, A., Carlsson, S., Demaine, E.D., Ian Ian Munro, J., Sedgewick, R. (1999). Resizable Arrays in Optimal Time and Space. In: Dehne, F., Sack, JR., Gupta, A., Tamassia, R. (eds) Algorithms and Data Structures. WADS 1999. Lecture Notes in Computer Science, vol 1663. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48447-7_4
Download citation
DOI: https://doi.org/10.1007/3-540-48447-7_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66279-2
Online ISBN: 978-3-540-48447-9
eBook Packages: Springer Book Archive