2.4

The `ArrayQueue` from the previous section is a data structure for
representing a sequence that allows us to efficiently add to one
end of the sequence and remove from the other end. The `ArrayDeque`
data structure allows for efficient addition and removal at both ends.
This structure implements the `List` interface by using the same circular
array technique used to represent an `ArrayQueue`.

T[] a; int j; int n;

The
and
operations on an `ArrayDeque` are
straightforward. They get or set the array element
.

T get(int i) { if (i < 0 || i > n-1) throw new IndexOutOfBoundsException(); return a[(j+i)%a.length]; } T set(int i, T x) { if (i < 0 || i > n-1) throw new IndexOutOfBoundsException(); T y = a[(j+i)%a.length]; a[(j+i)%a.length] = x; return y; }

The implementation of
is a little more interesting. As
usual, we first check if
is full and, if necessary, call
to resize
. Remember that we want this operation to be
fast when
is small (close to 0) or when
is large (close to
). Therefore, we check if
. If so, we shift the
elements
left by one position. Otherwise
(
), we shift the elements
right
by one position. See Figure 2.3 for an illustration of
and
operations on an `ArrayDeque`.

void add(int i, T x) { if (i < 0 || i > n) throw new IndexOutOfBoundsException(); if (n+1 > a.length) resize(); if (i < n/2) { // shift a[0],..,a[i-1] left one position j = (j == 0) ? a.length - 1 : j - 1; //(j-1)mod a.length for (int k = 0; k <= i-1; k++) a[(j+k)%a.length] = a[(j+k+1)%a.length]; } else { // shift a[i],..,a[n-1] right one position for (int k = n; k > i; k--) a[(j+k)%a.length] = a[(j+k-1)%a.length]; } a[(j+i)%a.length] = x; n++; }

By doing the shifting in this way, we guarantee that never has to shift more than elements. Thus, the running time of the operation (ignoring the cost of a operation) is .

The implementation of the operation is similar. It either shifts elements right by one position or shifts the elements left by one position depending on whether . Again, this means that never spends more than time to shift elements.

T remove(int i) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); T x = a[(j+i)%a.length]; if (i < n/2) { // shift a[0],..,[i-1] right one position for (int k = i; k > 0; k--) a[(j+k)%a.length] = a[(j+k-1)%a.length]; j = (j + 1) % a.length; } else { // shift a[i+1],..,a[n-1] left one position for (int k = i; k < n-1; k++) a[(j+k)%a.length] = a[(j+k+1)%a.length]; } n--; if (3*n < a.length) resize(); return x; }

The following theorem summarizes the performance of the `ArrayDeque`
data structure:

- and in time per operation; and
- and in time per operation.

opendatastructures.org