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
headpointer: Index of the first element - A
tailpointer: 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.