Circular Arrays Top Dynamic Circular Arrays Contents

Dynamic Arrays

Synopsis

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.

Structure

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.

Vocabulary

The terms used in describing a dynamic array, in addition to those of normal arrays, are:

dynamic fillable array
a more precise description of this data structure.
slot
A spot in the array which may or may not hold an element. Each spot is associated with a unique index.
empty slot
A spot in the array that does not (yet) hold an element.
filled slot
A spot in the array that holds an element.
capacity
The maximum number of elements that can be stored in an array. Also, the length of the array.
front
The first/leftmost value in the array.
back
The last/rightmost value in the array. With zero-based counting, if the array is non-empty, the back (or rear) element in the array has index size - 1.
size
The number of elements stored in the array. The size ranges from 0 (the array is completely empty) to the capacity of the array (the array is completely full). Also, with zero-based counting the size of the array is also an index that points to the next available slot.

Supports

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.

Dependencies

Dynamic arrays can be implemented using fillable arrays.

Operations

add-to-back (override)

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.

remove-from-back (override)

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.

grow

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).

shrink

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.

get, set, find

These operations are the same as those for (or inherited from) fillable arrays.

Traversals

Traversing a dynamic array proceeds exactly as that for a fillable array.

Concept Inventory

     
  1. Suppose a dynamic array has size s and capacity c, with s equal to c. Is the array required to grow on the next addition?
    1. true
    2. false

lusth@cs.ua.edu


Circular Arrays Top Dynamic Circular Arrays Contents