Internal Working of ArrayDeque in Java

Introduction

An ArrayDeque in Java is a part of the java.util package and is used as a resizable, double-ended queue (deque). It allows adding and removing elements from both ends efficiently and is faster than LinkedList for stack and queue operations.

---

1. Data Structure Used

ArrayDeque is implemented using a circular array, which allows efficient insertions and deletions from both ends.

Implementation in Java:

public class ArrayDeque<E> extends AbstractCollection<E> {
    transient Object[] elements;
    transient int head;
    transient int tail;
}

• elements[]: The underlying array storing the deque elements.
• head: Index pointing to the front of the deque.
• tail: Index pointing to the rear of the deque.

---

2. How Elements are Stored and Accessed

Adding an Element (addFirst() / addLast())

When adding an element:

1. If adding to the front (addFirst()), the head index is decremented and the element is placed.
2. If adding to the rear (addLast()), the element is added at the tail index, and tail is incremented.
3. If the array is full, it is resized dynamically.

Example:

ArrayDeque<String> deque = new ArrayDeque<>();
deque.addFirst("Apple");
deque.addLast("Banana");
deque.addFirst("Cherry");
System.out.println(deque); // Output: [Cherry, Apple, Banana]

Retrieving an Element (getFirst() / getLast())

Elements are accessed using direct indexing, which is O(1):

System.out.println(deque.getFirst()); // Output: Cherry
System.out.println(deque.getLast()); // Output: Banana

Removing an Element (removeFirst() / removeLast())

When removing an element:

1. If removing from the front (removeFirst()), head is incremented.
2. If removing from the rear (removeLast()), tail is decremented.
3. If the deque becomes too sparse, it is resized dynamically.

Example:

deque.removeFirst(); // Removes Cherry
System.out.println(deque); // Output: [Apple, Banana]

---

3. Internal Working of Circular Array in ArrayDeque

ArrayDeque uses a circular buffer mechanism, where indices wrap around when they reach the end of the array.

Circular Buffer Representation

Initial state: [ , , , ] (empty)
addFirst("A"):  [A, , , ] (head = 0, tail = 1)
addLast("B"):   [A, B, , ] (head = 0, tail = 2)
addFirst("C"):  [A, B, , C] (head = 3, tail = 2)

• Elements are stored in a circular manner, reducing unnecessary shifts.

Resizing Mechanism

• The default capacity is 16.
• When full, the array size doubles.
• Elements are copied to the new array, maintaining order.

---

4. Performance Analysis

Operation	Time Complexity
Add at Front (addFirst())	O(1)
Add at Rear (addLast())	O(1)
Remove at Front (removeFirst())	O(1)
Remove at Rear (removeLast())	O(1)
Get Element (getFirst() / getLast())	O(1)

Comparison with Other Collections

Feature	ArrayDeque (Circular Array)	LinkedList (Doubly Linked List)
Access Time	⚡ Fast (O(1))	❌ Slow (O(n))
Insert/Delete at Ends	⚡ Fast (O(1))	✅ Fast (O(1))
Memory Usage	✅ Lower	❌ Higher (Extra node pointers)
Best Use Case	Queue/Stack Operations	Frequent Mid-List Insertions

---

5. Use Cases of ArrayDeque

1. Implementing Stacks (push() / pop())
2. Queue Processing (addLast() / removeFirst())
3. Sliding Window Algorithms (Efficient Deque Handling)

Example: Stack Implementation

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack.pop()); // Output: 30

---

6. Key Takeaways

✔ ArrayDeque is a resizable, circular-array-based deque.

✔ Provides fast O(1) insertions and deletions at both ends.

✔ Uses circular buffer to avoid excessive memory allocation.

✔ Faster and more memory-efficient than LinkedList for deque operations.

✔ Ideal for queue, stack, and sliding window use cases.

Understanding the internal working of ArrayDeque helps in selecting the right data structure for efficient queue and stack operations.