**Reference**:- Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, and Robert Sedgewick, “Resizable Arrays in Optimal Time and Space”, Technical Report CS-99-09, Department of Computer Science, University of Waterloo, 1999.
**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 2^{k}−*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. **Length**:- The paper is 19 pages.
**Availability**:- The paper is available in PostScript (279k), gzipped PostScript (109k), and ZIPped PDF (724k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- ResizableArrays_WADS99 (Resizable Arrays in Optimal Time and Space)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.