ArrayDeque

About

ArrayDeque, part of the java.util package, is a resizable, double-ended queue that uses a dynamic array internally to store its elements. It is one of the most efficient implementations of the Deque interface and is a popular choice for scenarios requiring stack or queue functionality. Unlike LinkedList, it avoids the overhead of maintaining node references.

Features

1. Resizable Array: Automatically resizes its capacity when the internal array becomes full.

2. Double-Ended: Supports element insertion and removal at both ends.

3. Efficient Operations: Provides O(1) time complexity for most operations, including insertion and removal at either end.

4. No Capacity Restrictions: By default, it grows dynamically as needed (except when manually constrained by the user).

5. Null Elements Not Allowed: Helps prevent ambiguities during null checks in poll and peek methods.

6. Better than Stack/LinkedList: Faster and more efficient alternative for stack (push and pop) and queue implementations.

7. High Cache Performance: Operations are faster due to contiguous memory allocation, which benefits CPU caching.

8. Thread-Unsafety: Not thread-safe, but lightweight and faster in single-threaded applications. For concurrent usage, external synchronization or ConcurrentLinkedDeque is preferred.

Key Methods

Method Type	Method	Description
Add Operations	addFirst(E e)	Adds an element to the front of the deque. Throws exception if capacity is constrained.
	addLast(E e)	Adds an element to the end of the deque. Throws exception if capacity is constrained.
	offerFirst(E e)	Adds an element at the front without throwing exceptions.
	offerLast(E e)	Adds an element at the end without throwing exceptions.
Remove Operations	removeFirst()	Removes and returns the first element. Throws an exception if the deque is empty.
	removeLast()	Removes and returns the last element. Throws an exception if the deque is empty.
	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.
Access Operations	getFirst()	Retrieves the first element without removing it.
	getLast()	Retrieves the last element without removing it.
	peekFirst()	Retrieves the first element without removal or null if the deque is empty.
	peekLast()	Retrieves the last element without removal or null if the deque is empty.
Stack Operations	push(E e)	Pushes an element onto the stack (alias for addFirst).
	pop()	Removes and returns the top element of the stack (alias for removeFirst).
Iterator	iterator()	Returns an iterator over elements in front-to-back order.
	descendingIterator()	Returns an iterator over elements in reverse order.

Big O Time Complexity for ArrayDeque

Operation	Time Complexity	Details
Insert at Head (addFirst)	O(1)	Efficient insertion at the front due to circular buffer design.
Insert at Tail (addLast)	O(1)	Efficient insertion at the rear due to dynamic array resizing.
Remove from Head (pollFirst)	O(1)	Removes element from the front with constant time complexity.
Remove from Tail (pollLast)	O(1)	Removes element from the rear with constant time complexity.
Peek at Head (peekFirst)	O(1)	Accessing the front element without removing it.
Peek at Tail (peekLast)	O(1)	Accessing the rear element without removing it.
Search (contains)	O(n)	Linear scan for searching an element in the deque.
Resize Operation	O(n)	Occurs when the internal array exceeds capacity, rare but costly.

Example

Basic Operation

import java.util.ArrayDeque;
import java.util.Deque;

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

        // Add elements to both ends
        deque.addFirst("Alice");
        deque.addLast("Bob");
        System.out.println("Deque after additions: " + deque);

        // Access elements without removing
        System.out.println("First element (peekFirst): " + deque.peekFirst());
        System.out.println("Last element (peekLast): " + deque.peekLast());

        // Remove elements from both ends
        System.out.println("Removed first (pollFirst): " + deque.pollFirst());
        System.out.println("Removed last (pollLast): " + deque.pollLast());
        System.out.println("Deque after removals: " + deque);

        // Stack operations
        deque.push("Charlie");
        deque.push("David");
        System.out.println("Deque as stack: " + deque);
        System.out.println("Popped from stack: " + deque.pop());

        // Queue operations
        deque.offerFirst("Eve");
        deque.offerLast("Frank");
        System.out.println("Deque as queue: " + deque);

        // Iteration
        System.out.print("Iterating through deque: ");
        for (String name : deque) {
            System.out.print(name + " ");
        }

        // Reverse iteration
        System.out.print("\nReverse iteration: ");
        for (String name : deque.descendingIterator()) {
            System.out.print(name + " ");
        }
    }
}

Custom Objects in ArrayDeque

import java.util.ArrayDeque;
import java.util.Deque;

class Task {
    String name;
    int priority;

    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public String toString() {
        return "Task{name='" + name + "', priority=" + priority + '}';
    }
}

public class CustomObjectDeque {
    public static void main(String[] args) {
        Deque<Task> taskDeque = new ArrayDeque<>();

        // Adding custom objects
        taskDeque.addLast(new Task("Low Priority Task", 1));
        taskDeque.addFirst(new Task("High Priority Task", 3));
        System.out.println("Tasks: " + taskDeque);

        // Processing tasks
        System.out.println("Processing: " + taskDeque.pollFirst());
        System.out.println("Processing: " + taskDeque.pollLast());
    }
}

When to Use ArrayDeque ?

1. Double-Ended Operations: Ideal when you need fast operations at both ends.

2. As a Replacement for Stack: Use instead of Stack for a modern implementation.

3. Sliding Window Problems: Great for maintaining dynamic windows in algorithmic problems.

4. Thread-Safe Needs: Use ConcurrentLinkedDeque if thread safety is a concern.