2.4 : Fast Deque Operations Using an Array

The 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 data structure allows for efficient addition and removal at both ends. This structure implements the interface by using the same circular array technique used to represent an .

array<T> a; int j; int n;

The and operations on an are straightforward. They get or set the array element .

T get(int i) { return a[(j + i) % a.length]; } T set(int i, T x) { T y = a[(j + i) % a.length]; a[(j + i) % a.length] = x; return y; }

The implementation of is a little more interesting. As usual, we first check if is full and, if necessary, call to resize . Remember that we want this operation to be fast when is small (close to 0) or when is large (close to ). Therefore, we check if . If so, we shift the elements left by one position. Otherwise ( ), we shift the elements right by one position. See Figure 2.3 for an illustration of and operations on an .

void add(int i, T x) { 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; 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 never has to shift more than elements. Thus, the running time of the operation (ignoring the cost of a operation) is .

The implementation of the operation is similar. It either shifts elements right by one position or shifts the elements left by one position depending on whether . Again, this means that never spends more than time to shift elements.

T remove(int i) { 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; }

The following theorem summarizes the performance of the data structure:

- and in time per operation; and
- and in time per operation.

opendatastructures.org