2.4 $\mathtt{ArrayDeque}$: Fast Deque Operations Using an Array

The $\mathtt{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 $\mathtt{ArrayDeque}$ data structure allows for efficient addition and removal at both ends. This structure implements the $\mathtt{List}$ interface using the same circular array technique used to represent an $\mathtt{ArrayQueue}$.

  array<T> a;
  int j;
  int n;

The $\mathtt{get(i)}$ and $\mathtt{set(i,x)}$ operations on an $\mathtt{ArrayDeque}$ are straightforward. They get or set the array element $\ensuremath{\mathtt{a[}}{\ensuremath{\mathtt{(j+i)}}\bmod \ensuremath{\mathtt{a.length}}}\ensuremath{\mathtt{]}}$.

  T get(int i) {
    return a[(j + i) % a.length];
  }
  T set(int i, T x) {
    T y = a[(j + i) % a.length];
    a[(j + i) % a.length] = x;
    return y;
  }

The implementation of $\mathtt{add(i,x)}$ is a little more interesting. As usual, we first check if $\mathtt{a}$ is full and, if necessary, call $\mathtt{resize()}$ to resize $\mathtt{a}$. Remember that we want this operation to be fast when $\mathtt{i}$ is small (close to 0) or when $\mathtt{i}$ is large (close to $\mathtt{n}$). Therefore, we check if $\ensuremath{\mathtt{i}}<\ensuremath{\mathtt{n}}/2$. If so, we shift the elements $\ensuremath{\mathtt{a[0]}},\ldots,\ensuremath{\mathtt{a[i-1]}}$ left by one position. Otherwise ( $\ensuremath{\mathtt{i}}\ge\ensuremath{\mathtt{n}}/2$), we shift the elements $\ensuremath{\mathtt{a[i]}},\ldots,\ensuremath{\mathtt{a[n-1]}}$ right by one position. See Figure 2.3 for an illustration of $\mathtt{add(i,x)}$ and $\mathtt{remove(x)}$ operations on an $\mathtt{ArrayDeque}$.

Figure 2.3: A sequence of $\mathtt{add(i,x)}$ and $\mathtt{remove(i)}$ operations on an $\mathtt{ArrayDeque}$. Arrows denote elements being copied.

  void add(int i, T x) {
    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;
      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 $\mathtt{add(i,x)}$ never has to shift more than $\min\{ \ensuremath{\mathtt{i}}, \ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}} \}$ elements. Thus, the running time of the $\mathtt{add(i,x)}$ operation (ignoring the cost of a $\mathtt{resize()}$ operation) is $O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$.

The $\mathtt{remove(i)}$ operation is similar. It either shifts elements $\ensuremath{\mathtt{a[0]}},\ldots,\ensuremath{\mathtt{a[i-1]}}$ right by one position or shifts the elements $\ensuremath{\mathtt{a[i+1]}},\ldots,\ensuremath{\mathtt{a[n-1]}}$ left by one position depending on whether $\ensuremath{\mathtt{i}}<\ensuremath{\mathtt{n}}/2$. Again, this means that $\mathtt{remove(i)}$ never spends more than $O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time to shift elements.

  T remove(int i) {
      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;
  }

2.4.1 Summary

The following theorem summarizes the performance of the $\mathtt{ArrayDeque}$ data structure:

Theorem 2..3   An $\mathtt{ArrayDeque}$ implements the $\mathtt{List}$ interface. Ignoring the cost of calls to $\mathtt{resize()}$, an $\mathtt{ArrayDeque}$ supports the operations

• $\mathtt{get(i)}$ and $\mathtt{set(i,x)}$ in $O(1)$ time per operation; and
• $\mathtt{add(i,x)}$ and $\mathtt{remove(i)}$ in $O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time per operation.

Furthermore, beginning with an empty $\mathtt{ArrayDeque}$, any sequence of $m$ $\mathtt{add(i,x)}$ and $\mathtt{remove(i)}$ operations results in a total of $O(m)$ time spent during all calls to $\mathtt{resize()}$.