Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Resizable arrays in optimal time and space
Luleå tekniska universitet.
Department of Computer Science, University of Waterloo, Ontario.
Department of Computer Science, University of Waterloo, Ontario.
Show others and affiliations
1999 (English)In: Algorithms and Data Structures: 6th International Workshop, WADS'99 Vancouver, Canada, August 11-14, 1999 Proceedings / [ed] Frank Dehne, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1999, 37-48 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1999. 37-48 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1663
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-26832DOI: 10.1007/3-540-48447-7Local ID: 0168a6a0-f0fd-11dc-ba03-000ea68e967bISBN: 3-540-66279-0 (print)OAI: oai:DiVA.org:ltu-26832DiVA: diva2:1000012
Conference
International Workshop on Algorithms and Data Structures : 11/08/1999 - 14/08/1999
Note
Godkänd; 1999; 20080313 (ysko)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2017-11-25Bibliographically approved

Open Access in DiVA

fulltext(256 kB)23 downloads
File information
File name FULLTEXT01.pdfFile size 256 kBChecksum SHA-512
1fd3ca8fe4ab2f24acc176a1888a5b62751b7307abe45ed58f6f67e9dbac399ad2317974745e79484a07f286fa121ee56c644158efc3ad3a5ee0a09ac0722d19
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Brodnik, Andrej
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 23 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 13 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf