Java Notes
HubArray IntroductionArray OperationsArray Programs — FundamentalsArray Interview QuestionsJagged Array in JavaMulti Dimensional ArrayOne Dimensional Arraybreak and continue in JavaDo-While Loop in JavaFor Loop in JavaIf-Else Statements in JavaNested Loops in JavaSwitch-Case in JavaWhile Loop in JavaJava Compilation ProcessFeatures of JavaYour First Java ProgramHistory of JavaJava EditionsJava Program StructureJDK, JRE, and JVMWhat is Java?Immutable Strings in JavaString Class in JavaString Interview QuestionsString MethodsString Programs — FundamentalsStringBuffer in JavaStringBuilder in JavaComments in JavaData Types in JavaIdentifiers in JavaInput and Output in JavaKeywords in JavaOperators in JavaType Casting in JavaVariables in JavaAbstract Class in JavaAbstraction in JavaAnonymous Class in JavaClass and Object in JavaConstructor in JavaEncapsulation in JavaInheritance in JavaInner Class in JavaInterface in JavaMethod Overloading in JavaMethod Overriding in JavaObject Class in JavaObject Cloning in JavaOOPs IntroductionPolymorphism in Javastatic Keyword in Javasuper Keyword in Javathis Keyword in JavaWrapper Class in JavaCollections Framework OverviewCollections Practice ProgramsComparable vs Comparator in JavaGenerics in JavaIterator in JavaArrayList in JavaLinkedList in JavaStack in Java — Collections FrameworkVector in JavaHashMap in JavaHashtable in JavaLinkedHashMap in JavaTreeMap in JavaArrayDeque in JavaDeque Interface in JavaPriorityQueue in JavaHashSet in JavaLinkedHashSet in JavaTreeSet in JavaException Handling Best PracticesCustom Exceptions in JavaException Hierarchy in JavaFinally Block in JavaException Handling Introductionthrow and throws Keywords in JavaTry-Catch Block in JavaBuffered Streams in JavaByte Streams in JavaCharacter Streams in JavaDeserialization in JavaFile Class in JavaJava NIO PackageSerialization in JavaDate and Time API in Java 8Default and Static Methods in InterfacesFunctional Interface in Java 8Lambda Expression in Java 8Method Reference in Java 8Optional Class in Java 8Stream API in Java 8Creating Threads in JavaDaemon Threads in JavaExecutor Framework in JavaInter-Thread Communication in JavaMultithreading Programs in JavaRunnable Interface in JavaSynchronization in JavaThread Class in JavaThread IntroductionThread Life Cycle in JavaThread Priority in JavaBatch Processing in JDBCCallableStatement in JDBCJDBC ArchitectureJDBC IntroductionJDBC ProjectsMySQL Connection with JDBCPreparedStatement in JDBCResultSet in JDBCStatement Interface in JDBCTransaction Management in JDBCCookies in ServletsExpression Language (EL)GenericServletHttpServletJSP IntroductionJSP Tags and JSTLMVC ArchitectureRequest and Response ObjectsServlet IntroductionServlet Life CycleSession TrackingDependency InjectionAPI GatewayConfig ServerDocker DeploymentEureka Server - Service DiscoverySpring BeansCRUD ApplicationException Handling in Spring BootJWT Authentication — Java ProgrammingREST API with Spring BootSpring SecuritySpring Boot IntroductionSpring Data JPAValidation in Spring BootSpring Core ContainerSpring Framework IntroductionDynamic Programming in JavaGraph Data Structure in JavaHashing in JavaHeap (DSA)Linked List in JavaQueue in JavaRecursion in JavaSearching Algorithms in JavaSorting Algorithms in JavaStack in Java — DSA in JavaTime ComplexityTree Data Structure in JavaAdapter Design PatternBuilder Design PatternFactory Design PatternMVC Pattern — Java ProgrammingObserver Design PatternSingleton Design PatternArray Programs — PracticeBasic Java ProgramsCollection ProgramsJDBC ProgramsMultithreading ProgramsOOP ProgramsPlacement Coding QuestionsString Programs — PracticeBanking System — Java ProgrammingChat ApplicationE-Commerce BackendEmployee Management SystemLibrary Management System — Java ProgrammingSpring Boot Fullstack ProjectStudent Management System — Java ProgrammingCoding Interview QuestionsCollections Interview QuestionsCore Java Interview QuestionsJDBC Interview QuestionsMultithreading Interview QuestionsOOPs Interview QuestionsSpring Framework Interview QuestionsJava Cheat SheetImportant Formulas & ConceptsImportant Java ProgramsQuick Revision Notes — Java ProgrammingJava Master Course - Learning Roadmap
Complete guide to Java ArrayDeque — circular array implementation, resizing strategy, performance advantages over LinkedList and Stack, internal working, and practical usage patterns.
What is ArrayDeque?
java.util.ArrayDeque is the recommended implementation of both Deque and Queue interfaces. It uses a resizable circular array internally, providing O(1) amortized time for all deque operations.
java example
public class ArrayDeque<E>
extends AbstractCollection<E>
implements Deque<E>, Cloneable, SerializableFrom the official Java documentation:
"This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue."
How Operations Work
addLast(E e)
Example
public void addLast(E e) {
if (e == null) throw new NullPointerException();
elements[tail] = e;
tail = (tail + 1) & (elements.length - 1); // Increment with wrap
if (tail == head) doubleCapacity(); // Array is full — resize!
}
addFirst(E e)
Example
public void addFirst(E e) {
if (e == null) throw new NullPointerException();
head = (head - 1) & (elements.length - 1); // Decrement with wrap
elements[head] = e;
if (head == tail) doubleCapacity(); // Array is full — resize!
}
pollFirst()
Example
public E pollFirst() {
int h = head;
E result = (E) elements[h];
if (result == null) return null; // Empty deque
elements[h] = null; // Help GC
head = (h + 1) & (elements.length - 1);
return result;
}
pollLast()
Example
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
E result = (E) elements[t];
if (result == null) return null; // Empty deque
elements[t] = null; // Help GC
tail = t;
return result;
}
Resizing (doubleCapacity)
When head == tail (array is full), the capacity doubles:
Example
private void doubleCapacity() {
int p = head;
int n = elements.length;
int r = n - p; // Number of elements to the right of head
int newCapacity = n << 1; // Double
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r); // Copy right portion
System.arraycopy(elements, 0, a, r, p); // Copy left portion (wrapped)
elements = a;
head = 0;
tail = n;
}
Example:
| Array | [E] [F] [G] [H] [A] [B] [C] [D] |
| Logical | A B C D E F G H |
| Array | [A] [B] [C] [D] [E] [F] [G] [H] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] |
Time Complexity
| Operation | Time Complexity | Notes |
|---|---|---|
| ----------- | :-: | --- |
addFirst(E e) | O(1) amortized | Occasional O(n) resize |
addLast(E e) | O(1) amortized | Occasional O(n) resize |
pollFirst() | O(1) | Always constant |
pollLast() | O(1) | Always constant |
peekFirst() | O(1) | Always constant |
peekLast() | O(1) | Always constant |
size() | O(1) | Computed from head/tail |
contains(Object) | O(n) | Linear scan |
remove(Object) | O(n) | Linear scan + shift |
| Iteration | O(n) | Sequential access |
Complete Example
Example
import java.util.*;
public class ArrayDequeDemo {
public static void main(String[] args) {
// === As a Deque (double-ended) ===
ArrayDeque<String> deque = new ArrayDeque<>();
deque.addFirst("B"); // [B]
deque.addFirst("A"); // [A, B]
deque.addLast("C"); // [A, B, C]
deque.addLast("D"); // [A, B, C, D]
System.out.println("Deque: " + deque); // [A, B, C, D]
System.out.println("First: " + deque.peekFirst()); // A
System.out.println("Last: " + deque.peekLast()); // D
System.out.println("Size: " + deque.size()); // 4
deque.pollFirst(); // Remove A
deque.pollLast(); // Remove D
System.out.println("After polls: " + deque); // [B, C]
// === As a Stack (LIFO) ===
System.out.println("\n--- Stack Usage ---");
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Stack: " + stack); // [30, 20, 10]
System.out.println("Pop: " + stack.pop()); // 30
System.out.println("Peek: " + stack.peek()); // 20
// === As a Queue (FIFO) ===
System.out.println("\n--- Queue Usage ---");
Queue<String> queue = new ArrayDeque<>();
queue.offer("First");
queue.offer("Second");
queue.offer("Third");
System.out.println("Queue: " + queue); // [First, Second, Third]
System.out.println("Poll: " + queue.poll()); // First
System.out.println("Peek: " + queue.peek()); // Second
// === Bulk operations ===
ArrayDeque<Integer> nums = new ArrayDeque<>(Arrays.asList(1, 2, 3, 4, 5));
System.out.println("\nContains 3: " + nums.contains(3)); // true
System.out.println("Size: " + nums.size()); // 5
// Convert to array
Integer[] arr = nums.toArray(new Integer[0]);
System.out.println("Array: " + Arrays.toString(arr));
// Iteration
System.out.println("\nForward:");
for (int num : nums) System.out.print(num + " ");
System.out.println("\nBackward:");
Iterator<Integer> descIt = nums.descendingIterator();
while (descIt.hasNext()) System.out.print(descIt.next() + " ");
}
}
Output
Deque: [First, Middle, Last] PeekFirst: First PeekLast: Last PollFirst: First PollLast: Last Remaining: [Middle] Stack operations: Push A, B, C: [C, B, A] Pop: C Peek: B
Why ArrayDeque Over LinkedList?
1. Memory Efficiency
Per element overhead
- ArrayDeque: ~8 bytes (one reference in array)
- LinkedList: ~48 bytes (Node: prev + next + item + object header)
For 1 million elements
- ArrayDeque: ~8 MB + array overhead
- LinkedList: ~48 MB (6x more memory!)
2. Cache Performance
Example
ArrayDeque: [ref][ref][ref][ref][ref][ref] ← contiguous in memory
→ CPU can prefetch next elements
→ Cache lines are fully utilized
LinkedList: [Node] ← scattered → [Node] ← scattered → [Node]
→ Each access is a potential cache miss
→ No predictable memory pattern
3. No Object Allocation Per Element
java example
// ArrayDeque: just stores the reference in the existing array
deque.addLast(element); // No new object created (usually)
// LinkedList: creates a new Node object every time
list.addLast(element); // new Node<>(prev, element, next)4. Benchmark Results
Adding 10 million elements
ArrayDeque.addLast(): ~80ms
LinkedList.addLast(): ~250ms
Polling 10 million elements
ArrayDeque.pollFirst(): ~50ms
LinkedList.pollFirst(): ~150ms
Why ArrayDeque Over Stack?
| Feature | Stack (legacy) | ArrayDeque |
|---|---|---|
| Synchronized | Yes (overhead) | No (faster) |
| Exposes list methods | Yes (get, set, add at index) | No (proper encapsulation) |
| Null elements | Allowed | ❌ Not allowed |
| Growth | Doubles (Vector) | Doubles (more efficient) |
| Recommended | ❌ Legacy | ✅ Modern |
Constructors
java example
// Default: initial capacity 16
ArrayDeque<String> d1 = new ArrayDeque<>();
// Custom initial capacity (rounded up to next power of 2)
ArrayDeque<String> d2 = new ArrayDeque<>(100);
// Internal capacity becomes 128 (next power of 2 > 100)
// From another collection
ArrayDeque<String> d3 = new ArrayDeque<>(Arrays.asList("A", "B", "C"));Tip: If you know the expected size, specify it to avoid resizing:
java example
// For 1000 expected elements:
ArrayDeque<Event> events = new ArrayDeque<>(1024); // Power of 2 ≥ 1000Null Restriction
java example
ArrayDeque<String> deque = new ArrayDeque<>();
deque.add(null); // NullPointerException!
// WHY? ArrayDeque uses null internally to detect empty slots
// pollFirst() returns null when empty — if null elements were allowed,
// you couldn't distinguish "empty" from "element is null"Thread Safety
ArrayDeque is NOT thread-safe:
java example
// Option 1: ConcurrentLinkedDeque (non-blocking, unbounded)
Deque<String> concurrent = new ConcurrentLinkedDeque<>();
// Option 2: LinkedBlockingDeque (blocking, optionally bounded)
BlockingDeque<String> blocking = new LinkedBlockingDeque<>(100);
blocking.putFirst("item"); // Blocks if full
String item = blocking.takeLast(); // Blocks if empty
// Option 3: ArrayBlockingQueue (for Queue-only usage)
BlockingQueue<String> abq = new ArrayBlockingQueue<>(100);Practical Patterns
BFS Template
java example
public static void bfs(Node start) {
Deque<Node> queue = new ArrayDeque<>();
Set<Node> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
Node current = queue.poll();
process(current);
for (Node neighbor : current.getNeighbors()) {
if (visited.add(neighbor)) {
queue.offer(neighbor);
}
}
}
}DFS Template (Iterative)
java example
public static void dfs(Node start) {
Deque<Node> stack = new ArrayDeque<>();
Set<Node> visited = new HashSet<>();
stack.push(start);
while (!stack.isEmpty()) {
Node current = stack.pop();
if (!visited.add(current)) continue;
process(current);
for (Node neighbor : current.getNeighbors()) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}Bounded Buffer
java example
public class BoundedBuffer<T> {
private final ArrayDeque<T> buffer;
private final int maxSize;
public BoundedBuffer(int maxSize) {
this.buffer = new ArrayDeque<>(maxSize);
this.maxSize = maxSize;
}
public void add(T item) {
if (buffer.size() >= maxSize) {
buffer.pollFirst(); // Remove oldest
}
buffer.addLast(item);
}
public List<T> getAll() {
return new ArrayList<>(buffer);
}
}Common Mistakes
1. Adding Null
java example
deque.offer(null); // NPE! Use a sentinel object instead if needed2. Using as List (No Random Access)
java example
// ArrayDeque does NOT implement List — no get(index)!
// deque.get(3); // Compilation error!
// If you need index access, use ArrayList3. Confusing Push Direction
Example
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // [1]
stack.push(2); // [2, 1] — push adds to FIRST (head)!
stack.push(3); // [3, 2, 1]
// Iteration gives: 3 2 1 (from head to tail)
// pop() returns: 3 (from head)
4. Not Pre-sizing When Size is Known
Example
// WRONG — multiple resizes for large collections
Deque<String> deque = new ArrayDeque<>(); // Capacity 16
for (int i = 0; i < 10000; i++) deque.add("item" + i);
// Resizes: 16→32→64→128→256→512→1024→2048→4096→8192→16384
// BETTER — pre-allocate
Deque<String> deque = new ArrayDeque<>(16384);
Interview Questions
Q1: How does ArrayDeque work internally?
A: It uses a resizable circular array. Two pointers (head and tail) track the front and back. Elements wrap around the array, so both addFirst and addLast are O(1). When full, it doubles the capacity.
Q2: Why can't ArrayDeque store null?
A: Because it uses null internally as a sentinel to detect empty slots. poll() returns null when empty, so allowing null elements would make it ambiguous.
Q3: Why is ArrayDeque faster than LinkedList for queue/stack operations?
A: Better cache locality (contiguous memory), no per-element object allocation (no Node objects), and lower memory overhead (~8 bytes vs ~48 bytes per element).
Q4: What is the initial capacity of ArrayDeque?
A: 16 elements (or the next power of 2 ≥ the specified initial capacity).
Q5: What happens when ArrayDeque is full?
A: It doubles its internal array capacity and copies elements to the new array in correct logical order (unwrapping the circular buffer).
Q6: Can ArrayDeque be used as both a stack and a queue?
A: Yes. As a stack: push/pop/peek (LIFO from the head). As a queue: offer/poll/peek (FIFO — add to tail, remove from head).
Q7: What is the thread-safe alternative to ArrayDeque?
A: ConcurrentLinkedDeque (non-blocking) or LinkedBlockingDeque (blocking). There is no ArrayBlockingDeque in the JDK.
Q8: Why is ArrayDeque preferred over Stack class?
A: (1) ArrayDeque is faster — no synchronization overhead. (2) Stack extends Vector, exposing List methods that violate LIFO semantics. (3) ArrayDeque properly restricts access to ends only. (4) ArrayDeque implements Deque interface for consistent API. (5) ArrayDeque uses a resizable circular array with better cache locality.
Q9: How does ArrayDeque's circular array work internally?
A: ArrayDeque maintains a head and tail index in a backing array. Elements are added/removed by moving these indices. When head or tail wraps around the array end, it continues from the opposite side (circular). This allows O(1) operations at both ends without shifting elements.
Q10: Why doesn't ArrayDeque allow null elements?
A: ArrayDeque uses null as a sentinel value internally to detect empty slots and distinguish between "no element" and "element present." If null elements were allowed, pollFirst() returning null would be ambiguous — does it mean "deque is empty" or "the element was null"?
Q11: What is the initial capacity and growth strategy of ArrayDeque?
A: Default initial capacity is 16 (must be power of 2). When full, capacity doubles. The power-of-2 constraint enables efficient modular arithmetic using bitwise AND ((head - 1) & (elements.length - 1)) instead of expensive modulo operation.
Q12: When should you use ArrayDeque vs LinkedList for queue operations?
A: Almost always prefer ArrayDeque. It has better cache locality (contiguous memory), lower memory overhead (no node objects), and faster operations. LinkedList only wins when you need: (1) null elements, (2) frequent removal from middle via iterator, (3) simultaneous List interface access.
Summary
| Aspect | ArrayDeque |
|---|---|
| Structure | Circular resizable array |
| All deque operations | O(1) amortized |
| Null elements | ❌ Not allowed |
| Thread-safe | No |
| Memory efficiency | Excellent (contiguous, minimal overhead) |
| Use as stack | ✅ Preferred over java.util.Stack |
| Use as queue | ✅ Preferred over LinkedList |
| Initial capacity | 16 (always power of 2) |
| Growth | Doubles |
| The go-to choice for | Stack, Queue, or Deque — ArrayDeque is the default |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for ArrayDeque in Java.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, collections, framework, queue
Related Java Master Course Topics
Continue learning this concept
Collections FrameworkDeque Interface in JavaComplete guide to Java Deque interface — double-ended queue operations, stack and queue usage, method families, comparison of implementations, and best practices.Collections FrameworkPriorityQueue in JavaComplete guide to Java PriorityQueue — binary heap implementation, min-heap and max-heap, internal working, heapify operations, comparison with other queues, and practical applications.Collections FrameworkCollections Framework OverviewComplete guide to Java Collections Framework covering hierarchy, interfaces, implementations, algorithms, and choosing the right collection for your use case.Collections FrameworkCollections Practice ProgramsComprehensive Java Collections practice programs covering List, Set, Map, Queue operations with solutions, explanations, and time complexity analysis.Collections FrameworkComparable vs Comparator in JavaDeep dive into Comparable and Comparator interfaces in Java — natural ordering, custom sorting, lambda expressions, method references, and practical comparisons with examples.Collections FrameworkGenerics in JavaComplete guide to Java Generics — type parameters, bounded types, wildcards, type erasure, generic methods, generic classes, and common patterns with practical examples.