Implementing ArrayDeque

Here is the Deque interface:

public interface Deque<T> {
  void addFirst(T item);  // throws IllegalArgumentException if item is null
  void addLast(T item);   // throws IllegalArgumentException if item is null
  void removeFirst();     // throws NoSuchElementException if the deque is empty
  void removeLast();      // throws NoSuchElementException if the deque is empty
  T getFirst();           // throws NoSuchElementException if the deque is empty
  T getLast();            // throws NoSuchElementException if the deque is empty
  boolean isEmpty();
}

ArrayDeque<T> implements the Deque<T> interface with a backing array used as a circular array. The item at the first end is at index front, and the items continue to the right from there, wrapping around to index 0. We do not store an index for the last end:

import java.util.NoSuchElementException;

public class ArrayDeque<T> implements Deque<T> {

  private T[] arr;    // the backing array, used as a circular array
  private int front;  // the index of the first item
  private int size;   // how many items are in the deque

  @SuppressWarnings("unchecked")
  public ArrayDeque() {
    arr = (T[]) new Object[10];
    front = 0;
    size = 0;
  }

  // Doubles the capacity of arr.
  private void grow() { /* to implement */ }

  // the operations go here
}

Solution

public boolean isEmpty() {
  return size == 0;
}

public T getFirst() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return arr[front];
}

public T getLast() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return arr[(front + size - 1) % arr.length];
}

Solution

public void removeFirst() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  arr[front] = null;
  front = (front + 1) % arr.length;
  size--;
}

public void removeLast() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  arr[(front + size - 1) % arr.length] = null;
  size--;
}

Only removeFirst changes front. removeLast only decrements size, and we compute the last index from front and size.

Solution

public void addFirst(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (size == arr.length) {
    grow();
  }
  front = (front + arr.length - 1) % arr.length;
  arr[front] = item;
  size++;
}

public void addLast(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (size == arr.length) {
    grow();
  }
  arr[(front + size) % arr.length] = item;
  size++;
}

Solution

Yes. grow copies the items starting at front and then resets front to 0. When the array is full, the slot before front holds the last item, so if front moved first, grow would copy the last item into index 0 and the new item would overwrite it. grow must come first; then front moves from 0 to the last index of the new array.

Solution

@SuppressWarnings("unchecked")
private void grow() {
  T[] bigger = (T[]) new Object[arr.length * 2];
  for (int i = 0; i < size; i++) {
    bigger[i] = arr[(front + i) % arr.length];
  }
  arr = bigger;
  front = 0;
}

Solution

isEmpty, getFirst, getLast, removeFirst, and removeLast are $O (1)$ : each reads or writes front, size, and at most one slot. addFirst and addLast are amortized $O (1)$ : each writes one slot, and the $O (n)$ grow runs only when the array is full, which happens at most once every $n$ adds because each grow doubles the capacity.

Solution

Both use $O (n)$ space. The array has more slots than items unless it is full, and it keeps its largest capacity after items are removed. LinkedDeque allocates exactly one node per item plus two sentinels, but each node also stores two references, prev and next.