Resizable arrays in optimal time and space

Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Arvind Gupta, Roberto Tamassia
PublisherSpringer Verlag
Pages37-48
Number of pages12
ISBN (Print)3540662790, 9783540662792
DOIs
StatePublished - 1999
Event6th International Workshop on Algorithms and Data Structures, WADS 1999 - Vancouver, Canada
Duration: Aug 11 1999Aug 14 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1663
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International Workshop on Algorithms and Data Structures, WADS 1999
CountryCanada
CityVancouver
Period8/11/998/14/99

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Resizable arrays in optimal time and space'. Together they form a unique fingerprint.

  • Cite this

    Brodnik, A., Carlsson, S., Demaine, E. D., Munro, J. I., & Sedgewick, R. (1999). Resizable arrays in optimal time and space. In F. Dehne, J-R. Sack, A. Gupta, & R. Tamassia (Eds.), Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings (pp. 37-48). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1663). Springer Verlag. https://doi.org/10.1007/3-540-48447-7_4