TY - GEN
T1 - Resizable arrays in optimal time and space
AU - Brodnik, Andrej
AU - Carlsson, Svante
AU - Demaine, Erik D.
AU - Munro, J. Ian
AU - Sedgewick, Robert
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999
Y1 - 1999
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33845521680&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33845521680&partnerID=8YFLogxK
U2 - 10.1007/3-540-48447-7_4
DO - 10.1007/3-540-48447-7_4
M3 - Conference contribution
AN - SCOPUS:33845521680
SN - 3540662790
SN - 9783540662792
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 37
EP - 48
BT - Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings
A2 - Dehne, Frank
A2 - Sack, Jorg-Rudiger
A2 - Gupta, Arvind
A2 - Tamassia, Roberto
PB - Springer Verlag
T2 - 6th International Workshop on Algorithms and Data Structures, WADS 1999
Y2 - 11 August 1999 through 14 August 1999
ER -