Content deleted Content added
More sectioning, add operation times |
Variations |
||
Line 37:
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.
== Variations ==
Dynamic arrays supporting additional operations efficiently can be created. For example, by using cells from the middle of the buffer instead of the beginning of the buffer, one can allow amortized constant time insertion and deletion at both ends, at the expense of keeping track of the starting index of the data (this variation may also require copying during buffer growing more often, since functions like <code>realloc()</code> typically only grow in one direction). This variation is implemented by such standard classes as C++'s <code>std::deque</code>.
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.
== Language support ==
| |||