Java ArrayDeque addFirst and addLast

When you need a double-ended queue in Java, the ArrayDeque class provides constant-time insertion and removal at both ends. The methods addFirst and addLast are the primary insertion points, and understanding their behavior is essential for writing correct and efficient code. This article explains how java arraydeque addfirst addlast work, their contract, and where they fit in your data structure choices.

The Contract of addFirst and addLast

The ArrayDeque class implements the Deque interface. The addFirst(E e) method inserts an element at the front, shifting existing elements to the right. The addLast(E e) method inserts an element at the tail, preserving the order of existing elements. Both methods return void – they do not return a status. This means they are intended for operations where insertion is expected to succeed.

Unlike offerFirst and offerLast, which return a boolean indicating success, addFirst and addLast throw an exception if the operation fails. However, because ArrayDeque is resizable, the only failure condition is a null element.

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("first");
deque.addLast("last");
// deque now holds [first, last]

After these calls, iterating over the deque yields first then last. The addFirst call adds to the index that becomes the new head, while addLast appends to the tail.

The important thing to remember is that addFirst and addLast are equivalent to offerFirst and offerLast for an unbounded deque because capacity is not a constraint. The main difference is the contract: add methods throw on failure, offer methods do not.

What Happens When You Insert Null?

ArrayDeque does not allow null elements. Both addFirst(null) and addLast(null) throw a NullPointerException. This is a deliberate design choice because the deque uses null internally as a sentinel value to detect empty slots. If null were allowed, the algorithm that tracks the head and tail indices would break.

Consider this code:

ArrayDeque<String> deque = new ArrayDeque<>();
try {
    deque.addFirst(null);
} catch (NullPointerException e) {
    System.out.println("Null insertion rejected");
}

The exception is thrown immediately, and the deque remains unchanged. This behavior is consistent across all methods that insert elements, including offerFirst and offerLast, which also reject null despite returning false instead of throwing. Actually, the offer methods return false when you try to insert null, rather than throwing, as per the Deque interface contract. Verify this with your JDK version.

In practice, this means you must ensure that any element added to an ArrayDeque is non-null. If your application uses null to represent an absent value, you need a different collection, such as LinkedList, or you must replace null with a sentinel object.

Performance Characteristics of addFirst and addLast

Both addFirst and addLast run in amortized constant time. The ArrayDeque internally uses a circular array that doubles in size when it becomes full. The doubling process copies existing elements to a new array, which takes O(n) time, but this happens infrequently enough that the average cost per insertion remains O(1).

This performance is superior to LinkedList for most use cases. LinkedList also supports constant-time insertion at both ends, but it allocates a new node object for each element, resulting in more memory overhead and poorer cache locality. ArrayDeque stores elements contiguously, which often leads to better performance in practice.

However, the resizing behavior has a subtle implication. When the deque grows, the elements are copied, which temporarily doubles the memory usage. If you know you will insert many elements, you can pre-size the ArrayDeque using the constructor new ArrayDeque<>(initialCapacity) to avoid repeated resizing.

ArrayDeque<Integer> numbers = new ArrayDeque<>(10_000);
for (int i = 0; i < 10_000; i++) {
    numbers.addLast(i);
}

This allocates an array with enough space from the start, minimizing the number of resizing operations.

addFirst and addLast in Real-World Scenarios

The most common use of addFirst is implementing a stack. A stack that supports push and pop at the front can be built directly with addFirst and removeFirst. This yields a LIFO structure. Similarly, addLast combined with removeFirst creates a FIFO queue.

Consider a simple undo/redo system where you keep a history of actions. You can use addFirst to record the most recent action at the front, making it easy to traverse the history without shifting the entire collection.

Deque<String> actionHistory = new ArrayDeque<>();
actionHistory.addFirst("open file");
actionHistory.addFirst("edit line 5");
actionHistory.addFirst("save");
// The most recent is now at the head
String lastAction = actionHistory.removeFirst(); // "save"

Another common pattern is an event buffer. Producers add events to the tail with addLast, and consumers remove from the head with removeFirst. This preserves event order and allows efficient processing.

