Dynamic array: Difference between revisions

Revision as of 22:29, 24 November 2005

Revision as of 22:51, 24 November 2005

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 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. Additionally, they present a variant where growing and shrinking the buffer has not only amortized but worst-case constant time.

== Language support ==