ArrayDeque / Circular Buffer

📋 Quick Reference

Property	Value
Type	Resizable circular array
Add/Remove at Ends	O(1) amortized
Random Access	Not supported (no get(i))
Memory	O(n) - contiguous, cache-friendly
Null Elements	Not allowed
Best For	Stack, queue, deque operations

One-liner: Circular buffer providing O(1) operations at both ends - faster than LinkedList for stack/queue.

🎮 Interactive Visualizer

Watch how ArrayDeque uses circular indexing to avoid shifting elements:

ArrayDeque
O(1) all opsCircular buffer
1 / 13
Initialize ArrayDeque with capacity 8. Circular buffer: head and tail wrap around.
Use cases:Sliding window, BFS queue, undo/redo stacks, task scheduling
vs LinkedList:ArrayDeque is faster (cache-friendly), use LinkedList only for null values
Internal Array (capacity: 8)
0∅
1∅
2∅
3∅
4∅
5∅
6∅
7∅
H: 0
T: 0
Logical Order (front → back):
Empty deque
Circular indexing:next = (index + 1) & (capacity - 1)
prev = (index - 1) & (capacity - 1)
Bitwise AND for power-of-2 capacity (faster than modulo)
Pseudocode
1class ArrayDeque<E> {
2  E[] elements;
3  int head = 0, tail = 0;
4 
5  void addFirst(E e) {
6    head = (head - 1) & (capacity - 1);
7    elements[head] = e;
8    if (head == tail) grow();
9  }
10 
11  void addLast(E e) {
12    elements[tail] = e;
13    tail = (tail + 1) & (capacity - 1);
14    if (head == tail) grow();
15  }
16 
17  E removeFirst() {
18    E e = elements[head];
19    elements[head] = null;
20    head = (head + 1) & (capacity - 1);
21    return e;
22  }
23 
24  E removeLast() {
25    tail = (tail - 1) & (capacity - 1);
26    E e = elements[tail];
27    elements[tail] = null;
28    return e;
29  }
30}
Variables
head
=0
tail
=0
capacity
=8
size
=0
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Head pointer
Head pointer
Tail pointer
Tail pointer
Added element
Added element
Removed element
Removed element
Resize
Resize
P · [ ] · R
Loading visualizer...

Try these operations:

Add to front and back - see head/tail pointers move
Remove from both ends - watch circular wrap-around
Fill until resize - observe capacity doubling
Notice: no element shifting needed!

🔧 Key Operations

Creating

JAVA(14 lines)
Code
Loading syntax highlighter...

Adding Elements

JAVA(11 lines)
Code
Loading syntax highlighter...

Accessing

JAVA(8 lines)
Code
Loading syntax highlighter...

Removing

JAVA(14 lines)
Code
Loading syntax highlighter...

Iteration

JAVA(8 lines)
Code
Loading syntax highlighter...

📊 Complexity Analysis

Operation	Time	Notes
`addFirst/Last`	O(1)*	*Amortized - O(n) when resize needed
`removeFirst/Last`	O(1)	Just move pointer
`peekFirst/Last`	O(1)	Direct access
`remove(Object)`	O(n)	Linear search
`contains(Object)`	O(n)	Linear search
`size()`	O(1)	Stored field

Circular Buffer Mechanism

Array: [ _, _, C, D, E, F, _, _ ]
              ^           ^
             head        tail

After addFirst("B"):
Array: [ _, B, C, D, E, F, _, _ ]
           ^              ^
          head           tail

After addLast("G"):
Array: [ _, B, C, D, E, F, G, _ ]
           ^                 ^
          head              tail

Wrap-around example:
Array: [ G, H, C, D, E, F, _, _ ]
              ^           ^
             tail        head
(head > tail means wrapped around)

✅ When to Use ArrayDeque

Good Use Cases

Stack implementation - faster than Stack class
Queue implementation - faster than LinkedList
Double-ended queue - add/remove both ends
Sliding window - efficient window operations
BFS traversal - fast queue for graph algorithms

Avoid When

Need random access - no get(index) method
Need null elements - ArrayDeque prohibits null
Concurrent access - use ConcurrentLinkedDeque
Need List interface - use LinkedList instead

🔄 ArrayDeque vs LinkedList vs Stack

Feature	ArrayDeque	LinkedList	Stack
Push/Pop	O(1)	O(1)	O(1)
Memory	Compact	Node overhead	Legacy
Cache	Friendly	Poor	N/A
Null	Not allowed	Allowed	Allowed
Random Access	No	O(n)	O(n)
Recommended	✅ Yes	For List ops	❌ No

JAVA(7 lines)
Code
Loading syntax highlighter...

🧩 Common Patterns

Stack Usage

JAVA(9 lines)
Code
Loading syntax highlighter...

Queue Usage

JAVA(9 lines)
Code
Loading syntax highlighter...

Sliding Window Maximum

JAVA(24 lines)
Code
Loading syntax highlighter...

⚠️ Common Pitfalls

1. Adding Null Elements

JAVA(5 lines)
Code
Loading syntax highlighter...

2. Using Wrong Interface Type

JAVA(6 lines)
Code
Loading syntax highlighter...

3. Expecting get(index)

JAVA(6 lines)
Code
Loading syntax highlighter...

4. Using LinkedList for Stack/Queue

JAVA(5 lines)
Code
Loading syntax highlighter...

🎤 Interview Tips

Q: Why prefer ArrayDeque over LinkedList for stack/queue?

"

ArrayDeque uses a contiguous array (better cache locality), has no node allocation overhead, and provides the same O(1) operations. LinkedList has per-node memory overhead and poor cache performance.

Q: Why can't ArrayDeque contain null?

"

Null is used as a special value to indicate an empty slot in the circular buffer. If null were allowed, you couldn't distinguish between "no element" and "element is null".

Q: How does ArrayDeque achieve O(1) at both ends?

"

It uses a circular buffer with head and tail indices. Adding/removing just moves these indices (with modulo for wrap-around). No element shifting is needed.

Q: ArrayDeque vs PriorityQueue?

"

ArrayDeque maintains insertion order with O(1) access to both ends. PriorityQueue maintains heap order with O(1) access only to minimum. Choose based on whether you need FIFO/LIFO or priority ordering.

Previous: Part 5: PriorityQueue / Heap

Next: Part 7: LinkedHashMap

Visualizer: ArrayDeque from @tomaszjarosz/react-visualizers