Skip to main content
Engineering LibreTexts

2.4: ArrayDeque - Fast Deque Operations Using an Array

  • Page ID
    8440
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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 \(\mathtt{get(i)}\) and \(\mathtt{set(i,x)}\) operations on an ArrayDeque are straightforward. They get or set the array element \(\mathtt{a[}{\mathtt{(j+i)}\bmod\texttt{a.length}}\mathtt{]}\).

        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 \(\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 \(\mathtt{i}<\mathtt{n}/2\). If so, we shift the elements \(\mathtt{a[0]},\ldots,\mathtt{a[i-1]}\) left by one position. Otherwise ( \(\mathtt{i}\ge\mathtt{n}/2\)), we shift the elements \(\mathtt{a[i]},\ldots,\mathtt{a[n-1]}\) right by one position. See Figure \(\PageIndex{1}\) for an illustration of \(\mathtt{add(i,x)}\) and \(\mathtt{remove(x)}\) operations on an ArrayDeque.

    arraydeque.png
    Figure \(\PageIndex{1}\): A sequence of \(\mathtt{add(i,x)}\) and \(\mathtt{remove(i)}\) operations on an ArrayDeque. Arrows denote elements being copied.
        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 \(\mathtt{add(i,x)}\) never has to shift more than \(\min\{ \mathtt{i}, \mathtt{n}-\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\{\mathtt{i},\mathtt{n}-\mathtt{i}\})\).

    The implementation of the \(\mathtt{remove(i)}\) operation is similar. It either shifts elements \(\mathtt{a[0]},\ldots,\mathtt{a[i-1]}\) right by one position or shifts the elements \(\mathtt{a[i+1]},\ldots,\mathtt{a[n-1]}\) left by one position depending on whether \(\mathtt{i}<\mathtt{n}/2\). Again, this means that \(\mathtt{remove(i)}\) never spends more than \(O(1+\min\{\mathtt{i},\mathtt{n}-\mathtt{i}\})\) 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;
        }
    

    \(\PageIndex{1}\) Summary

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

    Theorem \(\PageIndex{1}\).

    An ArrayDeque implements the List interface. Ignoring the cost of calls to \(\mathtt{resize()}\), an 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\{\mathtt{i},\mathtt{n}-\mathtt{i}\})\) time per operation.

    Furthermore, beginning with an empty ArrayDeque, performing 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()}\).


    2.4: ArrayDeque - Fast Deque Operations Using an Array is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin.

    • Was this article helpful?