[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":92,"_73":93,"_35":94},"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",103,"title","LinkedList Deep Dive","slug","java-collections-part-7-linkedlist-deep-dive","excerpt","Analyze LinkedList's doubly-linked structure, ~40 bytes per node overhead, O(n) random access limitations, and when LinkedList actually outperforms ArrayList.","# Java Collections Part 7: LinkedList - When Linked Structures Win\n\nLinkedList is one of the most misunderstood data structures in Java. Many developers reach for it thinking \"insertions are O(1)\" without understanding the full picture. The reality is nuanced: LinkedList wins in specific scenarios but loses badly in others due to cache locality and memory overhead.\n\nThis article separates myth from reality, showing you exactly when LinkedList beats ArrayList and when it doesn't - backed by understanding of the internals and real benchmarks.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Internal Structure | Doubly-linked list of Node objects |\n| Node Overhead | ~40 bytes per element (header + 3 references) |\n| Random Access | O(n) - must traverse from head or tail |\n| Insert at Ends | O(1) - just update references |\n| Insert with Iterator | O(1) - if you have the position |\n| Implements | List, Deque, Queue |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Explain the node structure**: How doubly-linked nodes work\n- **Understand the real trade-offs**: Memory overhead and cache locality\n- **Know when LinkedList wins**: The specific scenarios where it excels\n- **Use LinkedList as Deque/Queue**: Its strength as a double-ended queue\n- **Make informed decisions**: ArrayList vs LinkedList with confidence\n\n### Interactive Visualizer\n\nWatch LinkedList operations in action - see how addFirst/addLast work in O(1) while indexed access requires O(n) traversal:\n\n```visualizer-linkedlist\ncontrols: true\n```\n\n---\n\n## 🔥 Production Story: The 10x Slowdown\n\nA team was optimizing a document processing service. They noticed the code frequently inserted elements in the middle of a list:\n\n```java\n// Original code\npublic void processDocument(List paragraphs) {\n List result = new ArrayList<>();\n\n for (Paragraph p : paragraphs) {\n int insertPos = findInsertionPoint(result, p);\n result.add(insertPos, p); // Middle insertion\n }\n}\n```\n\n\"ArrayList is slow for middle insertions,\" someone said. \"Let's use LinkedList!\"\n\n```java\n// \"Optimized\" code\npublic void processDocument(List paragraphs) {\n List result = new LinkedList<>(); // Changed!\n\n for (Paragraph p : paragraphs) {\n int insertPos = findInsertionPoint(result, p);\n result.add(insertPos, p); // Still using index-based add!\n }\n}\n```\n\n**Result:** The API became 10x slower!\n\n**Why?** The code was using `add(int index, E element)`, which requires:\n- ArrayList: O(n) to shift elements\n- LinkedList: O(n) to FIND the position, then O(1) to insert\n\n```java\n// LinkedList.add(index, element) internally:\npublic void add(int index, E element) {\n checkPositionIndex(index);\n if (index == size)\n linkLast(element);\n else\n linkBefore(element, node(index)); // node(index) is O(n)!\n}\n\n// node(index) traverses to find the node:\nNode node(int index) {\n if (index < (size >> 1)) { // First half: start from head\n Node x = first;\n for (int i = 0; i < index; i++)\n x = x.next;\n return x;\n } else { // Second half: start from tail\n Node x = last;\n for (int i = size - 1; i > index; i--)\n x = x.prev;\n return x;\n }\n}\n```\n\nPlus, LinkedList's scattered memory layout caused cache misses, making each traversal slower than ArrayList's contiguous memory.\n\n**The fix:** Use ListIterator for position-aware insertion:\n\n```java\n// Actually optimized code\npublic void processDocument(List paragraphs) {\n LinkedList result = new LinkedList<>();\n ListIterator iterator = result.listIterator();\n\n for (Paragraph p : paragraphs) {\n // Move iterator to correct position\n while (iterator.hasNext() && shouldInsertBefore(iterator.next(), p)) {\n // iterator moves forward\n }\n iterator.add(p); // O(1) insertion at iterator position!\n }\n}\n```\n\n**Lesson:** LinkedList only wins when you already have a position reference (via iterator). Index-based access is always O(n).\n\n---\n\n## 🧠 Mental Model: The Chain of Boxes\n\nThink of LinkedList as a chain where each box knows its neighbors:\n\n```text\n┌─────────────────────────────────────────────────────────────────┐\n│ LINKEDLIST STRUCTURE │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ LinkedList object: │\n│ ┌───────────────────────┐ │\n│ │ first ───────────┐ │ │\n│ │ last ─────────┐ │ │ │\n│ │ size = 4 │ │ │ │\n│ └───────────────│──│────┘ │\n│ │ │ │\n│ │ └─────────────────────────────────┐ │\n│ ↓ ↓ │\n│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │\n│ │ Node │←→ │ Node │←→ │ Node │←→ │ Node │ │\n│ │┌───────┐│ │┌───────┐│ │┌───────┐│ │┌───────┐│ │\n│ ││ prev ││ ││ prev ││ ││ prev ││ ││ prev ││ │\n│ ││ item:A││ ││ item:B││ ││ item:C││ ││ item:D││ │\n│ ││ next ││ ││ next ││ ││ next ││ ││ next ││ │\n│ │└───────┘│ │└───────┘│ │└───────┘│ │└───────┘│ │\n│ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │\n│ ↑ ↑ │\n│ first last │\n│ │\n│ Each Node knows: │\n│ - prev: previous node (or null if first) │\n│ - item: the actual element │\n│ - next: next node (or null if last) │\n│ │\n│ INSERTION at position: Just update 4 references │\n│ ACCESS by index: Must walk from first or last │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n**Key insight:** No shifting of elements, but no direct access either. Every operation requires finding the node first.\n\n---\n\n## 🔬 Deep Dive\n\n### 1. The Node Structure\n\n```java\n// ✅ From JDK source\npublic class LinkedList extends AbstractSequentialList\n implements List, Deque, Cloneable, Serializable {\n\n transient int size = 0;\n transient Node first; // Pointer to first node\n transient Node last; // Pointer to last node\n\n private static class Node {\n E item; // The actual element\n Node next; // Reference to next node\n Node prev; // Reference to previous node\n\n Node(Node prev, E element, Node next) {\n this.item = element;\n this.next = next;\n this.prev = prev;\n }\n }\n}\n```\n\n### 2. Memory Overhead\n\nEach element in LinkedList requires a Node object:\n\n```text\n┌─────────────────────────────────────────────────────────────────┐\n│ MEMORY COMPARISON │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ ArrayList storing 1000 Strings: │\n│ ┌──────────────────────────────────────────┐ │\n│ │ ArrayList object: ~32 bytes │ │\n│ │ Object[] elementData: ~16 + 8000 bytes│ (8 bytes/ref) │\n│ │ Total: ~8,048 bytes │ │\n│ └──────────────────────────────────────────┘ │\n│ │\n│ LinkedList storing 1000 Strings: │\n│ ┌──────────────────────────────────────────┐ │\n│ │ LinkedList object: ~32 bytes │ │\n│ │ 1000 Node objects: ~40,000 bytes │ │\n│ │ Each Node: │ │\n│ │ - Object header: 12 bytes │ │\n│ │ - item reference: 8 bytes │ │\n│ │ - prev reference: 8 bytes │ │\n│ │ - next reference: 8 bytes │ │\n│ │ - Padding: 4 bytes │ │\n│ │ Total per node: ~40 bytes │ │\n│ │ Total: ~40,032 bytes │ │\n│ └──────────────────────────────────────────┘ │\n│ │\n│ LinkedList uses ~5x more memory than ArrayList! │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### 3. Cache Locality Problem\n\nThis is why LinkedList often loses to ArrayList even for \"favorable\" operations:\n\n```text\n┌─────────────────────────────────────────────────────────────────┐\n│ CACHE LOCALITY │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ ArrayList memory layout (contiguous): │\n│ ┌────────────────────────────────────────────────┐ │\n│ │ [ref1][ref2][ref3][ref4][ref5][ref6][ref7][ref8]│ ← One │\n│ └────────────────────────────────────────────────┘ cache │\n│ line │\n│ When CPU loads ref1, it also loads ref2-ref8 into cache │\n│ Next 7 accesses are cache HITS (very fast) │\n│ │\n│ LinkedList memory layout (scattered): │\n│ ┌────────┐ ┌────────┐ ┌────────┐ │\n│ │ Node1 │ │ Node2 │ │ Node3 │ ... │\n│ │ @0x100 │ │ @0x500 │ │ @0x900 │ │\n│ └────────┘ └────────┘ └────────┘ │\n│ ↑ ↑ ↑ │\n│ Scattered across heap - each access is cache MISS │\n│ CPU must fetch from RAM each time (~100x slower) │\n│ │\n│ Result: Even O(1) operations in LinkedList can be slower │\n│ than O(n) operations in ArrayList for small n! │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### 4. Core Operations\n\n**Adding at ends - O(1):**\n\n```java\n// ✅ addFirst - O(1)\nprivate void linkFirst(E e) {\n final Node f = first;\n final Node newNode = new Node<>(null, e, f);\n first = newNode;\n if (f == null)\n last = newNode;\n else\n f.prev = newNode;\n size++;\n modCount++;\n}\n\n// ✅ addLast - O(1)\nvoid linkLast(E e) {\n final Node l = last;\n final Node newNode = new Node<>(l, e, null);\n last = newNode;\n if (l == null)\n first = newNode;\n else\n l.next = newNode;\n size++;\n modCount++;\n}\n```\n\n**Finding a node by index - O(n):**\n\n```java\n// ✅ Optimization: start from closer end\nNode node(int index) {\n if (index < (size >> 1)) { // First half\n Node x = first;\n for (int i = 0; i < index; i++)\n x = x.next;\n return x;\n } else { // Second half\n Node x = last;\n for (int i = size - 1; i > index; i--)\n x = x.prev;\n return x;\n }\n}\n// Best case: O(1) for index 0 or size-1\n// Worst case: O(n/2) for middle index\n// Average: O(n/4)\n```\n\n**Removing with iterator - O(1):**\n\n```java\n// ✅ ListIterator.remove() is O(1) - already at position\npublic void remove() {\n if (lastReturned == null)\n throw new IllegalStateException();\n checkForComodification();\n\n Node lastNext = lastReturned.next;\n unlink(lastReturned); // O(1) - just update references\n\n if (next == lastReturned)\n next = lastNext;\n else\n nextIndex--;\n\n lastReturned = null;\n expectedModCount++;\n}\n```\n\n### 5. LinkedList as Deque\n\nLinkedList implements `Deque`, making it a double-ended queue:\n\n```java\n// ✅ Deque operations - all O(1)\nLinkedList deque = new LinkedList<>();\n\n// Add to ends\ndeque.addFirst(\"A\"); // or offerFirst()\ndeque.addLast(\"B\"); // or offerLast()\n\n// Remove from ends\nString first = deque.removeFirst(); // or pollFirst()\nString last = deque.removeLast(); // or pollLast()\n\n// Peek without removing\nString peekFirst = deque.peekFirst();\nString peekLast = deque.peekLast();\n\n// Stack operations\ndeque.push(\"X\"); // Same as addFirst\nString top = deque.pop(); // Same as removeFirst\n\n// Queue operations\ndeque.offer(\"Y\"); // Same as addLast\nString head = deque.poll(); // Same as removeFirst\n```\n\n### 6. When LinkedList Actually Wins\n\n**Scenario 1: Queue/Deque operations only**\n\n```java\n// ✅ LinkedList excels here\nQueue taskQueue = new LinkedList<>();\ntaskQueue.offer(task); // O(1)\nTask next = taskQueue.poll(); // O(1)\n\n// But ArrayDeque is usually better!\nQueue betterQueue = new ArrayDeque<>();\n```\n\n**Scenario 2: Iterator-based modifications**\n\n```java\n// ✅ LinkedList wins when inserting/removing during iteration\nLinkedList list = new LinkedList<>(data);\nListIterator iter = list.listIterator();\n\nwhile (iter.hasNext()) {\n String item = iter.next();\n if (shouldRemove(item)) {\n iter.remove(); // O(1) for LinkedList!\n }\n if (shouldInsertAfter(item)) {\n iter.add(\"new\"); // O(1) for LinkedList!\n }\n}\n// Same pattern with ArrayList would be O(n) per modification\n```\n\n**Scenario 3: Frequent removes from front**\n\n```java\n// ✅ LinkedList is O(1) for removeFirst\nwhile (!linkedList.isEmpty()) {\n process(linkedList.removeFirst()); // O(1)\n}\n\n// ArrayList is O(n) for remove(0)\nwhile (!arrayList.isEmpty()) {\n process(arrayList.remove(0)); // O(n) - shifts all elements!\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Using get(index) in a Loop\n\n❌ **Problem:**\n```java\nLinkedList list = new LinkedList<>(data);\n\nfor (int i = 0; i < list.size(); i++) {\n String item = list.get(i); // O(n) each call!\n process(item);\n}\n// Total: O(n²)!\n```\n\n✅ **Solution:**\n```java\n// Use iterator or for-each\nfor (String item : list) { // O(n) total\n process(item);\n}\n\n// Or use iterator explicitly\nIterator iter = list.iterator();\nwhile (iter.hasNext()) {\n process(iter.next());\n}\n```\n\n---\n\n### Mistake 2: Thinking Index-Based Add is O(1)\n\n❌ **Problem:**\n```java\nLinkedList list = new LinkedList<>();\n\n// \"LinkedList has O(1) insertion!\"\nfor (int i = 0; i < 10000; i++) {\n int pos = findPosition(i);\n list.add(pos, \"item\" + i); // O(n) to find position!\n}\n```\n\n✅ **Solution:**\n```java\n// Use iterator if you're traversing anyway\nLinkedList list = new LinkedList<>();\nListIterator iter = list.listIterator();\n\nfor (int i = 0; i < 10000; i++) {\n // Move iterator to position\n while (iter.hasNext() && shouldContinue(iter)) {\n iter.next();\n }\n iter.add(\"item\" + i); // O(1) at iterator position\n}\n```\n\n---\n\n### Mistake 3: Using LinkedList as Default List\n\n❌ **Problem:**\n```java\n// \"I might need to insert in the middle someday\"\nList users = new LinkedList<>(); // Wrong default choice\n\n// Then mostly doing:\nusers.add(user); // Both O(1), but ArrayList has better constants\nUser u = users.get(5); // O(n) for LinkedList!\nusers.contains(user); // Same O(n) for both, but ArrayList is faster\n```\n\n✅ **Solution:**\n```java\n// ArrayList should be the default\nList users = new ArrayList<>();\n\n// Only use LinkedList when you specifically need:\n// 1. Deque operations (but consider ArrayDeque)\n// 2. Iterator-based insertion/removal\n// 3. Frequent removeFirst() operations\n```\n\n---\n\n### Mistake 4: Not Using ArrayDeque for Queues\n\n❌ **Problem:**\n```java\n// \"LinkedList implements Queue, perfect!\"\nQueue queue = new LinkedList<>();\n```\n\n✅ **Solution:**\n```java\n// ArrayDeque is almost always better for Queue/Deque\nQueue queue = new ArrayDeque<>();\n\n// ArrayDeque advantages:\n// - No node objects (less memory, better cache)\n// - Faster constant factors\n// - Same O(1) for queue operations\n\n// LinkedList only when you need:\n// - null elements (ArrayDeque doesn't allow)\n// - List interface methods\n```\n\n---\n\n### Mistake 5: Ignoring descendingIterator\n\n❌ **Problem:**\n```java\n// Iterate in reverse with index\nfor (int i = list.size() - 1; i >= 0; i--) {\n process(list.get(i)); // O(n) per call!\n}\n```\n\n✅ **Solution:**\n```java\n// Use descendingIterator for O(n) total\nIterator descIter = list.descendingIterator();\nwhile (descIter.hasNext()) {\n process(descIter.next());\n}\n```\n\n---\n\n## 🐛 Debug This: The Performance Mystery\n\nA developer reports: \"My LinkedList operations are slower than ArrayList!\"\n\n```java\npublic class EventProcessor {\n private LinkedList eventQueue = new LinkedList<>();\n\n public void addEvent(Event event) {\n // Insert in priority order\n int index = 0;\n for (Event e : eventQueue) {\n if (event.getPriority() > e.getPriority()) {\n break;\n }\n index++;\n }\n eventQueue.add(index, event); // Should be O(1)?\n }\n\n public Event getNextEvent() {\n return eventQueue.isEmpty() ? null : eventQueue.removeFirst();\n }\n}\n```\n\n**Why is addEvent() slow? How would you fix it?**\n\n---\n\n**✅ Solution:**\n\nThe code uses `add(index, event)` which is O(n) because it must traverse to find the position, even though it just traversed to calculate the index!\n\n```java\n// The problem:\nfor (Event e : eventQueue) { ... } // Traverse once: O(n)\neventQueue.add(index, event); // Traverse again: O(n)\n// Total: O(2n) with poor cache locality\n```\n\n**Fix using ListIterator:**\n\n```java\npublic class EventProcessor {\n private LinkedList eventQueue = new LinkedList<>();\n\n public void addEvent(Event event) {\n ListIterator iter = eventQueue.listIterator();\n\n while (iter.hasNext()) {\n if (event.getPriority() > iter.next().getPriority()) {\n iter.previous(); // Back up one position\n break;\n }\n }\n iter.add(event); // O(1) - already at position!\n }\n\n public Event getNextEvent() {\n return eventQueue.isEmpty() ? null : eventQueue.removeFirst();\n }\n}\n```\n\n**Or better - use PriorityQueue:**\n\n```java\npublic class EventProcessor {\n private PriorityQueue eventQueue =\n new PriorityQueue<>(Comparator.comparing(Event::getPriority).reversed());\n\n public void addEvent(Event event) {\n eventQueue.offer(event); // O(log n)\n }\n\n public Event getNextEvent() {\n return eventQueue.poll(); // O(log n)\n }\n}\n```\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: FIFO Queue Implementation\n⭐⭐ Difficulty: Medium | ⏱️ Time: 10 minutes\n\n**Task:** Implement a simple task queue using LinkedList's Deque interface.\n\n```java\npublic class TaskQueue {\n // TODO: Use LinkedList as backing store\n // - enqueue(Task) - add to back\n // - dequeue() - remove from front\n // - peek() - view front without removing\n // - isEmpty()\n // - size()\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class TaskQueue {\n private final LinkedList queue = new LinkedList<>();\n\n public void enqueue(Task task) {\n queue.addLast(task); // O(1)\n }\n\n public Task dequeue() {\n return queue.pollFirst(); // O(1), returns null if empty\n }\n\n public Task peek() {\n return queue.peekFirst(); // O(1), returns null if empty\n }\n\n public boolean isEmpty() {\n return queue.isEmpty(); // O(1)\n }\n\n public int size() {\n return queue.size(); // O(1)\n }\n\n // Bonus: dequeue with exception if empty\n public Task dequeueOrThrow() {\n return queue.removeFirst(); // Throws NoSuchElementException if empty\n }\n}\n\n// Usage:\nTaskQueue queue = new TaskQueue();\nqueue.enqueue(new Task(\"Task 1\"));\nqueue.enqueue(new Task(\"Task 2\"));\n\nwhile (!queue.isEmpty()) {\n Task task = queue.dequeue();\n process(task);\n}\n```\n\n---\n\n### Exercise 2: ArrayList vs LinkedList Benchmark\n⭐⭐⭐ Difficulty: Medium | ⏱️ Time: 20 minutes\n\n**Task:** Benchmark different operations to understand the real performance differences.\n\n```java\npublic class ListBenchmark {\n // TODO: Compare ArrayList vs LinkedList for:\n // 1. Sequential add (to end)\n // 2. Random access get(index)\n // 3. Iteration\n // 4. Add at front\n // 5. Remove during iteration\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class ListBenchmark {\n private static final int SIZE = 100_000;\n\n public static void main(String[] args) {\n System.out.println(\"=== List Benchmark (\" + SIZE + \" elements) ===\\n\");\n\n benchmarkAdd();\n benchmarkGet();\n benchmarkIteration();\n benchmarkAddFirst();\n benchmarkRemoveDuringIteration();\n }\n\n static void benchmarkAdd() {\n System.out.println(\"1. Sequential add():\");\n\n List arrayList = new ArrayList<>();\n long start = System.nanoTime();\n for (int i = 0; i < SIZE; i++) {\n arrayList.add(i);\n }\n long arrayTime = System.nanoTime() - start;\n\n List linkedList = new LinkedList<>();\n start = System.nanoTime();\n for (int i = 0; i < SIZE; i++) {\n linkedList.add(i);\n }\n long linkedTime = System.nanoTime() - start;\n\n System.out.printf(\" ArrayList: %d ms%n\", arrayTime / 1_000_000);\n System.out.printf(\" LinkedList: %d ms%n\", linkedTime / 1_000_000);\n System.out.printf(\" Winner: %s%n%n\",\n arrayTime < linkedTime ? \"ArrayList\" : \"LinkedList\");\n }\n\n static void benchmarkGet() {\n System.out.println(\"2. Random access get(index):\");\n\n List arrayList = new ArrayList<>();\n List linkedList = new LinkedList<>();\n for (int i = 0; i < SIZE; i++) {\n arrayList.add(i);\n linkedList.add(i);\n }\n\n Random random = new Random(42);\n int[] indices = random.ints(1000, 0, SIZE).toArray();\n\n long start = System.nanoTime();\n for (int idx : indices) {\n arrayList.get(idx);\n }\n long arrayTime = System.nanoTime() - start;\n\n start = System.nanoTime();\n for (int idx : indices) {\n linkedList.get(idx);\n }\n long linkedTime = System.nanoTime() - start;\n\n System.out.printf(\" ArrayList: %d ms (1000 random gets)%n\", arrayTime / 1_000_000);\n System.out.printf(\" LinkedList: %d ms (1000 random gets)%n\", linkedTime / 1_000_000);\n System.out.printf(\" ArrayList is %.0fx faster%n%n\", (double) linkedTime / arrayTime);\n }\n\n static void benchmarkIteration() {\n System.out.println(\"3. Full iteration:\");\n\n List arrayList = new ArrayList<>();\n List linkedList = new LinkedList<>();\n for (int i = 0; i < SIZE; i++) {\n arrayList.add(i);\n linkedList.add(i);\n }\n\n long sum = 0;\n long start = System.nanoTime();\n for (Integer i : arrayList) {\n sum += i;\n }\n long arrayTime = System.nanoTime() - start;\n\n start = System.nanoTime();\n for (Integer i : linkedList) {\n sum += i;\n }\n long linkedTime = System.nanoTime() - start;\n\n System.out.printf(\" ArrayList: %d ms%n\", arrayTime / 1_000_000);\n System.out.printf(\" LinkedList: %d ms%n\", linkedTime / 1_000_000);\n System.out.printf(\" Winner: %s (cache locality matters!)%n%n\",\n arrayTime < linkedTime ? \"ArrayList\" : \"LinkedList\");\n }\n\n static void benchmarkAddFirst() {\n System.out.println(\"4. Add at front (10000 times):\");\n int ops = 10_000;\n\n List arrayList = new ArrayList<>();\n long start = System.nanoTime();\n for (int i = 0; i < ops; i++) {\n arrayList.add(0, i);\n }\n long arrayTime = System.nanoTime() - start;\n\n LinkedList linkedList = new LinkedList<>();\n start = System.nanoTime();\n for (int i = 0; i < ops; i++) {\n linkedList.addFirst(i);\n }\n long linkedTime = System.nanoTime() - start;\n\n System.out.printf(\" ArrayList: %d ms%n\", arrayTime / 1_000_000);\n System.out.printf(\" LinkedList: %d ms%n\", linkedTime / 1_000_000);\n System.out.printf(\" LinkedList is %.0fx faster%n%n\", (double) arrayTime / linkedTime);\n }\n\n static void benchmarkRemoveDuringIteration() {\n System.out.println(\"5. Remove half elements during iteration:\");\n\n List arrayList = new ArrayList<>();\n List linkedList = new LinkedList<>();\n for (int i = 0; i < SIZE; i++) {\n arrayList.add(i);\n linkedList.add(i);\n }\n\n long start = System.nanoTime();\n arrayList.removeIf(i -> i % 2 == 0);\n long arrayTime = System.nanoTime() - start;\n\n start = System.nanoTime();\n Iterator iter = linkedList.iterator();\n while (iter.hasNext()) {\n if (iter.next() % 2 == 0) {\n iter.remove();\n }\n }\n long linkedTime = System.nanoTime() - start;\n\n System.out.printf(\" ArrayList (removeIf): %d ms%n\", arrayTime / 1_000_000);\n System.out.printf(\" LinkedList (iterator.remove): %d ms%n\", linkedTime / 1_000_000);\n System.out.printf(\" Winner: %s%n\",\n arrayTime < linkedTime ? \"ArrayList\" : \"LinkedList\");\n }\n}\n```\n\n---\n\n### Exercise 3: Simple LRU Cache\n⭐⭐⭐⭐ Difficulty: Hard | ⏱️ Time: 25 minutes\n\n**Task:** Implement a Least Recently Used cache using LinkedList + HashMap.\n\n```java\npublic class LRUCache {\n private final int capacity;\n // TODO: Implement using LinkedList for order and HashMap for lookup\n // - get(key): return value, move to front (most recent)\n // - put(key, value): add/update, move to front, evict if over capacity\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class LRUCache {\n private final int capacity;\n private final Map> map;\n private final LinkedList> order;\n\n private static class Node {\n K key;\n V value;\n\n Node(K key, V value) {\n this.key = key;\n this.value = value;\n }\n }\n\n public LRUCache(int capacity) {\n this.capacity = capacity;\n this.map = new HashMap<>(capacity);\n this.order = new LinkedList<>();\n }\n\n public V get(K key) {\n Node node = map.get(key);\n if (node == null) {\n return null;\n }\n\n // Move to front (most recently used)\n order.remove(node); // O(n) - this is why LinkedHashMap is better\n order.addFirst(node);\n\n return node.value;\n }\n\n public void put(K key, V value) {\n Node existing = map.get(key);\n\n if (existing != null) {\n // Update existing\n existing.value = value;\n order.remove(existing);\n order.addFirst(existing);\n } else {\n // Add new\n Node newNode = new Node<>(key, value);\n\n // Evict if at capacity\n if (map.size() >= capacity) {\n Node lru = order.removeLast(); // Least recently used\n map.remove(lru.key);\n }\n\n map.put(key, newNode);\n order.addFirst(newNode);\n }\n }\n\n public int size() {\n return map.size();\n }\n\n // Better implementation uses LinkedHashMap - see below\n}\n\n// Simpler and faster with LinkedHashMap:\nclass BetterLRUCache extends LinkedHashMap {\n private final int capacity;\n\n public BetterLRUCache(int capacity) {\n super(capacity, 0.75f, true); // accessOrder=true for LRU\n this.capacity = capacity;\n }\n\n @Override\n protected boolean removeEldestEntry(Map.Entry eldest) {\n return size() > capacity;\n }\n}\n```\n\n---\n\n### Exercise 4: Efficient Playlist\n⭐⭐⭐ Difficulty: Medium | ⏱️ Time: 15 minutes\n\n**Task:** Implement a music playlist with efficient add/remove around current position.\n\n```java\npublic class Playlist {\n // TODO: Support:\n // - addAfterCurrent(Song) - O(1)\n // - removeCurrent() - O(1)\n // - next() - move to next song\n // - previous() - move to previous song\n // - current() - get current song\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class Playlist {\n private final LinkedList songs = new LinkedList<>();\n private ListIterator cursor;\n private Song currentSong;\n\n public Playlist() {\n this.cursor = songs.listIterator();\n }\n\n public void addSong(Song song) {\n songs.addLast(song);\n if (currentSong == null) {\n cursor = songs.listIterator();\n next(); // Start at first song\n }\n }\n\n public void addAfterCurrent(Song song) {\n if (cursor == null) {\n addSong(song);\n } else {\n cursor.add(song); // O(1) - adds after cursor position\n }\n }\n\n public Song removeCurrent() {\n if (currentSong == null) {\n return null;\n }\n\n Song removed = currentSong;\n cursor.remove(); // O(1)\n\n // Move to next song if available\n if (cursor.hasNext()) {\n currentSong = cursor.next();\n } else if (cursor.hasPrevious()) {\n currentSong = cursor.previous();\n } else {\n currentSong = null;\n }\n\n return removed;\n }\n\n public Song next() {\n if (cursor.hasNext()) {\n currentSong = cursor.next();\n return currentSong;\n }\n return null;\n }\n\n public Song previous() {\n if (cursor.hasPrevious()) {\n currentSong = cursor.previous();\n return currentSong;\n }\n return null;\n }\n\n public Song current() {\n return currentSong;\n }\n\n public boolean hasNext() {\n return cursor.hasNext();\n }\n\n public boolean hasPrevious() {\n return cursor.hasPrevious();\n }\n\n public int size() {\n return songs.size();\n }\n}\n\nrecord Song(String title, String artist) {}\n\n// Usage:\nPlaylist playlist = new Playlist();\nplaylist.addSong(new Song(\"Song A\", \"Artist 1\"));\nplaylist.addSong(new Song(\"Song B\", \"Artist 2\"));\nplaylist.addSong(new Song(\"Song C\", \"Artist 3\"));\n\nSystem.out.println(playlist.current()); // Song A\nplaylist.next();\nSystem.out.println(playlist.current()); // Song B\nplaylist.addAfterCurrent(new Song(\"New Song\", \"Artist X\"));\nplaylist.next();\nSystem.out.println(playlist.current()); // New Song\n```\n\n---\n\n### Exercise 5: Deque Operations\n⭐⭐ Difficulty: Medium | ⏱️ Time: 10 minutes\n\n**Task:** Demonstrate all Deque operations using LinkedList.\n\n```java\npublic class DequeDemo {\n // TODO: Show all Deque operations:\n // - Adding: addFirst, addLast, offerFirst, offerLast\n // - Removing: removeFirst, removeLast, pollFirst, pollLast\n // - Examining: getFirst, getLast, peekFirst, peekLast\n // - Stack operations: push, pop, peek\n // - Queue operations: offer, poll, peek\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class DequeDemo {\n public static void main(String[] args) {\n LinkedList deque = new LinkedList<>();\n\n System.out.println(\"=== Adding Elements ===\");\n\n // addFirst/addLast - throw exception if capacity limited\n deque.addFirst(\"B\");\n deque.addLast(\"C\");\n deque.addFirst(\"A\");\n System.out.println(\"After adds: \" + deque); // [A, B, C]\n\n // offerFirst/offerLast - return boolean (for capacity-limited deques)\n deque.offerFirst(\"Start\");\n deque.offerLast(\"End\");\n System.out.println(\"After offers: \" + deque); // [Start, A, B, C, End]\n\n System.out.println(\"\\n=== Examining Elements ===\");\n\n // getFirst/getLast - throw NoSuchElementException if empty\n System.out.println(\"First: \" + deque.getFirst()); // Start\n System.out.println(\"Last: \" + deque.getLast()); // End\n\n // peekFirst/peekLast - return null if empty\n System.out.println(\"Peek First: \" + deque.peekFirst()); // Start\n System.out.println(\"Peek Last: \" + deque.peekLast()); // End\n\n System.out.println(\"\\n=== Removing Elements ===\");\n\n // removeFirst/removeLast - throw NoSuchElementException if empty\n String first = deque.removeFirst();\n System.out.println(\"Removed first: \" + first); // Start\n System.out.println(\"Deque: \" + deque); // [A, B, C, End]\n\n // pollFirst/pollLast - return null if empty\n String last = deque.pollLast();\n System.out.println(\"Polled last: \" + last); // End\n System.out.println(\"Deque: \" + deque); // [A, B, C]\n\n System.out.println(\"\\n=== Stack Operations (LIFO) ===\");\n\n LinkedList stack = new LinkedList<>();\n stack.push(\"First\"); // Same as addFirst\n stack.push(\"Second\");\n stack.push(\"Third\");\n System.out.println(\"Stack: \" + stack); // [Third, Second, First]\n\n String top = stack.pop(); // Same as removeFirst\n System.out.println(\"Popped: \" + top); // Third\n System.out.println(\"Peek: \" + stack.peek()); // Second\n\n System.out.println(\"\\n=== Queue Operations (FIFO) ===\");\n\n LinkedList queue = new LinkedList<>();\n queue.offer(\"First\"); // Same as addLast\n queue.offer(\"Second\");\n queue.offer(\"Third\");\n System.out.println(\"Queue: \" + queue); // [First, Second, Third]\n\n String head = queue.poll(); // Same as pollFirst\n System.out.println(\"Polled: \" + head); // First\n System.out.println(\"Peek: \" + queue.peek()); // Second\n\n System.out.println(\"\\n=== Empty Deque Behavior ===\");\n\n LinkedList empty = new LinkedList<>();\n System.out.println(\"peekFirst on empty: \" + empty.peekFirst()); // null\n System.out.println(\"pollFirst on empty: \" + empty.pollFirst()); // null\n // empty.getFirst(); // Would throw NoSuchElementException\n // empty.removeFirst(); // Would throw NoSuchElementException\n }\n}\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### Performance Comparison\n\n| Operation | ArrayList | LinkedList | Winner |\n|-----------|-----------|------------|--------|\n| get(index) | O(1) | O(n) | ArrayList |\n| add(E) at end | O(1)* | O(1) | ArrayList (cache) |\n| add(0, E) at front | O(n) | O(1) | LinkedList |\n| add(index, E) | O(n) | O(n)** | ArrayList |\n| remove(index) | O(n) | O(n)** | ArrayList |\n| remove via iterator | O(n) | O(1) | LinkedList |\n| contains(E) | O(n) | O(n) | ArrayList (cache) |\n| iteration | O(n) | O(n) | ArrayList (cache) |\n| memory per element | ~8 bytes | ~40 bytes | ArrayList |\n\n*Amortized, **Plus O(n) to find position\n\n### When to Use Each\n\n```text\n✅ Use ArrayList (default choice):\n- Random access needed\n- Mostly add/remove at end\n- Memory is a concern\n- Cache locality matters (most cases)\n\n✅ Use LinkedList:\n- Frequent add/remove at front (but consider ArrayDeque)\n- Iterator-based modifications\n- Implementing Queue/Deque (but consider ArrayDeque)\n- Memory for nodes doesn't matter\n\n✅ Use ArrayDeque instead of LinkedList for:\n- Queue operations\n- Stack operations\n- Deque operations\n- (Unless you need null elements or List interface)\n```\n\n### The Truth About LinkedList\n\nLinkedList rarely wins in practice because:\n1. **Cache locality**: Scattered nodes cause cache misses\n2. **Memory overhead**: 5x more memory than ArrayList\n3. **Index access**: Almost always needed at some point\n4. **ArrayDeque**: Better for Queue/Deque operations\n\n---\n\n## 🎤 Senior-Level Interview Questions\n\n### Question #1: When is LinkedList faster than ArrayList?\n\n**What interviewers want to hear**: Nuanced understanding, not blanket statements.\n\n**Strong answer**: LinkedList is faster when: (1) You need frequent insertions/removals at the front - `addFirst()` and `removeFirst()` are O(1) vs ArrayList's O(n). (2) You're modifying during iteration using `ListIterator` - iterator.remove() and iterator.add() are O(1). (3) You need Deque operations without null elements (though ArrayDeque is usually better). However, in practice LinkedList rarely wins due to cache locality issues and the fact that most code eventually needs index-based access.\n\n---\n\n### Question #2: What is the memory overhead of LinkedList?\n\n**What interviewers want to hear**: Understanding of node structure.\n\n**Strong answer**: Each element in LinkedList requires a Node object containing three references (prev, item, next) plus object header. On 64-bit JVM, that's approximately 40 bytes per node: 12 bytes object header + 8 bytes each for three references + 4 bytes padding. Compare to ArrayList which stores just 8-byte references in a contiguous array. For 1000 elements, ArrayList uses ~8KB while LinkedList uses ~40KB - roughly 5x the memory.\n\n---\n\n### Question #3: Why does cache locality affect LinkedList performance?\n\n**What interviewers want to hear**: Understanding of hardware/software interaction.\n\n**Strong answer**: ArrayList stores references in contiguous memory. When the CPU loads one reference, it fetches a cache line (typically 64 bytes) that includes nearby references. Subsequent accesses hit the cache. LinkedList nodes are scattered across the heap - each node access likely requires a trip to main memory, which is ~100x slower than cache access. Even operations that are theoretically O(1) for LinkedList can be slower than O(n) ArrayList operations for small to medium n because of these constant factors.\n\n---\n\n### Question #4: How does LinkedList implement Deque?\n\n**What interviewers want to hear**: Understanding of dual-interface implementation.\n\n**Strong answer**: LinkedList maintains both `first` and `last` pointers, enabling O(1) operations at both ends. For Deque operations: `addFirst()` creates a new node and updates `first`, `addLast()` creates a new node and updates `last`, `removeFirst()` and `removeLast()` simply update the respective pointers. The doubly-linked structure (each node has prev and next) allows traversal in both directions, supporting `descendingIterator()`. LinkedList can serve as both a FIFO queue (offer/poll from opposite ends) and LIFO stack (push/pop from same end).\n\n---\n\n### Question #5: Is LinkedList.get(index) always O(n)?\n\n**What interviewers want to hear**: Knowledge of the optimization.\n\n**Strong answer**: Not quite - there's an optimization. The `node(index)` method checks if the index is in the first or second half of the list. If in the first half, it traverses from `first`. If in the second half, it traverses backwards from `last`. So `get(0)` and `get(size-1)` are effectively O(1), while `get(size/2)` is the worst case at O(n/2). However, this is still O(n) complexity class, and the cache miss on each node hop makes it slower than ArrayList's true O(1) random access even for favorable indices.\n\n---\n\n### Question #6: When would you use LinkedList in production?\n\n**What interviewers want to hear**: Practical wisdom, not theoretical knowledge.\n\n**Strong answer**: Honestly, rarely. For Queue/Deque operations, ArrayDeque is almost always better - same O(1) complexity but better cache locality and less memory. LinkedList's main remaining use case is when you need the `List` interface combined with efficient iterator-based modifications - like a text editor's line buffer where you're constantly inserting and deleting at the cursor position. Even then, I'd benchmark against ArrayList with `removeIf()` which is often surprisingly competitive. The main production uses I've seen are legacy code and specific algorithms that naturally fit linked structures.\n\n---\n\n## 🏁 Conclusion\n\nLinkedList is a lesson in the gap between theoretical complexity and practical performance. On paper, O(1) insertion beats O(n) insertion. In reality, cache locality and memory overhead often flip the result.\n\n**Key takeaways:**\n\n1. **ArrayList is the default** - use it unless you have a specific reason\n2. **LinkedList wins at ends** - addFirst/removeFirst are genuinely O(1)\n3. **Iterator is key** - LinkedList only wins when you already have position\n4. **Cache locality matters** - scattered memory is slow memory\n5. **Consider ArrayDeque** - better than LinkedList for Queue/Deque\n\n**Your next step:** Continue to Part 8 (List Utilities) to master Collections helper methods, or Part 16 (Queue & Deque) for a deeper dive into queue implementations.\n\n---\n\n## 📅 Review Schedule for This Article\n\n| Day | Task | Time |\n|-----|------|------|\n| Day 1 | Review when LinkedList wins vs loses | 5 min |\n| Day 3 | Redo Exercise 2 (Benchmark) | 20 min |\n| Day 7 | Answer interview questions without looking | 10 min |\n| Day 14 | Redo Debug This exercise | 10 min |\n| Day 30 | Review performance comparison table | 5 min |\n\n---\n\n*Next in series: [Part 8: List Utility Methods & Collections Class]*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.911078Z","createdAt","2026-06-10T07:19:25.911920Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",23,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Java","readingTime","seriesId",5,"seriesOrder",7,"author",{"_31":55,"_100":57,"_101":102,"_103":104,"_105":-5,"_106":-5,"_107":-5,"_108":-5,"_109":-5},"category",{"_31":62,"_73":59,"_35":91,"_76":98,"_99":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Java Collections Compendium: From Fundamentals to Production Mastery","java-collections-compendium","description","A comprehensive 30-part series covering everything about Java Collections Framework. From foundational concepts like generics and equals/hashCode contract, through deep dives into ArrayList, LinkedList, HashMap, TreeMap, ConcurrentHashMap, to modern features like immutable collections, Java 21 sequenced collections, streams & collectors, and production patterns with JPA, Jackson & Spring. Includes real production stories, mental models, exercises, and 50+ interview questions.","isActive",{"_31":95,"_73":96,"_35":97},{"_31":92,"_73":93,"_35":94},{"_31":90,"_73":59,"_35":91},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},332,"List","list",254,"Linkedlist","linkedlist",14,"java",334,"Doubly-linked","doubly-linked",268,"Deque","deque","Category for Java","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]