2. Array-Based Lists

In this chapter, we study implementations of the $\mathtt{List}$ and $\mathtt{Queue}$ interfaces where the underlying data is stored in an array, called the backing array. The following table summarizes the running times of operations for the data structures presented in this chapter:

	$\mathtt{get(i)}$/ $\mathtt{set(i,x)}$	$\mathtt{add(i,x)}$/ $\mathtt{remove(i)}$
$\mathtt{ArrayStack}$	$O(1)$	$O(\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}})$
$\mathtt{ArrayDeque}$	$O(1)$	$O(\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$
$\mathtt{DualArrayDeque}$	$O(1)$	$O(\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$
$\mathtt{RootishArrayStack}$	$O(1)$	$O(\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}})$

Data structures that work by storing data in a single array have many advantages and limitations in common:

• Arrays offer constant time access to any value in the array. This is what allows $\mathtt{get(i)}$ and $\mathtt{set(i,x)}$ to run in constant time.

• Arrays are not very dynamic. Adding or removing an element near the middle of a list means that a large number of elements in the array need to be shifted to make room for the newly added element or to fill in the gap created by the deleted element. This is why the operations $\mathtt{add(i,x)}$ and $\mathtt{remove(i)}$ have running times that depend on $\mathtt{n}$ and $\mathtt{i}$.

• Arrays cannot expand or shrink. When the number of elements in the data structure exceeds the size of the backing array, a new array needs to be allocated and the data from the old array needs to be copied into the new array. This is an expensive operation.

The third point is important. The running times cited in the table above do not include the cost of growing and shrinking the backing array. We will see that, if carefully managed, the cost of growing and shrinking the backing array does not add much to the cost of an average operation. More precisely, if we start with an empty data structure, and perform any sequence of $m$ $\mathtt{add(i,x)}$ or $\mathtt{remove(i)}$ operations, then the total cost of growing and shrinking the backing array, over the entire sequence of $m$ operations is $O(m)$. Although some individual operations are more expensive, the amortized cost, when amortized over all $m$ operations, is only $O(1)$ per operation.

In this chapter, and throughout this book, it will be convenient to have arrays that keep track of their size. The usual C++ arrays do not do this, so we have defined a class, $\mathtt{array}$, that keeps track of its length. The implementation of this class is straightforward. It is implemented as a standard C++ array, $\mathtt{a}$, and an integer, $\mathtt{length}$:

  T *a;
  int length;

The size of an $\mathtt{array}$ is specified at the time of creation:

  array(int len) {
    length = len;
    a = new T[length];
  }

The elements of an array can be indexed:

  T& operator[](int i) {
    assert(i >= 0 && i < length);
    return a[i];
  }

Finally, when one array is assigned to another, this is just a pointer manipulation that takes constant time:

  array<T>& operator=(array<T> &b) {
    if (a != NULL) delete[] a;
    a = b.a;
    b.a = NULL;
    length = b.length;
    return *this;
  }