ArrayDeque in Java

Table of Contents

The ArrayDeque is a class in Java that implements the Deque and Queue interface. This is a special class that implements a double-ended queue data structure where it can insert and remove elements from both ends. It supports in implementation of a resizable array that grows automatically.

Features

The ArrayDeque in Java does not have any limitation on capacity
It is not thread-safe which means it does not support concurrent multiple thread access
We cannot store null values in an ArrayDeque in Java
It implements both Stack and queue and its performance is faster than Stack and LinkedList
It has constant time complexity for most of the methods.

Interfaces implemented by the ArrayDeque class

The ArrayDeque class in Java implements the below interfaces:

Deque
Queue

ArrayDeque in Java

Constructors

Constructor	Description
ArrayDeque()	Creates a default empty ArrayDeque with capacity 16
ArrayDeque(Collection c)	Creates an ArrayDeque with the specified elements in the Collection
ArrayDeque(int numberOfElemens)	Creates an empty ArrayDeque with capacity specified in the parameter

Methods

Since the ArrayDeque in Java implements the Deque interface, it inherits all the methods in the Deque interface as listed below.

Method	Description	Parameter
Boolean add(Element e)	Adds the specified element to the end of the deque.	e - the element to be added. Return value - True
Boolean addAll(Collection c)	Adds a collection of specified elements to the deque.	c - collection of elements to be added Return value - true
void addFirst(Element e)	Inserts an element at the beginning of the deque	e - the element to be inserted
void addLast(Element e)	Inserts an element at the end of the deque	e - the element to be inserted
void clear()	Clears all the elements in the deque.
Boolean contains(Object o)	Checks if the deque contains the specified element	Return value - true if the deque contains the element
Boolean containsAll(Collection c)	Checks if the deque contains all the elements in the collection	Return value - true if the deque contains all the elements
Iterator descendingIterator()	Returns an iterator over elements in the deque in the reverse order
Object element()	Returns the first element(head) in the deque
Boolean equals(Object o)	Compares if the deque contains all the specified elements in the exact order	Return value - true if object elements match with the deque
Object getFirst()	Returns the first element(head) in the deque
Object getLast()	Returns the last element(tail) in the deque
Boolean isEmpty()	Checks if the deque is empty or not	Return value - true if deque contains no values
Iterator iterator()	Retrieves the iterator of deque in sequence	Return value - Iterator
Boolean offer(Object e)	Inserts the element as the tail	e - element to be added
Boolean offerFirst(Object e)	Inserts the element at the front of the deque	e - element to be added
Boolean offerLast(Object e)	Inserts the element at the end of the deque	e - element to be added
Object peek()	Retrieves the first element of the deque(head)	Returns null if the deque is empty
Object peekFirst()	Retrieves the first element of the deque(head)	Returns null if the deque is empty
Object peekLast()	Retrieves the last element of the deque(tail)	Returns null if the deque is empty
Object poll()	Retrieves and removes the first element of the deque(head)	Returns null if the deque is empty
Object pollFirst()	Retrieves and removes the first element of the deque(head)	Returns null if the deque is empty
Object pollLast()	Retrieves and removes the last element of the deque(tail)	Returns null if the deque is empty
Object pop()	Retrieves or removes the first element from the stack of the deque
void push(Object e)	Inserts the element to the front of the deque	e - the element to be added
Object remove()	Removes the first element from the deque
Boolean remove(Object o)	Removes the first occurrence of the specified object from the deque if present	o - The element that needs to be removed Return value - true if deque contains the element
Boolean removeAll(Collection c)	Removes the first occurrence of all the elements in the collection from the deque if present	c - collection of elements Return value - true if the deque contains the collection
Object removeFirst()	Removes the first element of the deque
Boolean removeFirstOccurence(Object e)	Removes the first occurrence of the element specified in the deque	e - the element to be removed
Object removeLast()	Removes the last element from the deque
Boolean removeLastOccurence(Object e)	Removes the last occurrence of the specified element from the deque	e - the element to be removed
Boolean retainAll(Collection c)	Retains all the elements specified in collection in deque. Other elements will be removed	c - collection of elements that has to be retained Return value - true if the deque changed due to the method called
int size()	Fetches the size of the deque	Return value - size of the deque
Object[] toArray()	Returns an array of elements in proper sequence	Return value - Array of all elements in the deque in proper sequence
String toString()	Returns a String representation of the elements collection	Return value - String of array elements separated by comma and space and enclosed within []

