When do you use ArrayDeque vs LinkedList vs Stack?

• ArrayDeque is a resizable circular array implementing Deque; it provides O(1) amortized add/remove at both ends with excellent cache locality
• LinkedList implements both List and Deque but uses scattered heap nodes, causing cache misses that make it 2-3x slower than ArrayDeque for deque operations
• Stack extends Vector (Java 1.0), synchronizing every method; it also exposes get(index) which violates the LIFO abstraction
• The Java documentation states: "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue"

What is ArrayDeque?

ArrayDeque is a double-ended queue backed by a resizable circular array. It was introduced in Java 6 as the modern replacement for both the Stack class and LinkedList when used as a queue or deque.

The circular array means that the head and tail can wrap around the array boundaries. When you add to the front, the head index moves backward (wrapping to the end of the array). When you add to the back, the tail index moves forward. Both operations are O(1).

package com.bank.demo;

import java.util.*;

public class ArrayDequeBasicsDemo {
    public static void main(String[] args) {
        // As a Queue (FIFO)
        Deque<String> queue = new ArrayDeque<>();
        queue.offerLast("TXN-001: Deposit 50000");
        queue.offerLast("TXN-002: Withdraw 10000");
        queue.offerLast("TXN-003: Transfer 25000");

        System.out.println("Queue processing (FIFO):");
        while (!queue.isEmpty()) {
            System.out.println("  Process: " + queue.pollFirst());
        }

        // As a Stack (LIFO)
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Step 1: Open account");
        stack.push("Step 2: Deposit 50000");
        stack.push("Step 3: Set up auto-pay");

        System.out.println("\nUndo stack (LIFO):");
        while (!stack.isEmpty()) {
            System.out.println("  Undo: " + stack.pop());
        }

        // As a Deque (both ends)
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("High priority");
        deque.addLast("Normal priority");
        deque.addFirst("Urgent");
        System.out.println("\nDeque: " + deque);
    }
}

Queue processing (FIFO):
  Process: TXN-001: Deposit 50000
  Process: TXN-002: Withdraw 10000
  Process: TXN-003: Transfer 25000

Undo stack (LIFO):
  Undo: Step 3: Set up auto-pay
  Undo: Step 2: Deposit 50000
  Undo: Step 1: Open account

Deque: [Urgent, High priority, Normal priority]

How does the circular array work internally?

ArrayDeque maintains an Object[] elements array, a head index, and a tail index. The array is treated as circular: when an index goes past the end, it wraps around to the beginning.

• addFirst(e): decrement head (wrapping to elements.length - 1 if needed), place element at the new head position.
• addLast(e): place element at tail, increment tail (wrapping to 0 if needed).
• pollFirst(): read element at head, null it out, increment head.
• pollLast(): decrement tail, read and null the element.

When head == tail, the deque is either empty or full. ArrayDeque distinguishes these by doubling the array when full.

package com.bank.demo;

public class CircularArrayDemo {
    // Simplified circular array deque
    private Object[] elements = new Object[8];
    private int head = 0;
    private int tail = 0;

    public void addLast(Object e) {
        elements[tail] = e;
        tail = (tail + 1) & (elements.length - 1); // wrap using bitmask
        if (tail == head) grow(); // full -> double
    }

    public Object pollFirst() {
        Object e = elements[head];
        elements[head] = null;
        head = (head + 1) & (elements.length - 1);
        return e;
    }

    private void grow() {
        // Double the array and copy elements
        int oldLen = elements.length;
        Object[] newArr = new Object[oldLen << 1];
        // Copy head..end, then 0..tail
        System.arraycopy(elements, head, newArr, 0, oldLen - head);
        System.arraycopy(elements, 0, newArr, oldLen - head, head);
        elements = newArr;
        head = 0;
        tail = oldLen;
    }

