Content deleted Content added
Array article talks about dynamic arrays |
Write intro, discuss operations, amortized costs, brief language support, CLRS reference |
||
Line 1:
A '''dynamic array''', '''growable array''', or '''dynamic table''' 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.
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.
Dynamic arrays or growable arrays are arrays which automatically perform this resizing as late as possible, when the programmer attempts to add an element to the end of the array and there is no more space. However, if we added just one element to the array each time it runs out of space, the cost of the resizing operations rapidly becomes prohibitive.
To deal with this, we instead resize the array by a large amount, such as doubling its size. Then, the next time we need to enlarge the array, we just expand it into some of this reserved space. The amount of space we have allocated for the array is called its ''capacity'', and it may be larger than its current logical size. Here's how the operation adding an element to the end might work:
'''function''' insertEnd(''dynarray'' a, ''element'' e)
'''if''' a.size = a.capacity {
resize a to twice its current capacity
a.capacity = a.capacity × 2
}
a[a.size] := e
a.size := a.size + 1
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 shrink the array 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.
In computer science education, dynamic arrays often serve as an elementary example of amortized analysis because of their simplicity and familiarity.
== Language support ==
[[C Plus Plus|C++]]'s <code>std::vector</code> is an implementation of dynamic arrays, as are the <code>ArrayList</code> classes supplied with the [[Java programming language|Java]] API and the [[.NET Framework]]. The generic <code>List<></code> class supplied with version 2.0 of the .NET Framework is also implemented with dynamic arrays.
== References ==
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0262032937. Section 17.4: Dynamic tables, pp.416–425.
| |||