Comparing addFirst/addLast with Other Insertion Methods

The Deque interface provides several insertion variants: addFirst, offerFirst, addLast, offerLast. The add variants throw on failure, while the offer variants return a boolean. In an ArrayDeque, the only failure case is null, and the offer methods return false for null (or throw according to implementation details) but do not throw. The push method is an alias for addFirst, but it is semantically associated with stack operations.

Here is a quick comparison:

For a typical application where you control the input and know elements are non-null, addFirst and addLast are the clear choice because they communicate the assumption that the insertion will succeed.

Memory and Concurrency Considerations

ArrayDeque is not thread-safe. If multiple threads access a deque concurrently, and at least one thread modifies it, you must synchronize externally. The iterator returned by ArrayDeque is fail-fast: if the deque is modified after the iterator is created, the iterator throws ConcurrentModificationException when you call next().

When you need a thread-safe double-ended queue, consider using ConcurrentLinkedDeque or wrapping the ArrayDeque with Collections.synchronizedDeque(). The latter requires manual synchronization when iterating, as the iterator is not thread-safe even with the wrapper.

Memory-wise, ArrayDeque uses a backing array that never shrinks automatically. Once it has grown to a certain capacity, that memory is retained until the deque itself is garbage collected. If you frequently add and remove elements, the capacity can stay high, potentially retaining memory longer than necessary.

For long-lived deques with variable size, you might need to explicitly call trimToSize() to shrink the backing array. This method is not part of the Deque interface, but it is available on the ArrayDeque class.

ArrayDeque<String> deque = new ArrayDeque<>();
// ... many operations ...
deque.trimToSize();

This can reduce memory usage but at the cost of copying all elements to a new, smaller array.

Handling Capacity and Resizing

When you create an ArrayDeque with no arguments, it starts with a default capacity of 16 elements. Whenever you add an element that would fill the array, the deque allocates a new array twice the size of the current one, copies all elements, and then proceeds with the insertion. This resizing can be a source of latency if it happens frequently.

If you know the approximate maximum size your deque will reach, it is wise to pass an initial capacity to the constructor. The ArrayDeque(int numElements) constructor allocates an array with a capacity that is a power of two, at least as large as numElements.

// Holds at least 100 elements without resizing
ArrayDeque<Integer> deque = new ArrayDeque<>(100);

This is especially important for performance-sensitive code where you want to minimize resizing overhead.

When to Avoid addFirst and addLast

If you need to insert elements at an arbitrary index, ArrayDeque is not the right choice. Its add methods only work at the ends. For random insertions, you would need a list, such as ArrayList or LinkedList, though those have their own tradeoffs.

ArrayDeque also does not support indexed access. You cannot get element at position 5 without iterating. If you need frequent random access, use an ArrayList.

Null elements are another reason to avoid ArrayDeque. If your data model includes null as a valid value, you must either filter nulls or use a different collection.

Finally, if you need a bounded deque that rejects elements when full, ArrayDeque will not work because it is unbounded. In that case, consider a BlockingDeque implementation, such as LinkedBlockingDeque, which does not directly support addFirst when full, but offers methods like offerFirst with a timeout.

Verifying the Position of Elements

To confirm that addFirst and addLast place elements correctly, you can inspect the deque's head and tail. The getFirst() and getLast() methods return the elements at the ends without removing them. After a sequence of addFirst and addLast, these methods show the ordering.

ArrayDeque<String> deque = new ArrayDeque<>();
deque.addFirst("one");
deque.addLast("two");
deque.addFirst("zero"); // front
System.out.println(deque.getFirst()); // zero
System.out.println(deque.getLast());  // two

The deque now contains zero, one, two. The first element added (one) is now in the middle, shifted by subsequent addFirst calls. This demonstrates that addFirst prepends, while addLast appends.

This positional behavior is important when you use the deque as a buffer or as a collection where ordering matters. Confirming the head and tail helps prevent off-by-one errors in algorithms that rely on the order of elements.