Java ArrayDeque – What is it for? + How to use it?

In this article, you will learn everything about the java.util.ArrayDeque class:

• 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?

This is where we are in the class hierarchy:

ArrayDeque Characteristics

ArrayDeque is based – as the name suggests – on an array. More precisely: on a circular array. You’ll find out exactly how it works when we implement a Deque with an array in a later part of the series.

The array underlying the ArrayDeque grows as needed but is not automatically trimmed down, nor can it be trimmed down manually.

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.

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 article “Deque Implementations – 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 {
  public static void main(String[] args) {
    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.

The cost of the enqueue and dequeue operations is thus independent of the number of elements in the deque, i.e., constant.

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

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. You can find the reasons for this in the article “Differences between Array and Linked List”.

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.