Tracing the LinkedDeque

Let’s run a short sequence of operations and watch which real nodes get added and removed between the sentinels. We will use values similar to the stack and queue traces, but this time we will add and remove at both ends.

Start with an empty deque, which is just the two sentinels pointing at each other:

          ┌─────┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └─────┘

addFirst(4) splices a node between the two sentinels:

          ┌─────┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 4 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └─────┘

addLast(9) splices a node just before the back sentinel:

          ┌─────┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 4 │ ◀──▶ │ 9 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └─────┘

addFirst(2) splices a node just after the front sentinel:

          ┌─────┐      ┌───┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 2 │ ◀──▶ │ 4 │ ◀──▶ │ 9 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └───┘      └─────┘

Now getFirst() returns 2, and getLast() returns 9. Neither operation changes the deque.

removeLast() unlinks the last real node, 9. The node holding 4 and the back sentinel now point directly at each other:

          ┌─────┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 2 │ ◀──▶ │ 4 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └─────┘

addLast(6) adds at the last end again. It splices 6 just before the back sentinel:

          ┌─────┐      ┌───┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 2 │ ◀──▶ │ 4 │ ◀──▶ │ 6 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └───┘      └─────┘

Then removeFirst() unlinks the first real node, 2. The front sentinel and the node holding 4 now point directly at each other:

          ┌─────┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 4 │ ◀──▶ │ 6 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └─────┘

Finally, addFirst(7) splices 7 just after the front sentinel:

          ┌─────┐      ┌───┐      ┌───┐      ┌───┐      ┌─────┐
head ───▶ │ ░░░ │ ◀──▶ │ 7 │ ◀──▶ │ 4 │ ◀──▶ │ 6 │ ◀──▶ │ ░░░ │ ◀─── tail
          └─────┘      └───┘      └───┘      └───┘      └─────┘