Course contentsShow
← Java
Lesson 1203 of 2,87027. Queue and Deque ImplementationsFree lesson

Internal Structure: Circular Array Buffer

Understanding ArrayDeque's backing array and how head/tail pointers enable efficient double-ended operations.

Internal Structure: Circular Array Buffer

What you'll learn: How ArrayDeque uses a circular array with head and tail pointers to efficiently add and remove elements from both ends.

The Core Idea

Unlike a regular array where elements start at index 0 and fill sequentially, ArrayDeque uses a circular array buffer. Imagine a clock face: when you reach the end (position 11), the next position wraps around to the beginning (position 0). This clever design allows the deque to add and remove elements at both ends without constantly shifting elements.

How It Works

ArrayDeque maintains three key pieces of state:

  • An array: The backing storage for elements
  • A head pointer: Index of the first element
  • A tail pointer: Index where the next element will be inserted

When you add to the front (addFirst), the head pointer moves backward (wrapping around if needed). When you add to the back (addLast), the tail pointer moves forward. Removing elements similarly adjusts these pointers.

The Circular Wrap-Around

The "circular" part is crucial. If head is at index 0 and you addFirst, the new head wraps to the end of the array. Similarly, if tail reaches the array's end, it wraps to index 0. This eliminates wasted space and makes both ends equally efficient.

The array may look like: [E, F, _, _, _, _, C, D] where head points to index 6 (element C) and tail points to index 2. Elements logically flow: C, D, E, F.

Why This Matters

This structure gives ArrayDeque O(1) performance for all double-ended operations without the overhead of linked nodes (like LinkedList). No element shifting, no node allocation—just pointer arithmetic.

Key Takeaway: ArrayDeque uses a circular array with head and tail pointers that wrap around, enabling constant-time insertions and removals at both ends without shifting elements.