Designing the ArrayDeque

We use the same representation idea as ArrayQueue: a backing array, a front index, and a size field.

private T[] arr;
private int front;
private int size;

The item i positions after the first end is at:

(front + i) % arr.length

From this formula, we get the positions we need:

The first item is at front.
The last item is at (front + size - 1) % arr.length.
The next free slot after the last item is at (front + size) % arr.length.

For addLast, we use the next free slot after the last item, exactly like ArrayQueue uses its computed back slot.

For addFirst, we need the slot before front, wrapping around to the end of the array if front is 0. Be careful in Java: (front - 1) % arr.length is negative when front is 0, because Java’s % is a remainder operator, not a mathematical modulo operator. Use this instead:

(front + arr.length - 1) % arr.length

Empty and Full

As with ArrayQueue, the size field is what lets us tell an empty deque from a full one.

Here is a wrapped deque in a capacity-5 array:

 addLast writes here
          ↓
┌───┬───┬───┬───┬───┐
│ 4 │ 6 │ _ │ _ │ 2 │
└───┴───┴───┴───┴───┘
      ↑           ↑
    last        front

The deque contents are 2, 4, 6. Here front is 4 and size is 3. The last item is at (4 + 3 - 1) % 5 = 1. The slot for addFirst is (4 + 5 - 1) % 5 = 3.

Growing the Array

When the array is full, we grow it exactly as ArrayQueue does: copy the items in deque order into a larger array and reset front to 0.

Operations and Complexity

isEmpty(), getFirst(), removeFirst(), and addLast(T item): These work as isEmpty, front, dequeue, and enqueue do in ArrayQueue. Each is $O (1)$ , and addLast is amortized $O (1)$ .

getLast(): Return the item at the last item’s index. This is $O (1)$ .

removeLast(): Clear the slot at the last item’s index and decrement size. front does not move. This is $O (1)$ .

addFirst(T item): Move front back one slot and write the item there, growing the array first when it is full. This is amortized $O (1)$ .