# 2.5: DualArrayDeque - Building a Deque from Two Stacks

- Page ID
- 8441

Next, we present a data structure, the `DualArrayDeque` that achieves the same performance bounds as an `ArrayDeque` by using two `ArrayStack`s. Although the asymptotic performance of the `DualArrayDeque` is no better than that of the `ArrayDeque`, it is still worth studying, since it offers a good example of how to make a sophisticated data structure by combining two simpler data structures.

A `DualArrayDeque` represents a list using two `ArrayStack`s. Recall that an `ArrayStack` is fast when the operations on it modify elements near the end. A `DualArrayDeque` places two `ArrayStack`s, called \(\mathtt{front}\) and \(\mathtt{back}\), back-to-back so that operations are fast at either end.

List<T> front; List<T> back;

A `DualArrayDeque` does not explicitly store the number, \(\mathtt{n}\), of elements it contains. It doesn't need to, since it contains \(\mathtt{n}=\texttt{front.size()} + \texttt{back.size()}\) elements. Nevertheless, when analyzing the `DualArrayDeque` we will still use \(\mathtt{n}\) to denote the number of elements it contains.

int size() { return front.size() + back.size(); }

The \(\mathtt{front}\) `ArrayStack` stores the list elements that whose indices are \(0,\ldots,\texttt{front.size()}-1\), but stores them in reverse order. The \(\mathtt{back}\) `ArrayStack` contains list elements with indices in \(\texttt{front.size()},\ldots,\mathtt{size()}-1\) in the normal order. In this way, \(\mathtt{get(i)}\) and \(\mathtt{set(i,x)}\) translate into appropriate calls to \(\mathtt{get(i)}\) or \(\mathtt{set(i,x)}\) on either \(\mathtt{front}\) or \(\mathtt{back}\), which take \(O(1)\) time per operation.

T get(int i) { if (i < front.size()) { return front.get(front.size()-i-1); } else { return back.get(i-front.size()); } } T set(int i, T x) { if (i < front.size()) { return front.set(front.size()-i-1, x); } else { return back.set(i-front.size(), x); } }

Note that if an index \(\mathtt{i}<\texttt{front.size()}\), then it corresponds to the element of \(\mathtt{front}\) at position \(\texttt{front.size()}-\mathtt{i}-1\), since the elements of \(\mathtt{front}\) are stored in reverse order.

Adding and removing elements from a `DualArrayDeque` is illustrated in Figure \(\PageIndex{1}\). The \(\mathtt{add(i,x)}\) operation manipulates either \(\mathtt{front}\) or \(\mathtt{back}\), as appropriate:

void add(int i, T x) { if (i < front.size()) { front.add(front.size()-i, x); } else { back.add(i-front.size(), x); } balance(); }

The \(\mathtt{add(i,x)}\) method performs rebalancing of the two `ArrayStack`s \(\mathtt{front}\) and \(\mathtt{back}\), by calling the \(\mathtt{balance()}\) method. The implementation of \(\mathtt{balance()}\) is described below, but for now it is sufficient to know that \(\mathtt{balance()}\) ensures that, unless \(\mathtt{size()}<2\), \(\texttt{front.size()}\) and \(\texttt{back.size()}\) do not differ by more than a factor of 3. In particular, \(3\cdot\texttt{front.size()} \ge \texttt{back.size()}\) and \(3\cdot\texttt{back.size()} \ge \texttt{front.size()}\).

Next we analyze the cost of \(\mathtt{add(i,x)}\), ignoring the cost of calls to \(\mathtt{balance()}\). If \(\mathtt{i}<\texttt{front.size()}\), then \(\mathtt{add(i,x)}\) gets implemented by the call to \(\texttt{front.add(front.size()}\mathtt{-i-1,x)}\). Since \(\mathtt{front}\) is an `ArrayStack`, the cost of this is

\[O(\texttt{front.size()}-(\texttt{front.size()}-\mathtt{i}-1)+1) = O(\mathtt{i}+1) \enspace .\label{das-front}\]

On the other hand, if \(\mathtt{i}\ge\texttt{front.size()}\), then \(\mathtt{add(i,x)}\) gets implemented as \(\mathtt{back\texttt{.}add(i-front\texttt{.}size(),x)}\). The cost of this is

\[O(\texttt{back.size()}-(\mathtt{i}-\texttt{front.size()})+1) = O(\mathtt{n}-\mathtt{i}+1) \enspace .\label{das-back}\]

Notice that the first case (\(\ref{das-front}\)) occurs when \(\mathtt{i}<\mathtt{n}/4\). The second case (\(\ref{das-back}\)) occurs when \(\mathtt{i}\ge 3\mathtt{n}/4\). When \(\mathtt{n}/4\le\mathtt{i}<3\mathtt{n}/4\), we cannot be sure whether the operation affects \(\mathtt{front}\) or \(\mathtt{back}\), but in either case, the operation takes \(O(\mathtt{n})=O(\mathtt{i})=O(\mathtt{n}-\mathtt{i})\) time, since \(\mathtt{i}\ge \mathtt{n}/4\) and \(\mathtt{n}-\mathtt{i}>\mathtt{n}/4\). Summarizing the situation, we have

