Dynamic array: Difference between revisions

Revision as of 22:07, 24 November 2005

Revision as of 22:23, 24 November 2005

Line 48:

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 the 1999 paper ''Resizable Arrays in Optimal Time and Space'', 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.

== Language support ==

Line 56 ⟶ 58:

* [[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.

== External links ==