Paper by Erik D. Demaine
- 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.
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.
- The paper is 19 pages.
- 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.
These pages are generated automagically from a
Last updated January 4, 2022 by