Dynamic array: Difference between revisions

Revision as of 00:36, 19 November 2005

Revision as of 00:37, 19 November 2005

Line 3:

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: