Dynamic Arrays Top Nodes Contents

Dynamic Circular Arrays

Synopsis

Like dynamic arrays, dynamic circular arrays appear never to become full. When an attempt is made to add an element to a full array, the store is grown to accomodate the addition. When elements are removed, dynamic circular arrays can also shrink, if desired.

Structure

The typical dynamic circular array object adds one component to those of a circular array.

    class dynamic-circular-array extends circular-array
        {
        var factor = 2;         //how much to grow or shrink the store by
        //operations
        ...
        }

As with dynamic arrays, the factor is typically set to two, which means growing the array doubles its capacity. Conversely, shrinking the array halves the capacity.

Vocabulary

The vocabulary of dynamic circular arrays combines the vocabularies of dynamic arrays. and circular arrays.

Supports

Dynamic circular arrays are primarily used to implement queues. They can be used to implement stacks, but the simple dynamic arrays suffice.

Dependencies

Dynamic circular arrays can be implemented with circular arrays.

Operations

incrementIndex, decrementIndex, correctIndex

These operations are the same as that of circular arrays.

add-to-front (override), add-to-back (override)

These routines call grow if the array is full, before performing the logic of the superclass version of the functions.

See the add operations of dynamic arrays for more information.

remove-from-front (override), remove-from-back (override)

These routines call grow, if the array becomes significantly empty, before performing the logic of the superclass version of the functions.

See the remove operations of dynamic arrays for more information.

grow, shrink

The grow and shrink operations are the same as that of dynamic arrays, but the start index is usually reset to zero. Thus, the element at the start index of the old store gets placed in the leftmost slot in the new store, and so on. When computing the index of the next element to be transferred, the incrementIndex or correctIndex functions should be used.

get, set, find

These operations are the same as that of circular arrays.

Traversals

Traversals over dynamic circular arrays are the same as that for circular arrays.

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


Dynamic Arrays Top Nodes Contents