Dynamic array

When all space is consumed, and an additional element is to be added, then the underlying fixed-size array needs to be increased in size.

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

For growth factor a, the average time per insertion operation is about a/(a−1), while the number of wasted cells is bounded above by (a−1)n[citation needed].

Gap buffers are similar to dynamic arrays but allow efficient insertion and deletion operations clustered near the same arbitrary location.

The algorithm has O(1) amortized performance when appending a series of objects to the end of a hashed array tree.

In a 1999 paper,[18] Brodnik et al. describe a tiered dynamic array data structure, which wastes only n1/2 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.

Many scripting languages such as Perl and Ruby offer dynamic arrays as a built-in primitive data type.

Several cross-platform frameworks provide dynamic array implementations for C, including CFArray and CFMutableArray in Core Foundation, and GArray and GPtrArray in GLib.

Common Lisp provides a rudimentary support for resizable vectors by allowing to configure the built-in array type as adjustable and the location of insertion by the fill-pointer.