Subsections


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.
\includegraphics{figs/arraydeque}

  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 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()}$.

opendatastructures.org