Dynamic array: Difference between revisions

Revision as of 16:15, 7 June 2006

Revision as of 10:01, 10 August 2006

Line 51:

Another variation, notably used by the [[library sort]] algorithm, leaves carefully placed gaps between elements to facilitate rapid insertion in the middle of the list.

One of the problems with the simple dynamic array is that it often has a constant fraction of cells not in use, which wastes space. In thea 1999 paper<ref>Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, and Robert Sedgewick. [http://citeseer.ist.psu.edu/brodnik99resizable.html ''Resizable Arrays in Optimal Time and Space] (1999). ''Workshop on Algorithms and Data Structures'', pp.37&ndash;48</ref>, Brodnik et al. describe a dynamic array data structure which wastes only <math>\sqrt{n}</math> space for ''n'' elements at any point in time, and they prove a lower bound showing that any dynamic array must waste this much space if the operations are to remain amortized constant time. Additionally, they present a variant where growing and shrinking the buffer has not only amortized but worst-case constant time. However, like the circular buffer variant, these structures have the problem that indexing into the array is somewhat slower in practice.

== Language support ==

Line 64:

== References ==

<references/>

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 17.4: Dynamic tables, pp.416&ndash;425.

* Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, and Robert Sedgewick. [http://citeseer.ist.psu.edu/brodnik99resizable.html Resizable Arrays in Optimal Time and Space] (1999). ''Workshop on Algorithms and Data Structures'', pp.37&ndash;48.

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 17.4: Dynamic tables, pp.416&ndash;425.

== External links ==