[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":85,"_72":86,"_35":87},"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":52,"_62":63,"_64":65,"_66":67,"_68":69,"_70":71},"id",73,"title","LinkedList","slug","dsa-cheatsheet-part-2-linkedlist","excerpt","Visual guide to LinkedList: node-based structure, O(1) insert/delete at ends, O(n) access. See pointer manipulation in action.","# LinkedList\n\n## 📋 Quick Reference\n\n| Property | Value |\n|----------|-------|\n| **Type** | Doubly-linked node sequence |\n| **Access** | O(n) - must traverse from head/tail |\n| **Insert/Delete at Ends** | O(1) |\n| **Insert/Delete at Middle** | O(1) with iterator, O(n) to find position |\n| **Memory** | Extra overhead per node (prev + next pointers) |\n| **Best For** | Frequent insertions/deletions at known positions |\n\n**One-liner**: *Doubly-linked list with O(1) add/remove at ends, but O(n) random access.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how LinkedList manages node connections for insertions and deletions:\n\n```visualizer-linkedlist\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. Add at head/tail - see O(1) pointer updates\n2. Insert in middle - observe node linking\n3. Remove a node - watch pointer rewiring\n4. Traverse the list - see the step-by-step access\n\n---\n\n## 🔧 Key Operations\n\n### Creating\n\n```java\n// Empty list\nLinkedList list = new LinkedList<>();\n\n// From collection\nLinkedList list = new LinkedList<>(existingList);\n\n// As Deque (preferred for queue operations)\nDeque deque = new LinkedList<>();\n```\n\n### Adding Elements\n\n```java\nlist.addFirst(\"first\"); // O(1) - prepend\nlist.addLast(\"last\"); // O(1) - append\nlist.add(\"element\"); // O(1) - same as addLast\nlist.add(2, \"middle\"); // O(n) - insert at index (must traverse)\n\n// Deque methods\nlist.offerFirst(\"first\"); // O(1) - returns boolean\nlist.offerLast(\"last\"); // O(1) - returns boolean\n```\n\n### Accessing\n\n```java\nString first = list.getFirst(); // O(1) - throws if empty\nString last = list.getLast(); // O(1) - throws if empty\nString item = list.get(5); // O(n) - must traverse!\n\n// Safe access (returns null if empty)\nString first = list.peekFirst(); // O(1)\nString last = list.peekLast(); // O(1)\n```\n\n### Removing\n\n```java\nlist.removeFirst(); // O(1) - throws if empty\nlist.removeLast(); // O(1) - throws if empty\nlist.remove(2); // O(n) - by index\nlist.remove(\"element\"); // O(n) - by value (first occurrence)\n\n// Safe removal (returns null if empty)\nlist.pollFirst(); // O(1)\nlist.pollLast(); // O(1)\n```\n\n### Iteration\n\n```java\n// For-each (forward)\nfor (String item : list) { }\n\n// Descending iterator\nIterator desc = list.descendingIterator();\nwhile (desc.hasNext()) {\n String item = desc.next();\n}\n\n// ListIterator (bidirectional, can modify)\nListIterator it = list.listIterator();\nwhile (it.hasNext()) {\n if (it.next().isEmpty()) {\n it.remove(); // O(1) removal at current position!\n }\n}\n```\n\n---\n\n## 📊 Complexity Analysis\n\n| Operation | Time | Notes |\n|-----------|------|-------|\n| `addFirst/Last` | O(1) | Just update pointers |\n| `removeFirst/Last` | O(1) | Just update pointers |\n| `get(i)` | O(n) | Must traverse from head or tail |\n| `add(i, e)` | O(n) | Find position + O(1) insert |\n| `remove(i)` | O(n) | Find position + O(1) remove |\n| `contains(e)` | O(n) | Linear search |\n| `size()` | O(1) | Stored as field |\n\n### Memory Layout\n\n```\nHead → [prev|data|next] ⟷ [prev|data|next] ⟷ [prev|data|next] ← Tail\n null←─┘ └─────────────────────────────→ null\n\nEach node: ~24 bytes overhead (object header + 2 references)\nvs ArrayList: ~4 bytes per element (just the reference)\n```\n\n---\n\n## ✅ When to Use LinkedList\n\n### Good Use Cases\n\n- **Queue/Deque operations** - frequent add/remove at both ends\n- **Iterator-based modifications** - O(1) insert/delete during iteration\n- **Large elements** - moving pointers is cheaper than copying\n- **Frequent splicing** - merging lists is O(1)\n\n### Avoid When\n\n- **Random access needed** - use `ArrayList` instead\n- **Memory is tight** - node overhead is significant\n- **Cache performance matters** - non-contiguous memory\n- **Small elements** - overhead dominates actual data\n\n---\n\n## 🔄 LinkedList as Queue/Stack\n\n```java\n// As Queue (FIFO)\nQueue queue = new LinkedList<>();\nqueue.offer(\"first\"); // Add to tail\nqueue.poll(); // Remove from head\n\n// As Deque (double-ended)\nDeque deque = new LinkedList<>();\ndeque.offerFirst(\"a\"); // Add to head\ndeque.offerLast(\"b\"); // Add to tail\ndeque.pollFirst(); // Remove from head\ndeque.pollLast(); // Remove from tail\n\n// As Stack (LIFO) - but ArrayDeque is preferred\nDeque stack = new LinkedList<>();\nstack.push(\"item\"); // Add to head\nstack.pop(); // Remove from head\n```\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. Using get() in Loops\n\n```java\n// ❌ O(n²) - traverses from start each time!\nfor (int i = 0; i < list.size(); i++) {\n process(list.get(i));\n}\n\n// ✅ O(n) - use iterator\nfor (String item : list) {\n process(item);\n}\n```\n\n### 2. Wrong Data Structure Choice\n\n```java\n// ❌ LinkedList for random access\nLinkedList users = new LinkedList<>();\nUser user = users.get(500); // Traverses 500 nodes!\n\n// ✅ ArrayList for random access\nArrayList users = new ArrayList<>();\nUser user = users.get(500); // Direct array access\n```\n\n### 3. Ignoring ArrayDeque Alternative\n\n```java\n// ❌ LinkedList as stack (higher overhead)\nDeque stack = new LinkedList<>();\n\n// ✅ ArrayDeque is faster for stack/queue operations\nDeque stack = new ArrayDeque<>();\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: When would you use LinkedList over ArrayList?**\n\n> When you need frequent insertions/deletions at both ends (as Deque), or when modifying during iteration using ListIterator. In practice, ArrayList is usually better due to cache locality and lower memory overhead.\n\n**Q: What's the time complexity of get(n/2)?**\n\n> O(n), specifically O(n/2). Java's LinkedList optimizes by starting from the closer end (head or tail), but it's still linear. For index n/2, it traverses n/2 nodes.\n\n**Q: How does LinkedList implement List and Deque?**\n\n> It's a doubly-linked list where each node has prev/next references. Head and tail references enable O(1) operations at both ends, satisfying Deque. The List interface is satisfied by traversing to any index.\n\n**Q: ArrayList vs LinkedList for a queue?**\n\n> Neither is ideal. Use `ArrayDeque` - it has O(1) operations at both ends like LinkedList, but with ArrayList's cache locality and lower memory overhead.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 1: ArrayList](dsa-cheatsheet-part-1-arraylist)\n\n**Next**: [Part 3: HashMap](dsa-cheatsheet-part-3-hashmap)\n\n---\n\n**Visualizer**: `LinkedList` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.617786Z","createdAt","2026-06-10T07:19:25.617993Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",4,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId","seriesOrder",2,"author",{"_31":55,"_98":57,"_99":100,"_101":102,"_103":-5,"_104":-5,"_105":-5,"_106":-5,"_107":-5},"category",{"_31":94,"_72":59,"_35":95,"_75":96,"_97":-5},"tags",[78,79,80,81],"series",{"_31":52,"_72":73,"_35":74,"_75":76,"_77":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":91,"_72":92,"_35":93},{"_31":88,"_72":89,"_35":90},{"_31":85,"_72":86,"_35":87},{"_31":82,"_72":83,"_35":84},256,"O(1) Insert","o(1)-insert",255,"Nodes","nodes",254,"Linkedlist","linkedlist",252,"Data Structure","data-structure",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]