Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • 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.
Visa övriga samt affilieringar
1999 (Engelska)Ingår i: 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, s. 37-48Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1999. s. 37-48
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1663
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
URN: urn:nbn:se:ltu:diva-26832DOI: 10.1007/3-540-48447-7Lokalt ID: 0168a6a0-f0fd-11dc-ba03-000ea68e967bISBN: 3-540-66279-0 (tryckt)OAI: oai:DiVA.org:ltu-26832DiVA, id: diva2:1000012
Konferens
International Workshop on Algorithms and Data Structures : 11/08/1999 - 14/08/1999
Anmärkning
Godkänd; 1999; 20080313 (ysko)Tillgänglig från: 2016-09-30 Skapad: 2016-09-30 Senast uppdaterad: 2023-09-06Bibliografiskt granskad

Open Access i DiVA

fulltext(256 kB)638 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 256 kBChecksumma SHA-512
1fd3ca8fe4ab2f24acc176a1888a5b62751b7307abe45ed58f6f67e9dbac399ad2317974745e79484a07f286fa121ee56c644158efc3ad3a5ee0a09ac0722d19
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Person

Brodnik, Andrej

Sök vidare i DiVA

Av författaren/redaktören
Brodnik, Andrej
Av organisationen
Luleå tekniska universitet
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 638 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 70 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf