How does Java's ArrayDeque work inside: its circular array, how head and tail move and wrap, how it grows, and why it refuses null?
answer
- a ring, not a shifting list
- one slot stays null
- insert: head steps down, tail steps up
- head equal to tail means empty
- a null cell is the empty marker
basics
~20 sArrayDeque is a circular Object array with head and tail indices that wrap at its ends, keeping one slot null between calls. An insert that fills that slot grows the array. Null is refused because a null cell means empty.
solid answer
~50 s`ArrayDeque` stores elements in a package-private `Object[] elements` with two package-private indices: `head` indexes the first element and `tail` the slot for the next element at the end. `elements[tail]` stays null between calls, so `head == tail` then means empty, and the class has no size field. `addLast` writes at `tail` and then steps it up; `addFirst`, which `push` calls, steps `head` down and then writes; both wrap at the array's ends, so nothing shifts on an end operation. When an insert makes the indices meet, the array is full for an instant and `grow` copies it, at JDK 27 as at 25, to `2n + 2` slots below length 64 and `1.5n` from there, sliding the head leg to the new end. Null throws `NullPointerException` because a null cell is how `poll` and `peek` recognise an empty deque.
code
java · 33 linesimport java.lang.reflect.Field;
import java.util.ArrayDeque;
public class RingInspect {
static void show(String what, ArrayDeque<?> d) throws Exception {
Object[] es = (Object[]) read(d, "elements");
System.out.printf("%-10s length=%d head=%d tail=%d size=%d%n",
what, es.length, read(d, "head"), read(d, "tail"), d.size());
}
static Object read(ArrayDeque<?> d, String field) throws Exception {
Field f = ArrayDeque.class.getDeclaredField(field);
f.setAccessible(true);
return f.get(d);
}
public static void main(String[] args) throws Exception {
var d = new ArrayDeque<Integer>();
show("new", d);
d.push(1); // head wraps down from 0 to 16, then the write
show("push", d);
d.add(2); // write at tail 0, then tail moves up
show("add", d);
for (int i = 3; i <= 16; i++) d.add(i);
show("16 held", d); // one null slot left, at tail
d.add(17); // the array is full for an instant, so grow runs
show("17th", d);
}
}go deeper
Recall that ArrayDeque is one array used as a ring, with head and tail indices that wrap around its ends, so nothing shifts when you add or remove at either end. Remember that it throws on null.
Explain the empty slot at tail, why head equal to tail means empty, which way push and add move the indices, how grow slides the head leg, and why a null cell is the empty marker.
Connect the internals to operations: presize a deque when you know the load, expect interior removal to be linear, and remember that a drained deque keeps its peak array, so a long-lived buffer may need replacing after a burst.
Weigh the default for a team: an unsynchronized ring is cheap and compact for one owning thread, but its iterators detect misuse only on a best-effort basis, so a queue shared across threads calls for a concurrent queue or deliberate external synchronization.
## The fields and the one rule A **circular array** treats its last index as adjacent to its first, so elements can enter and leave at either end without the others shifting. `java.util.ArrayDeque` is that structure, resized when it fills up: | Member | Declared as | Role | |---|---|---| | `elements` | package-private `transient Object[]` | the cells; a cell not holding an element is null | | `head` | package-private `transient int` | index of the first element; equals `tail` when empty | | `tail` | package-private `transient int` | index where `addLast` writes next; that cell is null | The rule behind everything is the **empty slot at tail**. The source's debugging method `checkInvariants` puts it in a comment: `Use head and tail fields with empty slot at tail strategy. head == tail disambiguates to "empty".` - **No size field.** `size()` computes the circular distance from `head` to `tail`, and `isEmpty()` compares them. - **An array of length n holds n - 1 elements.** `new ArrayDeque<>()` allocates `new Object[16 + 1]`, and `new ArrayDeque<>(n)` normally allocates `n + 1`, or one slot when `n` is below 1. - **At JDK 27, lengths need not be powers of two.** The default run is 17, 36, 74, and the package-private `inc` and `dec` helpers wrap with a comparison, not a bit mask. ## How head and tail move ```java // ArrayDeque.addLast, after its null check es[tail] = e; if (head == (tail = inc(tail, es.length))) grow(1); // ArrayDeque.addFirst, after its null check es[head = dec(head, es.length)] = e; if (head == tail) grow(1); ``` | Calls | End | What happens | |---|---|---| | `addLast`, `add`, `offer`, `offerLast` | tail | write at `tail`, then `tail` steps up | | `addFirst`, `push`, `offerFirst` | head | `head` steps down, then write | | `pollFirst`, `poll`, `removeFirst`, `remove()`, `pop` | head | read at `head`, null the cell, `head` steps up | | `pollLast`, `removeLast` | tail | read just below `tail`, null the cell, `tail` steps down | Stepping up from the last index gives 0, and stepping down from 0 gives the last index. What follows from that: - **A stack grows downward.** On a new deque, `push` wraps `head` from 0 to 16, so the first element lands in the array's last slot. - **A queue circles.** `add` and `poll` chase each other: 100 add-then-poll pairs on a default deque at JDK 27 left length 17 with both indices at 15. - **End operations do not shift**, so they run in what the Javadoc calls amortized constant time; the occasional copy is the amortized part. - **Interior removal does shift.** `remove(Object)` and `iterator.remove()` use package-private `delete(i)`, which moves whichever side of the gap holds fewer elements. The Javadoc lists them as linear. ## Growth 1. An insert writes first and checks after. If the indices now meet, the array is full for an instant, the exception that a comment in `grow` flags: "Exceptionally, here tail == head needs to be disambiguated". 2. Private `grow` computes `jump` as `(oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)`, and the new length is old plus `jump`. 3. `Arrays.copyOf` keeps every element at its old index in the longer array. 4. If `tail < head`, or `tail == head` with a non-null `es[head]`, the leg from `head` to the old end slides to the new end. The vacated cells are nulled and `head` moves with the leg, while `tail` stays. The free cells now sit between `tail` and `head`, so the ring simply has more room. - **Lengths** run 17, 36, 74, 111, 166 on JDK 27, and a default deque grows on its 17th element. - **Bulk loads presize.** `addAll` calls `grow` once for the whole shortfall: 1,000 elements into a default deque gave length 1,001. `ArrayDeque(Collection)` allocates `c.size() + 1`. Both then call `addLast` per element. - **Nothing shrinks the array.** Polled cells are nulled, so elements become collectible, and `clear` also resets both indices to 0, but the length stays. - **Not a contract.** The class Javadoc says deques "grow as necessary". The numbers come from private code at JDK 27, and `ArrayDeque.java` is identical at JDK 25. ## Why null is refused Inside this class a null cell is the empty marker: - `pollFirst` tests only `if (e != null)`, and `peekFirst` returns the cell as it is. - `removeFirst` and `getFirst` turn a null read into `NoSuchElementException`. - `grow` checks `es[head] != null` to tell a full array from an empty one. - An iterator's `next` reads through package-private `nonNullElementAt`, which throws `ConcurrentModificationException` on a null cell. A stored null at `head` would make a non-empty deque look empty: `poll` would return null without moving `head`, stranding everything behind it. The contract says this one level up. `ArrayDeque`'s Javadoc states "Null elements are prohibited", and `Deque`'s says implementations are "strongly encouraged" to prohibit null, because null is a special return value meaning empty. That is encouragement rather than a rule: `Queue`'s Javadoc names `LinkedList` as an implementation that allows null. | Call on an empty `ArrayDeque` | Result | |---|---| | `add(null)`, `offer(null)`, `push(null)` | `NullPointerException` | | `poll()`, `peek()` | `null` | | `pop()`, `removeFirst()`, `getFirst()` | `NoSuchElementException` | | `contains(null)`, `remove((Object) null)` | `false` | `offer(null)` throws rather than returning `false`: here `offer` returns `true` or throws, because the deque has no capacity limit to refuse on.
- Why does a new ArrayDeque used as a stack put its first element in the array's last slot?`push` is `addFirst`, which steps `head` down before writing, and on the default 17-slot array `dec(0, 17)` wraps to 16. Later pushes keep moving down and `pop` steps back up. It costs nothing, since both directions are index arithmetic. It also means iteration, which runs from `head` to `tail`, visits the stack from top to bottom.
- ArrayDeque's Javadoc calls its iterators fail-fast, yet the class has no modCount field, so how do they detect modification?`next` reads through package-private `nonNullElementAt`, which throws `ConcurrentModificationException` on a null cell; a source comment says this does not catch all comodifications but does catch ones that corrupt traversal. `forEachRemaining` instead checks the indices against what it expected, before and after its loop. On JDK 27, over three elements, one `add` that forces growth during a for-each throws, while one `poll` finishes silently. That fits the Javadoc's warning that fail-fast is best-effort, for detecting bugs.
- What happens to an ArrayDeque's memory after a burst of elements has been drained?The elements become collectible because polling nulls their cells, but the array keeps its length: no method shrinks it, and `clear` only nulls the cells and resets `head` and `tail` to 0. A long-lived deque that once held a million elements keeps an array that long. If that matters, replace the deque with a new instance after the burst.
- How does ArrayDeque remove an element from the middle, and what does that cost?`remove(Object)` scans from head to tail with `equals`, then package-private `delete(i)` closes the gap by moving whichever side holds fewer elements with `System.arraycopy`, handling the wrap, and steps `head` up or `tail` down. The Javadoc lists this as linear time, so the constant-time claim for the ring covers its two ends, not its interior.
A row of numbered lockers treated as a ring, with one attendant at the front and one at the back. Items stay where they are and only the attendants walk. Between jobs one locker between them stays empty, so the two meeting means nothing is stored; an item that takes that last locker sends everything to a longer row at once.
- At JDK 27, ArrayDeque's capacity is always a power of two, and its indices wrap with a bit mask.
- Removing from the head of an ArrayDeque shifts the remaining elements one slot toward index 0.
- offer(null) on an ArrayDeque returns false, because offer methods report failure without throwing.
- An ArrayDeque's array can fill every slot, so head equal to tail may mean full between calls.
- ArrayDeque keeps a size field that tells it when the array is empty or full.
- Refusing null is only API style; nothing inside ArrayDeque depends on it.
- java.util.ArrayDeque
- Java 1.6
Assumes JDK 27; the array lengths come from private code rather than the API contract, and ArrayDeque.java is identical at JDK 25.
context
- ArrayDeque (Java SE 27 & JDK 27)docs.oracle.com
- Deque (Java SE 27 & JDK 27)docs.oracle.com
- ArrayDeque.java at jdk-27-gagithub.com