Example: Insert elements into an ArrayDeque

We can insert elements into an ArrayDeque in Java either using the add() or offer() methods. For inserting a collection of elements, we can use the addAll() method. To insert a value at the beginning, use the addFirst(), offerFirst() or push() method whereas to insert values at the end, we can use the addLast(), or offerLast() method.

import java.util.ArrayDeque;

public class InsertArrayDequeElements {

  public static void main(String[] args) {
    ArrayDeque<String> d = new ArrayDeque<String>();
    d.add("Delhi");
    d.addFirst("Bangalore");
    d.addLast("Chennai");
    
    System.out.println("Elements in the Deque after add, addFirst and addLast: " + d);
    
    ArrayDeque<String> dq = new ArrayDeque<String>();
    dq.add("Hyderabad");
    dq.add("Trivandrum");
    
    d.addAll(dq);
    
    System.out.println("Elements in the Deque after addAll: " + d);
    
    d.offer("Jaipur");
    d.offerFirst("Goa");
    d.offerLast("Mumbai");
    
    System.out.println("Elements in the Deque after offer, offerFirst and offerLast: " + d);
    
    d.push("Kolkata");
    
    System.out.println("Elements in the Deque after push: " + d);

  }

}

Elements in the Deque after add, addFirst and addLast: [Bangalore, Delhi, Chennai]
Elements in the Deque after addAll: [Bangalore, Delhi, Chennai, Hyderabad, Trivandrum]
Elements in the Deque after offer, offerFirst and offerLast: [Goa, Bangalore, Delhi, Chennai, Hyderabad, Trivandrum, Jaipur, Mumbai]
Elements in the Deque after push: [Kolkata, Goa, Bangalore, Delhi, Chennai, Hyderabad, Trivandrum, Jaipur, Mumbai]

Example: Deleting elements from the ArrayDeque

The below example shows how we can delete elements from the ArrayDeque using various methods. The remove(), removeFirst(), poll(), pollFirst() and pop() methods deletes the first element in the deque. The removeLast() and pollLast() deletes the last value in the deque. To delete all the elements except the collection of specified elements, we can use the retainAll() method, and to remove all the elements in the collection, we can use the removeAll() method.

import java.util.ArrayDeque;

public class DeleteArrayDequeElements {

  public static void main(String[] args) {
    ArrayDeque<String> ad = new ArrayDeque<String>();
    ad.add("Red");
    ad.add("Blue");
    ad.add("White");
    ad.add("Yellow");
    ad.add("Black");
    
    ArrayDeque<String> d = new ArrayDeque<String>();
    d.add("Pink");
    d.add("Green");
    d.add("Purple");
    d.add("Orange");
    d.add("Brown");
    
    ad.addAll(d);
    System.out.println("Elements in the ArrayDeque: " + ad);
    
    ad.remove();
    ad.remove("Black");
    
    System.out.println("Elements in the ArrayDeque after remove: " + ad);
    
    ad.removeFirst();
    ad.removeLast();
    
    System.out.println("Elements in the ArrayDeque after removeFirst and removeLast: " + ad);
    
    ad.poll();
    ad.pollFirst();
    ad.pollLast();
    
    System.out.println("Elements in the ArrayDeque after poll, pollFirst, pollLast: " + ad);
    
    ad.pop();
    System.out.println("Elements in the ArrayDeque after pop: " + ad);
    
    ad.retainAll(d);
    System.out.println("Elements in the ArrayDeque after retainAll: " + ad);
    
    ad.removeAll(d);
    System.out.println("Elements in the ArrayDeque after removeAll: " + ad);

  }

}

Elements in the ArrayDeque: [Red, Blue, White, Yellow, Black, Pink, Green, Purple, Orange, Brown]
Elements in the ArrayDeque after remove: [Blue, White, Yellow, Pink, Green, Purple, Orange, Brown]
Elements in the ArrayDeque after removeFirst and removeLast: [White, Yellow, Pink, Green, Purple, Orange]
Elements in the ArrayDeque after poll, pollFirst, pollLast: [Pink, Green, Purple]
Elements in the ArrayDeque after pop: [Green, Purple]
Elements in the ArrayDeque after retainAll: [Green, Purple]
Elements in the ArrayDeque after removeAll: []

