[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":84,"_73":85,"_35":86},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",77,"title","ArrayDeque / Circular Buffer","slug","dsa-cheatsheet-part-6-arraydeque","excerpt","Visual guide to ArrayDeque: circular buffer, O(1) operations at both ends. Watch head/tail pointers wrap around.","# ArrayDeque / Circular Buffer\n\n## 📋 Quick Reference\n\n| Property | Value |\n|----------|-------|\n| **Type** | Resizable circular array |\n| **Add/Remove at Ends** | O(1) amortized |\n| **Random Access** | Not supported (no get(i)) |\n| **Memory** | O(n) - contiguous, cache-friendly |\n| **Null Elements** | Not allowed |\n| **Best For** | Stack, queue, deque operations |\n\n**One-liner**: *Circular buffer providing O(1) operations at both ends - faster than LinkedList for stack/queue.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how ArrayDeque uses circular indexing to avoid shifting elements:\n\n```visualizer-arraydeque\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. Add to front and back - see head/tail pointers move\n2. Remove from both ends - watch circular wrap-around\n3. Fill until resize - observe capacity doubling\n4. Notice: no element shifting needed!\n\n---\n\n## 🔧 Key Operations\n\n### Creating\n\n```java\n// Empty deque (default capacity 16)\nDeque deque = new ArrayDeque<>();\n\n// With initial capacity\nDeque deque = new ArrayDeque<>(100);\n\n// From collection\nDeque deque = new ArrayDeque<>(existingCollection);\n\n// As Stack\nDeque stack = new ArrayDeque<>();\n\n// As Queue\nQueue queue = new ArrayDeque<>();\n```\n\n### Adding Elements\n\n```java\n// At front\ndeque.addFirst(\"first\"); // O(1) - throws if null\ndeque.offerFirst(\"first\"); // O(1) - returns boolean\n\n// At back\ndeque.addLast(\"last\"); // O(1) - throws if null\ndeque.offerLast(\"last\"); // O(1) - returns boolean\ndeque.add(\"element\"); // O(1) - alias for addLast\n\n// Stack operations\ndeque.push(\"item\"); // O(1) - alias for addFirst\n```\n\n### Accessing\n\n```java\n// Front\nString first = deque.getFirst(); // O(1) - throws if empty\nString first = deque.peekFirst(); // O(1) - returns null if empty\nString first = deque.peek(); // O(1) - alias for peekFirst\n\n// Back\nString last = deque.getLast(); // O(1) - throws if empty\nString last = deque.peekLast(); // O(1) - returns null if empty\n```\n\n### Removing\n\n```java\n// From front\nString first = deque.removeFirst(); // O(1) - throws if empty\nString first = deque.pollFirst(); // O(1) - returns null if empty\nString first = deque.poll(); // O(1) - alias for pollFirst\nString first = deque.pop(); // O(1) - alias for removeFirst (stack)\n\n// From back\nString last = deque.removeLast(); // O(1) - throws if empty\nString last = deque.pollLast(); // O(1) - returns null if empty\n\n// By value\ndeque.remove(\"element\"); // O(n) - linear search\ndeque.removeFirstOccurrence(\"x\"); // O(n) - from front\ndeque.removeLastOccurrence(\"x\"); // O(n) - from back\n```\n\n### Iteration\n\n```java\n// Forward (front to back)\nfor (String item : deque) { }\n\n// Backward (back to front)\nIterator desc = deque.descendingIterator();\nwhile (desc.hasNext()) {\n String item = desc.next();\n}\n```\n\n---\n\n## 📊 Complexity Analysis\n\n| Operation | Time | Notes |\n|-----------|------|-------|\n| `addFirst/Last` | O(1)* | *Amortized - O(n) when resize needed |\n| `removeFirst/Last` | O(1) | Just move pointer |\n| `peekFirst/Last` | O(1) | Direct access |\n| `remove(Object)` | O(n) | Linear search |\n| `contains(Object)` | O(n) | Linear search |\n| `size()` | O(1) | Stored field |\n\n### Circular Buffer Mechanism\n\n```\nArray: [ _, _, C, D, E, F, _, _ ]\n ^ ^\n head tail\n\nAfter addFirst(\"B\"):\nArray: [ _, B, C, D, E, F, _, _ ]\n ^ ^\n head tail\n\nAfter addLast(\"G\"):\nArray: [ _, B, C, D, E, F, G, _ ]\n ^ ^\n head tail\n\nWrap-around example:\nArray: [ G, H, C, D, E, F, _, _ ]\n ^ ^\n tail head\n(head > tail means wrapped around)\n```\n\n---\n\n## ✅ When to Use ArrayDeque\n\n### Good Use Cases\n\n- **Stack implementation** - faster than Stack class\n- **Queue implementation** - faster than LinkedList\n- **Double-ended queue** - add/remove both ends\n- **Sliding window** - efficient window operations\n- **BFS traversal** - fast queue for graph algorithms\n\n### Avoid When\n\n- **Need random access** - no get(index) method\n- **Need null elements** - ArrayDeque prohibits null\n- **Concurrent access** - use ConcurrentLinkedDeque\n- **Need List interface** - use LinkedList instead\n\n---\n\n## 🔄 ArrayDeque vs LinkedList vs Stack\n\n| Feature | ArrayDeque | LinkedList | Stack |\n|---------|------------|------------|-------|\n| Push/Pop | O(1) | O(1) | O(1) |\n| Memory | Compact | Node overhead | Legacy |\n| Cache | Friendly | Poor | N/A |\n| Null | Not allowed | Allowed | Allowed |\n| Random Access | No | O(n) | O(n) |\n| Recommended | ✅ Yes | For List ops | ❌ No |\n\n```java\n// ✅ Preferred for stack\nDeque stack = new ArrayDeque<>();\nstack.push(\"item\");\nstack.pop();\n\n// ❌ Legacy - avoid\nStack stack = new Stack<>(); // Synchronized, slow\n```\n\n---\n\n## 🧩 Common Patterns\n\n### Stack Usage\n\n```java\nDeque stack = new ArrayDeque<>();\nstack.push(1);\nstack.push(2);\nstack.push(3);\n// Stack: [3, 2, 1] (3 is at front)\n\nwhile (!stack.isEmpty()) {\n System.out.println(stack.pop()); // 3, 2, 1\n}\n```\n\n### Queue Usage\n\n```java\nQueue queue = new ArrayDeque<>();\nqueue.offer(1);\nqueue.offer(2);\nqueue.offer(3);\n// Queue: [1, 2, 3] (1 is at front)\n\nwhile (!queue.isEmpty()) {\n System.out.println(queue.poll()); // 1, 2, 3\n}\n```\n\n### Sliding Window Maximum\n\n```java\npublic int[] maxSlidingWindow(int[] nums, int k) {\n Deque deque = new ArrayDeque<>(); // Store indices\n int[] result = new int[nums.length - k + 1];\n\n for (int i = 0; i < nums.length; i++) {\n // Remove indices outside window\n while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {\n deque.pollFirst();\n }\n\n // Remove smaller elements (useless)\n while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {\n deque.pollLast();\n }\n\n deque.offerLast(i);\n\n if (i >= k - 1) {\n result[i - k + 1] = nums[deque.peekFirst()];\n }\n }\n\n return result;\n}\n```\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. Adding Null Elements\n\n```java\n// ❌ Throws NullPointerException\ndeque.add(null);\n\n// ✅ Use Optional or sentinel value\ndeque.add(Optional.ofNullable(value).orElse(DEFAULT));\n```\n\n### 2. Using Wrong Interface Type\n\n```java\n// ❌ Using concrete type limits flexibility\nArrayDeque deque = new ArrayDeque<>();\n\n// ✅ Use interface type\nDeque deque = new ArrayDeque<>(); // For deque operations\nQueue queue = new ArrayDeque<>(); // For queue operations\n```\n\n### 3. Expecting get(index)\n\n```java\n// ❌ ArrayDeque has no random access\nString item = deque.get(5); // Compilation error!\n\n// ✅ Convert to array or list if index access needed\nString[] arr = deque.toArray(new String[0]);\nString item = arr[5];\n```\n\n### 4. Using LinkedList for Stack/Queue\n\n```java\n// ❌ LinkedList has higher overhead\nDeque stack = new LinkedList<>();\n\n// ✅ ArrayDeque is more efficient\nDeque stack = new ArrayDeque<>();\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: Why prefer ArrayDeque over LinkedList for stack/queue?**\n\n> 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.\n\n**Q: Why can't ArrayDeque contain null?**\n\n> 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\".\n\n**Q: How does ArrayDeque achieve O(1) at both ends?**\n\n> 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.\n\n**Q: ArrayDeque vs PriorityQueue?**\n\n> 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.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 5: PriorityQueue / Heap](dsa-cheatsheet-part-5-priorityqueue)\n\n**Next**: [Part 7: LinkedHashMap](dsa-cheatsheet-part-7-linkedhashmap)\n\n---\n\n**Visualizer**: `ArrayDeque` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.645805Z","createdAt","2026-06-10T07:19:25.646055Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",5,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",4,"seriesOrder",6,"author",{"_31":55,"_102":57,"_103":104,"_105":106,"_107":-5,"_108":-5,"_109":-5,"_110":-5,"_111":-5},"category",{"_31":64,"_73":59,"_35":99,"_76":100,"_101":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Interactive Data Structures & Algorithms","dsa-visualized-cheatsheet","description","A concise, visual reference for essential data structures and algorithms. Each article features an interactive visualizer showing how the structure/algorithm works step-by-step, along with complexity analysis, use cases, and quick reference code. Perfect for interview prep, quick review, or learning by visualization.","isActive",{"_31":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},271,"Stack","stack",270,"Queue","queue",268,"Deque","deque",269,"Circular Buffer","circular-buffer",267,"Arraydeque","arraydeque","algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]