Data Structures with Generic Types in Java/

...

/

DualArrayDeque: Building a Deque from Two Stacks

DualArrayDeque: Building a Deque from Two Stacks

Learn how to implement the DualArrayDeque data structure.

We'll cover the following...

Next, we present a data structure, the DualArrayDeque that achieves the same performance bounds as an ArrayDeque by using two ArrayStacks. 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.

Two ends of a DualArrayDeque

A DualArrayDeque represents a list using two ArrayStacks. Recall that an ArrayStack is fast when the operations on it modify elements near the end. A DualArrayDeque places two ArrayStacks, called front and back, back-to-back so that operations are fast at either end.

Press + to interact
List<T> front;
List<T> back;

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

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

The DualArrayDeque operations

The front ArrayStack stores the list elements whose indexes are 0,...,front.size() − 1, but stores them in reverse order. The back ArrayStack contains list elements with indexes in front.size(),...,size() − 1 in the normal order. In this way, get(i) and set(i, x) translate into appropriate calls to get(i) or set(i, x) on either front or back, which take O(1)O(1) time per operation.

Press + to interact
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 i < front.size(), then it corresponds to the element of front at position front.size() − i − 1, since the elements of front are stored in reverse order.

Visual demonstration

Adding and removing elements from a DualArrayDeque is illustrated below. Arrows denote elements being copied. Operations that result in a rebalancing by balance() are marked with an asterisk.

The add(i, x) operation manipulates either front or back, as appropriate:

Press + to interact
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 add(i, x) method performs rebalancing of the two ArrayStacks front and back, by calling the balance() method. The implementation of balance() is described below, but for now it is sufficient to know that balance() ensures that, unless size() < 2, front.size() and back.size() do not differ by more than a factor of 33. In particular, 3.front.size() ≥\ge back.size() and 3.back.size() ≥\ge front.size().

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

O(front.size()−(front.size()−i−1)+1)=O(i+1)(2.1)\tag{2.1} O(\text{front.size}()−(\text{front.size}()−i−1)+1)=O(i+1)

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

O(back.size()−(i−front.size())+1)=O(n−i+1)(2.2)\tag{2.2} O(\text{back.size}()−(i−\text{front.size}())+1)=O(n−i+1)

Notice that the first case (2.12.1 ...