Running time of \(\mathtt{add(i,x)} \le

\left\{

\begin{array}{ll}

O(1+\mathtt{i})&\text{if $\mathtt{i} < \mathtt{n}/4$}\\

O(\mathtt{n})&\text{if $\mathtt{n}/4 \le \mathtt{i} < 3\mathtt{n}/4$}\\

O(1+\mathtt{n}-\mathtt{i})&\text{if $\mathtt{i} \ge 3\mathtt{n}/4$}

\end{array}\right.\)

Thus, the running time of \(\mathtt{add(i,x)}\), if we ignore the cost of the call to \(\mathtt{balance()}\), is \(O(1+\min\{\mathtt{i}, \mathtt{n}-\mathtt{i}\})\).

The \(\mathtt{remove(i)}\) operation and its analysis resemble the \(\mathtt{add(i,x)}\) operation and analysis.

T remove(int i) { T x; if (i < front.size()) { x = front.remove(front.size()-i-1); } else { x = back.remove(i-front.size()); } balance(); return x; }

## \(\PageIndex{1}\) Balancing

Finally, we turn to the \(\mathtt{balance()}\) operation performed by \(\mathtt{add(i,x)}\) and \(\mathtt{remove(i)}\). This operation ensures that neither \(\mathtt{front}\) nor \(\mathtt{back}\) becomes too big (or too small). It ensures that, unless there are fewer than two elements, each of \(\mathtt{front}\) and \(\mathtt{back}\) contain at least \(\mathtt{n}/4\) elements. If this is not the case, then it moves elements between them so that \(\mathtt{front}\) and \(\mathtt{back}\) contain exactly \(\lfloor\mathtt{n}/2\rfloor\) elements and \(\lceil\mathtt{n}/2\rceil\) elements, respectively.

void balance() { int n = size(); if (3*front.size() < back.size()) { int s = n/2 - front.size(); List<T> l1 = newStack(); List<T> l2 = newStack(); l1.addAll(back.subList(0,s)); Collections.reverse(l1); l1.addAll(front); l2.addAll(back.subList(s, back.size())); front = l1; back = l2; } else if (3*back.size() < front.size()) { int s = front.size() - n/2; List<T> l1 = newStack(); List<T> l2 = newStack(); l1.addAll(front.subList(s, front.size())); l2.addAll(front.subList(0, s)); Collections.reverse(l2); l2.addAll(back); front = l1; back = l2; } }

Here there is little to analyze. If the \(\mathtt{balance()}\) operation does rebalancing, then it moves \(O(\mathtt{n})\) elements and this takes \(O(\mathtt{n})\) time. This is bad, since \(\mathtt{balance()}\) is called with each call to \(\mathtt{add(i,x)}\) and \(\mathtt{remove(i)}\). However, the following lemma shows that, on average, \(\mathtt{balance()}\) only spends a constant amount of time per operation.

*If an empty DualArrayDeque is created and any sequence of \(m\ge 1\) calls to \(\mathtt{add(i,x)}\) and \(\mathtt{remove(i)}\) are performed, then the total time spent during all calls to \(\mathtt{balance()}\) is \(O(m)\).*

*Proof*. We will show that, if \(\mathtt{balance()}\) is forced to shift elements, then the number of \(\mathtt{add(i,x)}\) and \(\mathtt{remove(i)}\) operations since the last time any elements were shifted by \(\mathtt{balance()}\) is at least \(\mathtt{n}/2-1\). As in the proof of Lemma 2.1.1, this is sufficient to prove that the total time spent by \(\mathtt{balance()}\) is \(O(m)\).

We will perform our analysis using a technique knows as the potential method. Define the potential, \(\Phi\), of the `DualArrayDeque` as the difference in size between \(\mathtt{front}\) and \(\mathtt{back}\):

\[ \Phi = \vert\texttt{front.size()} - \texttt{back.size()}\vert \enspace . \nonumber\]

The interesting thing about this potential is that a call to \(\mathtt{add(i,x)}\) or \(\mathtt{remove(i)}\) that does not do any balancing can increase the potential by at most 1.

Observe that, immediately after a call to \(\mathtt{balance()}\) that shifts elements, the potential, \(\Phi_0\), is at most 1, since

\[ \Phi_0 = \left\vert\lfloor\mathtt{n}/2\rfloor-\lceil\mathtt{n}/2\rceil\right\vert\le 1 \enspace .\nonumber\]

Consider the situation immediately before a call to \(\mathtt{balance()}\) that shifts elements and suppose, without loss of generality, that \(\mathtt{balance()}\) is shifting elements because \(3\texttt{front.size()} < \texttt{back.size()}\). Notice that, in this case,

\[\begin{align}

\mathtt{n}

&= \texttt{front.size()}+\texttt{back.size()}\nonumber\\

&< \texttt{back.size()}/3+\texttt{back.size()}\nonumber\\

&= \frac{4}{3}\texttt{back.size()}\nonumber

\end{align}\nonumber\]

Furthermore, the potential at this point in time is

\[\begin{align}

\Phi_1

&= \texttt{back.size()} - \texttt{front.size()}\nonumber\\

&> \texttt{back.size()} - \texttt{back.size()}/3\nonumber\\

&= \frac{2}{3}\texttt{back.size()}\nonumber\\[3pt]

&> \frac{2}{3}\times\frac{3}{4}\mathtt{n}\nonumber\\

&= \mathtt{n}/2\nonumber

\end{align}\nonumber\]

Therefore, the number of calls to \(\mathtt{add(i,x)}\) or \(\mathtt{remove(i)}\) since the last time \(\mathtt{balance()}\) shifted elements is at least \(\Phi_1-\Phi_0> \mathtt{n}/2-1\). This completes the proof.

## \(\PageIndex{2}\) Summary

The following theorem summarizes the properties of a `DualArrayDeque`:

*A DualArrayDeque implements the List interface. Ignoring the cost of calls to \(\mathtt{resize()}\) and \(\mathtt{balance()}\), a DualArrayDeque 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 DualArrayDeque, 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()}\) and \(\mathtt{balance()}\).*