Arrays Top Circular Arrays Contents

Fillable Arrays

Synopsis

Conceptually, a fillable array is composed of slots, which are either empty or filled. A filled slot holds an element. Each index of the array is associated with a slot and slots are filled preferentially from left to right. Thus, if zero-based counting is used, the first slot to be filled has index 0, the second has index one and so on.

Practically, a fillable array is usually implemented as an object with a normal array as a component. This array component is typically known as a store, since the values stored in a fillable array are actually stored in the component array.

Structure

The typical fillable array object has three components, plus operators:

    class fillable-array
        {
        var store = ?;          //points to a normal array
        var capacity = ?;       //set by the constructor
        var size = 0;
        //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.

Vocabulary

The terms used in describing a fillable array are:

store
The actual array where elements are stored.
slot
A spot in the store which may or may not hold an element. Each spot is associated with a unique index.
empty slot
A spot in the store that does not (yet) hold an element. A slot is empty if its index lies between size and capacity-1, inclusive.
filled slot
A spot in the store that holds an element. A slot is filled if its index lies between 0 and size-1, inclusive.
capacity
The maximum number of elements that can be placed in the store. Also, the length of the store array.
front
The leftmost value in the store.
back
The rightmost value in the store. 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 placed in the store. The size ranges from 0 (the store is completely empty) to the capacity of the store (the store is completely full). Also, with zero-based counting the size of the store is also an index that points to the next available slot.

Supports

Fillable arrays can be used to implement:

Important fillable arrays are:

Dependencies

Fillable arrays are implemented using arrays.

Operations

add-to-front

This operation places the given value in the first slot of the store. This necessitates shifting all previously added elements one slot to the right. Because add-to-front takes takes Θ(n) time, it is rarely implemented for fillable arrays.

remove-from-front

This operation removes the in the first slot of the store. This necessitates shifting all previously added elements one slot to the left, in order to fill the hole left by the removed element. Because remove-from-front takes takes Θ(n) time, it is rarely implemented for fillable arrays.

add-to-back

This operation adds the given value to the store. The value is stored to the immediate right of the previously added values or, in other words, the leftmost empty slot. The size is also incremented to reflect the fact that a value has been added.

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

Unlike adding a value to the front, adding a value at the back takes Θ(1) time, since no shifting of previously added values is needed.

remove-from-back

This operation removes the rightmost value in the store. This can be done simply by decrementing the size.

Removing a value from the back takes Θ(1) time.

get, set

These operations are similar to those of normal arrays, but a valid index lies between 0 and size - 1.

find

The find operation for fillable arrays, assuming the elements are unsorted, uses a traversal as shown below.

Traversals

Like normal arrays, fillable arrays are usually traversed from left to right. However, it is important to remember that the last filled slot has index size - 1, so any traversal has to take this into account:

    for (i = 0; i < size; i += 1)
        println(items[i])

Note that this traversal works from left to right. To insert in the middle of the array, a traversal of the upper part of the array must be performed from right to left, in order that shifting an element rightward does not trash the element to the immediate right. In a right-to-left traversal, the element to the immediate right has already been shifted rightward, leaving a hole; the element on the left is shifted into this hole, leaving a new hole. Thus, the hole appears to move leftward.

To delete from the middle of an array, a left-to-right traversal is performed.

Concept Inventory

     
  1. Suppose a fillable array has size s and capacity c. The next value to be added to the array will be placed at index:
    1. s
    2. c
    3. c - 1
    4. c + 1
    5. s - 1
     
  2. Suppose for a fillable 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
     
  3. Suppose a fillable 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


Arrays Top Circular Arrays Contents