Java ArrayDeque: How It Works, Example, vs. LinkedList and Stack

In this article, you will learn everything about the java.util.ArrayDeque class, which has been around since Java 6:

• What are the characteristics of ArrayDeque?
• When should you use it?
• How to use it (Java example)?
• What are the time complexities of the ArrayDeque operations?
• What is the difference between ArrayDeque and LinkedList?
• Why is ArrayDeque the better Stack?

This is where we are in the class hierarchy:

Since Java 21, Deque also extends the SequencedCollection interface. This gives ArrayDeque the reversed() method, which returns a reverse-ordered view of the deque. What this means for a deque is explained in the article Queue vs. Deque.

ArrayDeque Characteristics

ArrayDeque is based – as the name suggests – on an array. More precisely: on a circular array. How it works and how the array grows, I explain in the article “Ring Buffer (Circular Buffer).” We implement such a deque ourselves in a later part of the series, in the article “Implement a Deque Using a Circular Array in Java.”

The array underlying the ArrayDeque grows as needed but is not automatically trimmed down, nor can it be trimmed down manually. The default constructor creates an array with 17 slots. If you know in advance how many elements the deque will hold, pass that number to the constructor new ArrayDeque<>(n) – then the array does not have to grow until that number is reached.

null elements are not allowed (offerFirst(null) throws a NullPointerException) – which is why pollFirst() and peekFirst() can use the return value null to signal “deque empty” unambiguously.

The characteristics in detail:

Underlying data structure	Thread-safe?	Blocking/ non-blocking	Bounded/ unbounded	Iterator type
Array	No	Non-blocking	Unbounded	Fail-fast¹

¹ Fail-fast: The iterator throws a ConcurrentModificationException if elements are inserted into or removed from the deque during iteration – except through the iterator’s own remove() method.

Recommended Use Case

ArrayDeque is a good choice for single-threaded applications (and only for that). Keep in mind that the underlying array never shrinks.

For multi-threaded scenarios, you should use one of the following deques:

• ConcurrentLinkedDeque
• LinkedBlockingDeque

For guidance on deciding which to use, see the section “Deque Implementations in Java: Which One to Use?”.

ArrayDeque Example

The following Java code shows how to use ArrayDeque in Java. Here is what happens:

• Several random elements are inserted randomly at the head or the tail of the deque.
• The program displays whether the deque is empty and which elements it contains at the head and tail.
• Then, until the deque is empty, elements from a random side are removed and displayed.
• Finally, the status of the deque is displayed once again.

You can find the code in the ArrayDequeDemo class in the GitHub repository.

public class ArrayDequeDemo {
  static void main() {
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < 8; i++) {
      int element = ThreadLocalRandom.current().nextInt(10, 100);
      if (ThreadLocalRandom.current().nextBoolean()) {
        deque.offerFirst(element);
        System.out.println("deque.offerFirst(" + element + ") --> deque = " + deque);
      } else {
        deque.offerLast(element);
        System.out.println("deque.offerLast(" + element + ")  --> deque = " + deque);
      }
    }

    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
    System.out.println();

    while (!deque.isEmpty()) {
      if (ThreadLocalRandom.current().nextBoolean()) {
        System.out.println("deque.pollFirst() = " + deque.pollFirst()
            + " --> deque = " + deque);
      } else {
        System.out.println("deque.pollLast()  = " + deque.pollLast()
            + " --> deque = " + deque);
      }
    }

    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
  }
}

The output of the program looks like the following, for example:

deque.offerLast(25)  --> deque = [25]
deque.offerFirst(15) --> deque = [15, 25]
deque.offerFirst(26) --> deque = [26, 15, 25]
deque.offerFirst(39) --> deque = [39, 26, 15, 25]
deque.offerLast(25)  --> deque = [39, 26, 15, 25, 25]
deque.offerLast(50)  --> deque = [39, 26, 15, 25, 25, 50]
deque.offerFirst(95) --> deque = [95, 39, 26, 15, 25, 25, 50]
deque.offerLast(66)  --> deque = [95, 39, 26, 15, 25, 25, 50, 66]

deque.isEmpty()   = false
deque.peekFirst() = 95
deque.peekLast()  = 66

deque.pollFirst() = 95 --> deque = [39, 26, 15, 25, 25, 50, 66]
deque.pollLast()  = 66 --> deque = [39, 26, 15, 25, 25, 50]
deque.pollLast()  = 50 --> deque = [39, 26, 15, 25, 25]
deque.pollLast()  = 25 --> deque = [39, 26, 15, 25]
deque.pollFirst() = 39 --> deque = [26, 15, 25]
deque.pollLast()  = 25 --> deque = [26, 15]
deque.pollFirst() = 26 --> deque = [15]
deque.pollLast()  = 15 --> deque = []

deque.isEmpty()   = true
deque.peekFirst() = null
deque.peekLast()  = null

You can easily understand how ArrayDeque works by looking at the output.

ArrayDeque Time Complexity

(You can find an introduction to time complexity in the article “Big O Notation and Time Complexity – Easily Explained”.)

By using a circular array, the elements do not have to be relocated within the array, neither when inserting them into the deque nor when removing them.

Only when the array is full does ArrayDeque allocate a larger one and copy all elements over – which costs O(n). Since the array grows in proportion to its size, this happens rarely; averaged over many insertions, the cost per insertion remains constant. How the array grows is described in the section “Growing Buffer” of the ring buffer article.

Thus, the time complexity for both the enqueue and dequeue operations is: amortized O(1).

All operations that search for or remove an element in the middle – contains(), remove(Object), removeFirstOccurrence(), and removeLastOccurrence() – run in O(n), on the other hand.

ArrayDeque vs. LinkedList

An alternative Deque implementation is LinkedList, which I will introduce in the next part of the tutorial.

The difference between ArrayDeque and LinkedList is the underlying data structure: array or linked list.

ArrayDeque is faster than LinkedList in most cases. The class’s Javadoc says so as well: when used as a queue, ArrayDeque is “likely to be faster than LinkedList”. You can find the reasons for this in the article “Differences between Array and Linked List”.

ArrayDeque vs. Stack

For a stack, Deque offers the methods push(), pop(), and peek(), which work at the head of the deque. The Javadoc of the Deque interface recommends using a deque in preference to the legacy java.util.Stack class, and the Javadoc of ArrayDeque adds that the class is likely to be faster than Stack when used as a stack.

The reason: Stack extends Vector, whose methods are synchronized – even when only one thread uses the stack. ArrayDeque does without this synchronization. You can find further differences – iteration order, handling of an empty stack, interface instead of class – in the article Java Deque vs. Stack.

Summary

In this part of the tutorial series, you learned about the Deque implementation ArrayDeque and its characteristics. ArrayDeque is a good choice for single-threaded applications – as a queue, as a deque, and as a replacement for the Stack class.