Content deleted Content added
m →References: Fix year |
More sectioning, add operation times |
||
Line 1:
A '''dynamic array''', '''growable array''', '''dynamic table''', or '''array list''' is a [[data structure]], an [[array]] which is automatically expanded to accomodate new objects if filled beyond its current size. It may also automatically deallocate some of its unused space to save memory. They have become a popular [[data structure]] in modern mainstream programming languages, supplied with most standard libraries.
== Overview ==
One of the main disadvantages of a simple array is that it has a single fixed size, and although its size can be altered in some environments (for example, with C's <code>realloc</code> function), this is an expensive operation that may involve copying the entire contents of the array.
Line 19 ⟶ 21:
Many dynamic arrays also deallocate some of the underlying storage if its size drops below a certain threshold, such as 30% of the capacity.
In computer science education, dynamic arrays often serve as an elementary example of amortized analysis because of their simplicity and familiarity.▼
In choosing the percentage by which to enlarge the table, there is a time-space tradeoff: the average time per insertion operation is about ''a''/(''a''−1), where ''a'' is the multiplier factor such as 2 by which the table size increases each time. On the other hand, ''capacity'' minus ''size'' space is allocated but not in use, a quantity bounded above by (''a''−1)''n''. The choice ''a''=2 is a commonly-used value, but depending on the application many values between about ''a''=1.2 and ''a''=4 may be suitable.▼
== Performance ==
In most ways the dynamic array has performance similar to an array, with the addition of new operations to add and remove elements from the end:
* Getting or setting the value at a particular index (constant time)
* Iterating over the elements in order (linear time, good cache performance)
* Add an element to the end (constant amortized time)
* Remove an element from the end (constant amortized time, or just constant time if there is no buffer shrinking)
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.
== Analysis ==
▲In computer science education, dynamic arrays often serve as an elementary example of amortized analysis because of their simplicity and familiarity.
▲In choosing the percentage by which to enlarge the table, there is a time-space tradeoff: the average time per insertion operation is about ''a''/(''a''−1), where ''a'' is the multiplier factor such as 2 by which the table size increases each time. On the other hand, ''capacity'' minus ''size'' space is allocated but not in use, a quantity bounded above by (''a''−1)''n''. The choice ''a''=2 is a commonly-used value, but depending on the application many values between about ''a''=1.2 and ''a''=4 may be suitable.
== Language support ==
| |||