Next: 2.6 RootishArrayStack: A Space-Efficient Up: 2. Array-Based Lists Previous: 2.4 ArrayDeque: Fast Deque Contents
Next, we present another 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.
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
and
, 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,
,
of elements it contains. It doesn't need to, since it contains
elements. Nevertheless, when
analyzing the DualArrayDeque we will still use
to denote the number
of elements it contains.
int size() {
return front.size() + back.size();
}
The
ArrayStack contains list elements with indices
, but stores them in reverse order.
The
ArrayStack contains list elements with indices
in the normal order. In this way,
and
translate into appropriate calls to
or
on either
or
, which take 
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
, then it corresponds to the
element of
at position
, since the
elements of
are stored in reverse order.
Adding and removing elements from a DualArrayDeque is illustrated in
Figure 2.4. The
operation manipulates either
or
, 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
method performs rebalancing of the two ArrayStacks
and
, by calling the
method. The
implementation of
is described below, but for now it is
sufficient to know that
ensures that, unless
,
and
do not differ by more than a factor
of 3. In particular,
and
.
Next we analyze the cost of
, ignoring the cost of the
operation. If
, then
becomes
.
Since
is an ArrayStack, the cost of this is
, then
becomes
.
The cost of this is
Notice that the first case (2.1) occurs when
.
The second case (2.2) occurs when
. When
, we can't be sure whether the operation affects
or
, but in either case, the operation takes
time, since
and
. Summarizing the situation, we have
(ignoring the cost of the call to
) is
.
The
operation, and its analysis, is similar to the
operation.
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;
}
Finally, we study the
operation performed by
and
. This operation is used to ensure that neither
nor
gets too big (or too small). It ensures that, unless there
are fewer than 2 elements, each of
and
contain at least
elements. If this is not the case, then it moves elements between
them so that
and
contain exactly
elements and
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;
}
}
There is not much to analyze. If the
operation does
rebalancing, then it moves
elements and this takes
time. This is bad, since
is called with each call to
and
. However, the following lemma shows that, on
average,
only spends a constant amount of time per operation.
calls
to
and
are performed, then the total time spent
during all calls to
is 
.
is forced to shift elements,
then the number of
and
operations since the
last time
shifted any elements is at least
.
As in the proof of Lemma 2.1, this is sufficient
to prove that the total time spent by
is .
We will perform our analysis using the potential method. Define the potential of the DualArrayDeque as
or
that does not do any balancing can increase the potential
by at most 1.
Observe that, immediately after a call to
that shifts
elements, the potential, 
, is at most 1, since
Consider the situation immediately before a call to
that
shifts elements and suppose, without loss of generality, that
is shifting elements because
.
Notice that, in this case,
 |
 |
 |
|
 |
 |
||
|
 |
 |
|
 |
|
 |
 |
||
|
 |
||
|
 |
||
|
 |
or
since
the last time
shifted elements is at least
. This completes the proof.
The following theorem summarizes the performance of a DualArrayStack
and
, a DualArrayDeque
supports the operations
and
in time per operation; and
and
in
time
per operation.
and
operations results in a total of
time spent during all calls to
and
.opendatastructures.org