Example: Access ArrayDeque elements

The below example illustrates how to check if a value exists and how to access first or last values from the ArrayDeque in Java. To check the existence of an element, use the contains() method. It returns true if the value exists else it returns false. To access the first element, we can use the element(), getFirst(), peek() or peekFirst() methods whereas to get the last value, we can use the getLast() or peekLast() methods.

import java.util.ArrayDeque;

public class RetrieveArrayDeque {

  public static void main(String[] args) {
    ArrayDeque<String> ad = new ArrayDeque<String>();
    ad.add("Red");
    ad.add("Blue");
    ad.add("White");
    ad.add("Yellow");
    ad.add("Black");
    
    ArrayDeque<String> d = new ArrayDeque<String>();
    d.add("Green");
    d.add("Orange");
    
    ad.addAll(d);
    
    System.out.println(ad);
    System.out.println(ad.contains("White"));
    System.out.println(d.contains("Brown"));
    System.out.println(d.containsAll(d));
    
    System.out.println("Output of element: " + ad.element());
    System.out.println("Get first element using getFirst: " + ad.getFirst());
    System.out.println("Get last element using getLast: " + ad.getLast());
    System.out.println("Output of peek: " + ad.peek());
    System.out.println("Get first element using peekFirst: " + ad.peekFirst());
    System.out.println("Get last element using peekLast: " + ad.peekLast());

  }

}

[Red, Blue, White, Yellow, Black, Green, Orange]
true
false
true
Output of element: Red
Get first element using getFirst: Red
Get last element using getLast: Orange
Output of peek: Red
Get first element using peekFirst: Red
Get last element using peekLast: Orange

Example: Iterate an ArrayDeque in Java

We can iterate through all elements in the ArrayDeque in Java in the same order using the iterator() method. To retrieve the values in the descending order, we can use the descendingIterator() method.

import java.util.ArrayDeque;
import java.util.Iterator;

public class IterateArrayDeque {

  public static void main(String[] args) {
    ArrayDeque<String> ad = new ArrayDeque<String>();
    ad.add("Red");
    ad.add("Blue");
    ad.add("White");
    ad.add("Yellow");
    ad.add("Black");
    
    System.out.println("Iterate using iterator:");
    Iterator<String> i = ad.iterator();
    while(i.hasNext())
      System.out.println(i.next());
    
    System.out.println("Iterate using descendingIterator:");
    Iterator<String> di = ad.descendingIterator();
    while(di.hasNext())
      System.out.println(di.next());

  }

}

Iterate using iterator:
Red
Blue
White
Yellow
Black
Iterate using descendingIterator:
Black
Yellow
White
Blue
Red

Example: ArrayDeque as a stack in Java

ArrayDeque provides implementation of a stack using the push(), peek() and pop() methods. For Last-In-First-Out (LIFO) stack implementation, it is always better to use a Deque instead of a stack since its performance is faster than the stack.

import java.util.ArrayDeque;

public class ArrayDequeAsStack {

  public static void main(String[] args) {
    ArrayDeque<String> s = new ArrayDeque<String>();
    s.push("Red");
    s.push("Green");
    s.push("Blue");
    
    System.out.println("Elements in ArrayDeque as stack: " + s);
    
    System.out.println("Retrieve element: " + s.peek());
    
    String val = s.pop();
    System.out.println("Removed element: " + val);
  }

}

Elements in ArrayDeque as stack: [Blue, Green, Red]
Retrieve element: Blue
Removed element: Blue

Example: ArrayDeque with an initial capacity

We can construct an ArrayDeque with the specified initial capacity as illustrated below. In this example, it shows that the deque can hold a minimum of 5 elements.

import java.util.ArrayDeque;

public class ArrayDequeCapacity {

  public static void main(String[] args) {
    ArrayDeque<Integer> a = new ArrayDeque<Integer>(5);
    a.add(20);
    a.add(10);
    a.add(40);
    a.add(30);
    a.add(50);
    
    a.add(60);
    System.out.println(a);
    System.out.println("Size of ArrayDeque: " + a.size());

  }

}

[20, 10, 40, 30, 50, 60]
Size of ArrayDeque: 6

Reference