Contents |
A dynamic array is a fillable array that can grow in capacity should the array become completely filled, thus making room for more additions. Conversely, a dynamic array can shrink in capacity if it becomes mostly empty.
The typical dynamic array object adds one component to those of a fillable array.
class dynamic-array extends fillable-array { var factor = 2; //how much to grow or shrink the store by //operations ... }
The factor is typically set to two, which means growing the array doubles its capacity. Conversely, shrinking the array halves the capacity.
The terms used in describing a dynamic array, in addition to those of normal arrays, are:
Dynamic arrays can be used to implement:
They are also useful for reading in an unknown quantity of data:
items = new-dynamic-array(); value = readValue(); if (valid(value)) { items.add-to-back(value); value = readValue(); } items.shrink-to-fit();
The shrink-to-fit is like shrink, but the operation removes all empty slots.
Dynamic arrays can be implemented using fillable arrays.
This operation works the same as add-to-back for fillable arrays. The only difference is, at the very start of the operation, a check is made to see if the array is full. If it is, a grow operation is performed. Whether or not, the array was full at the start of add-to-back, there is now at least one empty slot in which the new value can be placed.
function add-to-back(value) { if (size == capacity) grow(); store[size] = value; size += 1; }
This operation takes Θ(1) time if the array is not full, but takes Θ(n) time if it is, due to the expense of the grow operation.
As with fillable arrays, this operation removes the rightmost value in the array and can be done simply by decrementing the size. However, a test can be made to see if the array has become mostly empty. If so, a shrink operation can be performed. A good metric: when the ratio of size to capacity is less than 0.25, the array should be shrunk.
This operation takes Θ(n) time if shrinking occurs, due to the expense of the shrink operation. Otherwise, the operation takes Θ(1) time.
The grow operation performs the following steps:
Although it is beyond this document to explain why, computing the new capacity using a constant multiplicative factor (e.g., doubling the capacity) gives far better efficiency than by using a constant additive term (e.g., increasing the capacity by 100).
The shrink operation is similar to that of the grow operation, except that the capacity is made smaller. As with grow, computing the new capacity by dividing by a constant gives better performance than by subtracting off a constant.
A variant of shrink is shrink-to-fit, where the capacity is reduced to the size so that the resulting store is completely filled.
These operations are the same as those for (or inherited from) fillable arrays.
Traversing a dynamic array proceeds exactly as that for a fillable array.
Contents |