Next: 2.6 RootishArrayStack: A Space-Efficient Up: 2. Array-Based Lists Previous: 2.4 ArrayDeque: Fast Deque Contents Index
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.
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 stores the list elements that whose indices
are
, but stores them in reverse order.
The
ArrayStack contains list elements with indices
in
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:
![\includegraphics[scale=0.90909]{figs/dualarraydeque}](img342.png)
|
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 calls to
. If
, then
gets implemented
by the call to
. Since
is an
ArrayStack, the cost of this is
, then
gets
implemented as
. The cost of this is
Notice that the first case (2.1) occurs when
.
The second case (2.2) occurs when
. When
, we cannot be sure whether the operation affects
or
, but in either case, the operation takes
time, since
and
. Summarizing the situation, we have
, if we ignore the cost of the call
to
, is
.
The
operation and its analysis resemble the
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;
}
Finally, we turn to the
operation performed by
and
. This operation ensures that neither
nor
becomes too big (or too small). It ensures that, unless there are fewer
than two 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;
}
}
Here there is little 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 any elements were shifted by
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 a technique knows as the
potential method.
Define the potential, 
, of the
DualArrayDeque as the difference in size between
and
:
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 properties of a DualArrayDeque:
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