    public static void main(String[] args) {
        CircularArrayDemo deque = new CircularArrayDemo();
        deque.addLast("SAV2001");
        deque.addLast("CUR3001");
        System.out.println("First: " + deque.pollFirst());
        System.out.println("Second: " + deque.pollFirst());
    }
}

First: SAV2001
Second: CUR3001

How is ArrayDeque different from LinkedList as a Deque?

Both implement Deque, but their internal structures give them very different performance profiles.

| Feature | ArrayDeque | LinkedList |
|---|---|---|
| Backing structure | Circular array | Doubly-linked nodes |
| Cache locality | Excellent (contiguous) | Poor (scattered heap) |
| Memory per element | ~4-8 bytes | ~40 bytes |
| addFirst / addLast | O(1) amortized | O(1) |
| pollFirst / pollLast | O(1) | O(1) |
| Null elements | Not allowed | Allowed |
| Implements List | No | Yes |
| get(index) | No | Yes (but O(n)) |
| Growth | Doubles (2x) | Per-node allocation |
| GC pressure | Low (one array) | High (one Node per element) |

In benchmarks, ArrayDeque is typically 2-3x faster than LinkedList for queue and stack operations because of cache locality.

package com.bank.demo;

import java.util.*;

public class DequePerformanceDemo {
    public static void main(String[] args) {
        int size = 1_000_000;

        // ArrayDeque
        Deque<Integer> arrayDeque = new ArrayDeque<>();
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) arrayDeque.offerLast(i);
        while (!arrayDeque.isEmpty()) arrayDeque.pollFirst();
        long adTime = System.nanoTime() - start;

        // LinkedList
        Deque<Integer> linkedList = new LinkedList<>();
        start = System.nanoTime();
        for (int i = 0; i < size; i++) linkedList.offerLast(i);
        while (!linkedList.isEmpty()) linkedList.pollFirst();
        long llTime = System.nanoTime() - start;

        System.out.printf("ArrayDeque:  %d ms%n", adTime / 1_000_000);
        System.out.printf("LinkedList:  %d ms%n", llTime / 1_000_000);
        System.out.printf("ArrayDeque is %.1fx faster%n", (double) llTime / adTime);
    }
}

ArrayDeque:  28 ms
LinkedList:  65 ms
ArrayDeque is 2.3x faster

Why should you never use the Stack class?

Stack was added in Java 1.0, before the Collections Framework existed. It extends Vector, which means:

1. Every method is synchronized. Even in single-threaded code, push, pop, and peek acquire and release a monitor lock. This adds 15-30% overhead.
2. It exposes get(index). A stack should only allow access to the top element. Stack lets you call get(0) to access the bottom, violating the LIFO contract.
3. Legacy API. Stack has search(Object) which returns a 1-based position, inconsistent with the rest of the Collections Framework.

package com.bank.demo;

import java.util.*;

public class StackProblemsDemo {
    public static void main(String[] args) {
        // Stack: synchronized + exposes random access
        Stack<String> legacy = new Stack<>();
        legacy.push("Step 1");
        legacy.push("Step 2");
        legacy.push("Step 3");

        // BAD: random access violates stack abstraction
        String bottom = legacy.get(0); // "Step 1" – not LIFO!
        System.out.println("Stack.get(0) = " + bottom);

        // BAD: search() returns 1-based position (non-standard)
        int pos = legacy.search("Step 2"); // 2 (1-based from top)
        System.out.println("Stack.search = " + pos);

        // ArrayDeque: no random access, no sync overhead
        Deque<String> modern = new ArrayDeque<>();
        modern.push("Step 1");
        modern.push("Step 2");
        modern.push("Step 3");
        // modern.get(0); // compile error – no get() method!
        System.out.println("ArrayDeque.pop() = " + modern.pop()); // proper LIFO
    }
}

Stack.get(0) = Step 1
Stack.search = 2
ArrayDeque.pop() = Step 3

What about null elements?

