[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":81,"_71":82,"_35":83},"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":52,"_55":56,"_57":58,"_59":52,"_60":61,"_62":16,"_63":64,"_65":66,"_67":68,"_69":70},"id",72,"title","ArrayList / Dynamic Array","slug","dsa-cheatsheet-part-1-arraylist","excerpt","Visual guide to ArrayList: dynamic resizing, amortized O(1) append, O(n) insert. Interactive visualizer shows resize operations.","# ArrayList / Dynamic Array\n\n## 📋 Quick Reference\n\n| Property | Value |\n|----------|-------|\n| **Type** | Sequential, indexed collection |\n| **Access** | O(1) random access by index |\n| **Insert/Delete** | O(n) - requires shifting elements |\n| **Append** | O(1) amortized (O(n) when resizing) |\n| **Memory** | Contiguous block, cache-friendly |\n| **Best For** | Random access, iteration, append-heavy workloads |\n\n**One-liner**: *Dynamic array that grows automatically when full, providing O(1) index access.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how ArrayList handles operations including the automatic resize when capacity is exceeded:\n\n```visualizer-arraylist\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. Add elements until resize triggers (capacity doubles)\n2. Insert at index 0 - see all elements shift right\n3. Remove from middle - see elements shift left\n4. Access by index - instant O(1) operation\n\n---\n\n## 🔧 Key Operations\n\n### Creating\n\n```java\n// Empty list (default capacity 10)\nList list = new ArrayList<>();\n\n// With initial capacity (avoid resizing)\nList list = new ArrayList<>(100);\n\n// From existing collection\nList list = new ArrayList<>(existingList);\n\n// Java 9+ immutable (for fixed data)\nList list = List.of(\"a\", \"b\", \"c\");\n```\n\n### Adding Elements\n\n```java\nlist.add(\"element\"); // O(1) amortized - append\nlist.add(0, \"first\"); // O(n) - insert at index, shifts all\nlist.addAll(otherList); // O(n) - append all\n```\n\n### Accessing\n\n```java\nString item = list.get(2); // O(1) - direct index access\nint idx = list.indexOf(\"x\"); // O(n) - linear search\nboolean has = list.contains(x);// O(n) - linear search\n```\n\n### Removing\n\n```java\nlist.remove(0); // O(n) - by index, shifts elements\nlist.remove(\"element\"); // O(n) - by value, searches then shifts\nlist.clear(); // O(n) - remove all\n```\n\n### Iteration\n\n```java\n// For-each (preferred)\nfor (String item : list) { }\n\n// Index-based (when index needed)\nfor (int i = 0; i < list.size(); i++) {\n String item = list.get(i); // O(1) each access\n}\n\n// Stream\nlist.stream().filter(x -> x.length() > 3).toList();\n```\n\n---\n\n## 📊 Complexity Analysis\n\n| Operation | Time | Notes |\n|-----------|------|-------|\n| `get(i)` | O(1) | Direct array access |\n| `set(i, e)` | O(1) | Direct array access |\n| `add(e)` | O(1)* | *Amortized - O(n) when resize needed |\n| `add(i, e)` | O(n) | Shifts elements right |\n| `remove(i)` | O(n) | Shifts elements left |\n| `contains(e)` | O(n) | Linear search |\n| `size()` | O(1) | Stored as field |\n\n### Resize Strategy\n\n```\nCapacity doubles: 10 → 20 → 40 → 80 → 160 → ...\n\nGrowth factor = 1.5x (in some implementations)\nNew capacity = oldCapacity + (oldCapacity >> 1)\n```\n\n---\n\n## ✅ When to Use ArrayList\n\n### Good Use Cases\n\n- **Random access needed** - get/set by index frequently\n- **Mostly appending** - add to end is O(1) amortized\n- **Iteration-heavy** - cache-friendly memory layout\n- **Known size** - pre-size to avoid resizing\n\n### Avoid When\n\n- **Frequent insert/delete at front** - use `ArrayDeque` or `LinkedList`\n- **Frequent insert/delete in middle** - consider `LinkedList`\n- **Need thread safety** - use `CopyOnWriteArrayList` or synchronize\n- **Primitive types** - boxing overhead; use primitive arrays or specialized libs\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. ConcurrentModificationException\n\n```java\n// ❌ Wrong - modifying during iteration\nfor (String item : list) {\n if (item.isEmpty()) {\n list.remove(item); // Throws ConcurrentModificationException!\n }\n}\n\n// ✅ Correct - use Iterator.remove()\nIterator it = list.iterator();\nwhile (it.hasNext()) {\n if (it.next().isEmpty()) {\n it.remove();\n }\n}\n\n// ✅ Or use removeIf (Java 8+)\nlist.removeIf(String::isEmpty);\n```\n\n### 2. Forgetting Initial Capacity\n\n```java\n// ❌ Multiple resizes for known size\nList users = new ArrayList<>();\nfor (int i = 0; i < 10000; i++) {\n users.add(loadUser(i)); // Resizes ~13 times!\n}\n\n// ✅ Pre-size when you know the count\nList users = new ArrayList<>(10000);\n```\n\n### 3. Sublist Gotcha\n\n```java\nList sub = list.subList(0, 5);\nlist.add(\"new\"); // Modifies original\nsub.get(0); // Throws ConcurrentModificationException!\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: When would you choose ArrayList over LinkedList?**\n\n> Almost always. ArrayList has O(1) random access, better cache locality, and lower memory overhead. LinkedList only wins for frequent insertions/deletions at known positions with an iterator, which is rare.\n\n**Q: What happens when ArrayList is full?**\n\n> It creates a new array ~1.5x larger, copies all elements, then discards the old array. This is O(n) but happens infrequently enough that add() is O(1) amortized.\n\n**Q: How would you make ArrayList thread-safe?**\n\n> Options: `Collections.synchronizedList(list)`, `CopyOnWriteArrayList` (for read-heavy), or external synchronization. ConcurrentHashMap has no direct List equivalent.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 0: Series Overview](dsa-cheatsheet-part-0-overview)\n\n**Next**: [Part 2: LinkedList](dsa-cheatsheet-part-2-linkedlist)\n\n---\n\n**Visualizer**: `ArrayList` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.611662Z","createdAt","2026-06-10T07:19:25.611825Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",3,"estimatedReadingTime","authorId","authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",4,"seriesOrder","author",{"_31":52,"_97":56,"_98":99,"_100":101,"_102":-5,"_103":-5,"_104":-5,"_105":-5,"_106":-5},"category",{"_31":93,"_71":58,"_35":94,"_74":95,"_96":-5},"tags",[77,78,79,80],"series",{"_31":61,"_71":72,"_35":73,"_74":75,"_76":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":90,"_71":91,"_35":92},{"_31":87,"_71":88,"_35":89},{"_31":84,"_71":85,"_35":86},{"_31":81,"_71":82,"_35":83},253,"O(1) Access","o(1)-access",251,"Dynamic Array","dynamic-array",252,"Data Structure","data-structure",250,"Arraylist","arraylist",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]