Dynamic array: Difference between revisions

Revision as of 00:37, 19 November 2005

Revision as of 00:38, 19 November 2005

Line 17:

Using [[amortized analysis]], it can be shown that as long as we expand the array by some fixed percentage each time, the cost for inserting ''n'' elements will be O(''n''); we say the insertions have an ''amortized cost'' of O(1) each.

Many dynamic arrays also shrinkdeallocate some of the arrayunderlying storage if its size drops below a certain threshold, such as 30% of the capacity.

Dynamic arrays benefit from many of the advantages of arrays, including good [[locality of reference]] and [[data cache]] utilization, compactness (low memory use), and [[random access]]. They usually have only a small fixed additional overhead for storing information about the size and capacity. This makes dynamic arrays an attractive tool for building cache-friendly data structures.