ArrayDeque does not allow null elements. If you call addFirst(null) or offerLast(null), it throws NullPointerException. This is because ArrayDeque uses null internally as a sentinel to distinguish empty slots from occupied ones.

LinkedList allows null elements. If you need to store nulls in a deque, LinkedList is the only standard option.

Deque<String> arrayDeque = new ArrayDeque<>();
try {
    arrayDeque.offerLast(null); // NullPointerException!
} catch (NullPointerException e) {
    System.out.println("ArrayDeque rejects null");
}

Deque<String> linkedList = new LinkedList<>();
linkedList.offerLast(null); // OK
System.out.println("LinkedList allows null: " + linkedList);

ArrayDeque rejects null
LinkedList allows null: [null]

What are common mistakes?

Mistake 1: Using Stack instead of ArrayDeque

// WRONG – legacy, synchronized, exposes get(index)
Stack<String> stack = new Stack<>();

// CORRECT – modern, fast, proper LIFO API
Deque<String> stack = new ArrayDeque<>();

Mistake 2: Using LinkedList as a queue when ArrayDeque is better

// SUBOPTIMAL – LinkedList has cache misses and high memory overhead
Queue<String> queue = new LinkedList<>();

// BETTER – ArrayDeque is 2-3x faster
Queue<String> queue = new ArrayDeque<>();

Mistake 3: Declaring the variable as ArrayDeque instead of Deque

// WRONG – locked to implementation
ArrayDeque<String> deque = new ArrayDeque<>();

// CORRECT – program to the interface
Deque<String> deque = new ArrayDeque<>();

What about thread safety?

ArrayDeque is not thread-safe. For concurrent access:

• Concurrent queue: use ConcurrentLinkedDeque (lock-free, unbounded) or LinkedBlockingDeque (blocking, bounded).
• Concurrent stack: use ConcurrentLinkedDeque with push/pop.
• Producer-consumer: use LinkedBlockingQueue (blocking) or ArrayBlockingQueue (bounded, array-backed).

When should you use each implementation?

| Need | Implementation | Why |
|---|---|---|
| Queue (FIFO) | ArrayDeque | Fastest, least memory |
| Stack (LIFO) | ArrayDeque | Replaces legacy Stack |
| Deque (both ends) | ArrayDeque | Default choice |
| List + Deque | LinkedList | Only option |
| Null elements in deque | LinkedList | ArrayDeque rejects null |
| Thread-safe queue | ConcurrentLinkedDeque | Lock-free |
| Blocking queue | LinkedBlockingQueue | Producer-consumer |
| Priority queue | PriorityQueue | Sorted by priority |

What should a senior engineer know?

- Capacity is always a power of 2. ArrayDeque's internal array size is always a power of 2 (16, 32, 64, etc.). This allows the use of bitwise AND (index & (length - 1)) instead of modulo (index % length) for wrapping, which is faster.

- Growth doubles the array. When the circular array is full, ArrayDeque doubles it (2x growth). This is different from ArrayList's 1.5x growth. The doubling makes sense because deque operations happen at both ends, and you want to minimize the number of resizes.

- No iterator-based modification. ArrayDeque's iterator does not support add() during iteration. Only remove() is supported. This is different from LinkedList's ListIterator which supports both.

- Spliterator support. ArrayDeque provides a good Spliterator for parallel streams because the underlying array can be split in half. LinkedList's Spliterator cannot split efficiently.

- Used in BFS algorithms. ArrayDeque is the standard choice for breadth-first search because it provides O(1) FIFO operations without the overhead of LinkedList.

What are common interview follow-up questions?

• "What is the internal data structure of ArrayDeque?" – Resizable circular array.
• "Can ArrayDeque store null?" – No, null is used as an internal sentinel.
• "What is the growth strategy of ArrayDeque?" – Doubles (2x).
• "Why is Stack a bad design?" – Extends Vector (synchronized), exposes get(index).
• "When would you use LinkedList over ArrayDeque?" – When you need List interface or null elements.