Fillable Arrays Top Dynamic Arrays Contents

Circular Arrays

Synopsis

A circular array is like a fillable array except values can be added to and removed from the front of the store as well as the back. A consequence of this is the front element of the store may have an associated index other than zero. To avoid shifting elements when adding an element to the front of the store, indices are allowed to roll over. For example, suppose the capacity is 10 and the size is 5, with the first element residing at index 0 (using zero-based counting). Adding a new value to the front should place it at index -1, which does not exist. Since the index is too small (i.e., negative), the capacity is added to the index to make it non-negative. For our example, the new index is -1 plus 10, or 9. Thus the new element is added at index 9, the rightmost slot. Conversely, with the same size and capacity as before, but with the index of the first element being 5, consider adding an element to the back. In this case, the index of the most rightmost element is 9, because the size is 5 (the five values are stored at indices 5, 6, 7, 8, and 9). Adding an element at the back would place it at index 10, which does not exist. Since the index is too large, the proper index is then computed by subtracting off the capacity. The places the to-be-added element at index 0. The tests for indices being too small or too large can be eliminated by the use of modular arithmetic.

As with fillable arrays circular arrays use a normal array as a store.

Structure

The typical circular array object has three components plus a set of operators:

    class circular-array
        {
        var store = ?;      //points to an array
        var capacity = ?;   //length of the store
        var size = 0;       //net number of elements added
        var startIndex = 0; //index of the first/leftmost element
        var endIndex = 0;   //optional: index of the first open slot
        //operations
        ...
        }

The store component points to a normal array and is set by the constructor. The capacity is usually given as an argument to the constructor and is used to allocate the store. Both the start and end indices are set to zero; the only case when these indices are equal is when the circular array is empty.

Vocabulary

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

start index
The index of the first element in the store. When computing a new start index, if the result is too large, it is corrected by subtracting off the capacity. If it becomes to small (e.g., negative for zero-based counting), it is corrected by adding in the capacity.
end index
The index of the first open slot in the store. It is computed dynamically by adding the size to the start index. If the generated index is too large, it is corrected by subtracting off the capacity. The end index may also be cached as a component of the data structure.
index correction
The process of correcting an index if it is too small or too large. A convenient method of correction uses modular arithmetic.
modular arithmetic
A calculated index, whether it be too small or two large, can be corrected by adding in the capacity and then modding by the capacity. If the calculated index was neither too small or too large, the operations of adding in the capacity and then modding has no effect.

Supports

Circular arrays can be used to implement:

Circular arrays are used as a basis for:

Dependencies

Circular arrays are implemented using arrays, with similarities to fillable arrays.

Operations

decrement-index

This operation subracts one from the given index. If the resulting value becomes too small, the value is corrected by adding in the capacity. In any case, the new, perhaps corrected, value is returned.

This operation is generally a private method.

increment-index

Like decrement-index, except one is added to the given index (with possible correction).

This operation is generally a private method.

correct

The increment and decrement operations can be replaced with this operation which typically uses modular arithmetic to adjust the given index. The calls:

    u = decrementIndex(v)
    x = incrementIndex(y)

would be replaced with:

    u = correctIndex(v - 1);
    x = correctIndex(y + 1);

This operation is generally a private method.

add-to-front

This operation adds a given value to the front of the store. A special case exists if the array is empty. If so, add-to-back is called to handle the addition. Otherwise, the start index is decremented and corrected, if necessary.

    function add-to-front(value)
        {
        if (size == 0)
            add-to-back(value)
        else
            {
            startIndex = decrementIndex(startIndex);
            store[startIndex] = value;
            size += 1;
            }
        }

Adding an element to the front takes Θ(1) time.

add-to-back

This operation adds a given value to the back of the store. Unlike fillable arrays, the next available slot may not have index size. The start index is added to the size to generate the actual index of the next available slot. The generated index is corrected, if necessary.

    function add-to-back(value)
        {
        store[endIndex] = value;
        endIndex = incrementIndex(endIndex)
        size += 1;
        }

Adding an element to the back takes Θ(1) time.

remove-from-front

This operation removes the leftmost value in the store. This can be done simply by incrementing the start index (with correction). The size component is updated accordingly.

Removing the front element takes Θ(1) time.

remove-from-back

This operation removes the rightmost value in the store. This can be done simply by decrementing the size, if the end index is not cached. If the end index is cached, it needs to be decremented (with correction) as well.

Removing the back element takes Θ(1) time.

get, set

Like fillable arrays, a valid index for get and set lies between 0 and size - 1. However, the value of the start index must be added to the given index and then corrected as necessary. For example, get becomes:

    function get(index)
        {
        var spot = correctIndex(index + startIndex);
        return store[spot];
        }

The code for set follows a similar pattern.

find

Find is similar to that of fillable arrays. Assuming the elements are unsorted, a modified linear traversal (see below) is used.

Traversals

Circular arrays support traversals similar to that of arrays, except that the actual starting (or ending) point is the start index while the actual ending (or starting point) is the end index. However, since the end index may be smaller than the start index, it becomes difficult to write a loop based upon these actual values. By basing the traversal on get (or set), then the starting (or ending) point is zero and the ending (or starting point) is the size - 1 and writing such a traversing loop is greatly simplified:

    for (i = 0; i < size; i += 1)
        println(get(i));

A right-to-left traversal is similar.

Concept Inventory

     
  1. In a circular array, the start index (after correction) can never equal the size.
    1. True
    2. False
     
  2. In a circular array, the start index (after correction) can never equal the capacity.  
     
     
  3. Suppose a circular array has size s, capacity c, and start index of i. Before correction, the next value to be added to the front of the array will be placed at index:
    1. s + i
    2. s - i
    3. i
    4. i - 1
    5. c - 1
    6. c - i
     
  4. Suppose for a circular array, the size is equal to the capacity. Can a value be added?
    1. Yes, there is room for one more value
    2. No, the array is completely full
     
  5. Suppose a circular array is empty. The size of the array is:
    1. zero
    2. one
    3. the length of the array
    4. the capacity of the array.

lusth@cs.ua.edu


Fillable Arrays Top Dynamic Arrays Contents