ArrayDeque

ArrayDeque is a resizable-array implementation of a double-ended queue (deque). It provides constant time insertion and removal at both ends and supports iteration. In Java, ArrayDeque is part of java.util and is intended as a high-performance replacement for LinkedList when a deque is needed. It does not permit null elements and is not thread-safe.

Internally, elements are stored in a circular array. The deque maintains indices for the head and tail. When the underlying array fills, the implementation grows the array capacity, typically doubling the size. The new array is copied and the head offset is adjusted.

Common operations include addFirst, addLast (or offerFirst, offerLast), removeFirst, removeLast (or pollFirst, pollLast), getFirst, getLast, peekFirst, peekLast, and size/isEmpty. These operations run in amortized constant time. There is no direct random access by index; you must traverse from an end or use an iterator. Null elements are not allowed.

Because it uses an array and contiguous storage, it tends to have better locality and performance than a linked-list-based deque for typical workloads. It is best used when you need a lightweight, non-synchronized deque. If multiple threads share a deque, external synchronization is required.