The Circular Array for a Deque

First end at index 0: addLast is $O(1)$ amortized and removeLast is $O(1)$, but addFirst and removeFirst are $O(n)$, because all the other items shift one slot. Last end at index 0: addFirst is $O(1)$ amortized and removeFirst is $O(1)$, but addLast and removeLast are $O(n)$. Either way, the two operations at one end cost $O(n)$.

1. front, which is 6.
2. (front + size - 1) % arr.length, which is (6 + 2) % 8, that is, 0.
3. (front + size) % arr.length, which is (6 + 3) % 8, that is, 1.
4. (front + arr.length - 1) % arr.length, which is (6 + 7) % 8, that is, 5.

It fails when front is 0. Java’s % keeps the sign of the left operand, so -1 % arr.length is -1, which is not a valid index. The fix is to add arr.length before taking the remainder: (front + arr.length - 1) % arr.length, which gives arr.length - 1 when front is 0.

  0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ W │ _ │ _ │ K │ M │
└───┴───┴───┴───┴───┘
      ↑   ↑   ↑
      │   │ front
      │ addFirst
   addLast

K is at index 3, M at index 4, and W wraps to index 0. The next addFirst writes at index 2, and the next addLast writes at index 1.