Tracing the ArrayDeque

Let’s trace the same kind of mixed-end sequence on an ArrayDeque. The pictures use a capacity-5 array, so that wrapping happens early. As before, _ marks a null slot.

A fresh deque has front = 0 and size = 0:

┌───┬───┬───┬───┬───┐
│ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┘
  ↑
front

addFirst(4) moves front one slot left, wrapping from 0 to 4, then writes 4:

┌───┬───┬───┬───┬───┐
│ _ │ _ │ _ │ _ │ 4 │
└───┴───┴───┴───┴───┘
                  ↑
                front

addLast(9) writes at index(size), which is (4 + 1) % 5 = 0:

┌───┬───┬───┬───┬───┐
│ 9 │ _ │ _ │ _ │ 4 │
└───┴───┴───┴───┴───┘
  ↑               ↑
last            front

The deque contents are 4, 9. The deque is already wrapped.

addFirst(2) moves front from 4 to 3 and writes 2:

┌───┬───┬───┬───┬───┐
│ 9 │ _ │ _ │ 2 │ 4 │
└───┴───┴───┴───┴───┘
  ↑           ↑
last        front

Now getFirst() returns 2, and getLast() returns 9. Nothing changes.

removeLast() clears index(size - 1), which is (3 + 3 - 1) % 5 = 0, then decrements size:

┌───┬───┬───┬───┬───┐
│ _ │ _ │ _ │ 2 │ 4 │
└───┴───┴───┴───┴───┘
              ↑   ↑
            front last

addLast(6) writes at index(size), which is (3 + 2) % 5 = 0:

┌───┬───┬───┬───┬───┐
│ 6 │ _ │ _ │ 2 │ 4 │
└───┴───┴───┴───┴───┘
  ↑           ↑
last        front

removeFirst() clears slot 3 and moves front right to 4:

┌───┬───┬───┬───┬───┐
│ 6 │ _ │ _ │ _ │ 4 │
└───┴───┴───┴───┴───┘
  ↑               ↑
last            front

addFirst(7) moves front left to 3 and writes 7:

┌───┬───┬───┬───┬───┐
│ 6 │ _ │ _ │ 7 │ 4 │
└───┴───┴───┴───┴───┘
  ↑           ↑
last        front

At this point the deque contents are 7, 4, 6. Add one more item at the last end, addLast(8):

┌───┬───┬───┬───┬───┐
│ 6 │ 8 │ _ │ 7 │ 4 │
└───┴───┴───┴───┴───┘
      ↑       ↑
    last    front

And one more item at the first end, addFirst(1):

┌───┬───┬───┬───┬───┐
│ 6 │ 8 │ 1 │ 7 │ 4 │
└───┴───┴───┴───┴───┘
      ↑   ↑
    last front

The deque is full, and its contents are 1, 7, 4, 6, 8. If we now call addLast(3), grow copies those five items in deque order into a larger array, resets front to 0, and then writes 3 at index 5:

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 7 │ 4 │ 6 │ 8 │ 3 │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  ↑                   ↑
front               last