Java ArrayDeque

---

The ArrayDeque class in Java is a versatile implementation of the Deque interface, backed by a resizable array. It provides an efficient way to perform operations on both ends of a collection, making it a useful data structure for a variety of applications. Unlike a LinkedList, which uses a doubly linked list, the ArrayDeque uses a dynamic array to store elements, which allows for faster access and manipulation of data. However, it does have some trade-offs when it comes to the resizing and memory overhead of arrays.

---

What is the Java ArrayDeque?

ArrayDeque is a class in Java that implements the Deque interface. A Deque (Double-Ended Queue) allows elements to be added or removed from both ends efficiently. The ArrayDeque class uses a resizable array to store elements, providing better performance than a LinkedList in most cases, especially for operations at the front or end of the deque.

Key Features of ArrayDeque

• Resizable Array: ArrayDeque uses an array internally, which grows automatically as needed, offering better performance in terms of access times compared to LinkedList.
• No Capacity Limit: The capacity of an ArrayDeque grows automatically as more elements are added.
• Efficient Operations: It offers O(1) time complexity for both add and remove operations at both ends of the deque.
• No Null Elements: Unlike other collections, ArrayDeque does not allow null elements.
• Faster Than LinkedList: Since ArrayDeque is based on a contiguous array, it generally offers better performance than LinkedList for most use cases, except for insertion/removal operations in the middle.

---

Key Methods of ArrayDeque

Here are some of the most commonly used methods in the ArrayDeque class:

• addFirst(E e): Adds the specified element at the front of the deque.
• addLast(E e): Adds the specified element at the end of the deque.
• offerFirst(E e): Inserts the specified element at the front of the deque (returns true if successful).
• offerLast(E e): Inserts the specified element at the end of the deque (returns true if successful).
• removeFirst(): Removes and returns the first element from the deque.
• removeLast(): Removes and returns the last element from the deque.
• pollFirst(): Removes and returns the first element, or null if the deque is empty.
• pollLast(): Removes and returns the last element, or null if the deque is empty.
• getFirst(): Retrieves but does not remove the first element.
• getLast(): Retrieves but does not remove the last element.
• peekFirst(): Retrieves but does not remove the first element, or null if empty.
• peekLast(): Retrieves but does not remove the last element, or null if empty.
• size(): Returns the number of elements in the deque.
• isEmpty(): Checks if the deque is empty.

---

Creating an ArrayDeque in Java

You can create an ArrayDeque in Java by using its default constructor or by specifying an initial collection of elements.

Example 1: Basic ArrayDeque Usage

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        // Create an ArrayDeque of Strings
        ArrayDeque<String> deque = new ArrayDeque<>();

        // Adding elements to the front and end
        deque.addFirst("Java");
        deque.addLast("Python");
        deque.addLast("C++");
        deque.addFirst("JavaScript");

        // Displaying the deque
        System.out.println("ArrayDeque: " + deque);

        // Removing elements from the front and end
        System.out.println("Removed First: " + deque.removeFirst());
        System.out.println("Removed Last: " + deque.removeLast());

        // Displaying the deque after removal
        System.out.println("ArrayDeque after removal: " + deque);
    }
}

Output:

ArrayDeque: [JavaScript, Java, Python, C++]
Removed First: JavaScript
Removed Last: C++
ArrayDeque after removal: [Java, Python]

In this example, we create an ArrayDeque, add elements to both ends, and then remove them. The ArrayDeque is efficient for adding and removing elements from both ends.

---

Example 2: Using ArrayDeque as a Queue

You can use an ArrayDeque as a queue by adding elements at the end and removing them from the front.

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        // Create an ArrayDeque to act as a queue
        ArrayDeque<String> queue = new ArrayDeque<>();

        // Add elements to the queue
        queue.offerLast("Task 1");
        queue.offerLast("Task 2");
        queue.offerLast("Task 3");

        // Displaying the queue
        System.out.println("Queue: " + queue);

        // Remove elements from the front of the queue (FIFO)
        System.out.println("Dequeued: " + queue.pollFirst());
        System.out.println("Dequeued: " + queue.pollFirst());

        // Displaying the queue after removal
        System.out.println("Queue after dequeue: " + queue);
    }
}

Output:

Queue: [Task 1, Task 2, Task 3]
Dequeued: Task 1
Dequeued: Task 2
Queue after dequeue: [Task 3]

In this example, we use the ArrayDeque as a queue (FIFO) by using the offerLast() and pollFirst() methods.

---

Example 3: Using ArrayDeque as a Stack

You can also use an ArrayDeque as a stack (LIFO) by adding and removing elements from the front.

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        // Create an ArrayDeque to act as a stack
        ArrayDeque<String> stack = new ArrayDeque<>();

        // Push elements onto the stack
        stack.push("Red");
        stack.push("Green");
        stack.push("Blue");

        // Displaying the stack
        System.out.println("Stack: " + stack);

        // Pop elements from the stack (LIFO)
        System.out.println("Popped: " + stack.pop());
        System.out.println("Popped: " + stack.pop());

        // Displaying the stack after pops
        System.out.println("Stack after pop: " + stack);
    }
}

Output:

Stack: [Blue, Green, Red]
Popped: Blue
Popped: Green
Stack after pop: [Red]

In this case, the ArrayDeque functions as a stack by using the push() and pop() methods, adhering to the LIFO (Last-In-First-Out) principle.

---

When to Use ArrayDeque

The ArrayDeque class is ideal for use cases that require:

1. Double-ended queue operations: Adding and removing elements from both ends.
2. Queue functionality: Implementing a FIFO (First-In-First-Out) queue for tasks or messages.
3. Stack functionality: Implementing a LIFO (Last-In-First-Out) stack for algorithms like depth-first search (DFS).
4. Fast insertion and removal: Operations at the beginning and end of the deque are generally O(1), making it highly efficient.

However, it is not suitable when you need to frequently access elements by index, as this requires O(n) time for traversal.

---

ArrayDeque vs LinkedList

Here’s a quick comparison of ArrayDeque and LinkedList:

• Memory Overhead: ArrayDeque uses a dynamic array, while LinkedList uses a doubly linked list. ArrayDeque is usually more memory-efficient since it doesn't need to store additional references (next and previous) for each element.
• Performance: ArrayDeque provides faster access to elements and better cache locality than LinkedList, especially for operations at both ends of the deque.
• Thread-Safety: Neither ArrayDeque nor LinkedList is thread-safe. However, if you need thread safety, you can use ConcurrentLinkedDeque.

---

---