Linked Lists

What you'll learn

• Node Structure

  Every linked list is built from nodes. A node is the fundamental building block: - data: The value stored in the node (integer, string, object, etc.) - next: A pointer/reference to the next node in the list In code, a node looks like: Th…

• Memory Allocation

  Linked lists use non-contiguous, heap-allocated memory: Each node is independently allocated on the heap. This means: - Nodes can be anywhere in memory - No need to declare size upfront - No wasted pre-allocated space - But no cache-line…

• Singly Linked List

  The most basic form. Each node points to the next node, and the last node points to null.

• Visual Representation

• Operations with Diagrams

• Doubly Linked List

  Each node has pointers to both the next AND previous nodes, enabling bidirectional traversal.

• Node Structure

• Visual Representation

• Insert in Doubly Linked List

• Delete in Doubly Linked List

  Complexity: O(1) time with a direct node reference, O(1) space. When you have a pointer to the node, both neighbors are instantly accessible via prev and next. In a singly linked list, you would need O(n) traversal to find the previous n…

• When to Prefer Doubly Over Singly

  - When you need backward traversal (e.g., browser history back/forward) - When deletion is frequent and you have direct node references (e.g., LRU cache) - When implementing deques (double-ended queues) - When you need to traverse a wind…

• Space Overhead

  - Singly linked list: 1 extra pointer per node - Doubly linked list: 2 extra pointers per node For a node storing a 4-byte integer on a 64-bit system: - Array: 4 bytes per element - Singly: 4 + 8 = 12 bytes per element (50% overhead) - D…

• Circular Linked List

  The last node points back to the first node, forming a cycle.

• Singly Circular

• Doubly Circular

• Use Cases

  1. Round-robin scheduling: Process scheduler cycles through tasks endlessly 2. Circular buffers: Audio streaming, network packet buffers 3. Multiplayer games: Turn rotation among players 4. Carousel/slideshow: Cycling through items with…

• Complete Time Complexity Table

  | Operation | Singly | Doubly | Why | |-----------|--------|--------|-----| | Access by index | O(n) | O(n) | No random access; must traverse from head | | Search | O(n) | O(n) | Must check nodes sequentially | | Insert at head | O(1) |…

• Space Complexity

  - Overall: O(n) for n elements - Per node overhead: - Singly: +1 pointer (8 bytes on 64-bit) - Doubly: +2 pointers (16 bytes on 64-bit)

• Common Patterns and Algorithms

• 1. Runner Technique (Fast/Slow Pointers)

  Use two pointers moving at different speeds to solve cycle detection, find midpoints, and more. Find middle of list: Sample Input / Output Input: head = 1 → 2 → 3 → 4 → 5 Output: 3 (middle node) Input: head = 1 → 2 → 3 → 4 Output: 3 (mid…

• 2. Linked List Reversal

  Reverse the direction of all pointers. Sample Input / Output Input: head = 1 → 2 → 3 → 4 → 5 Output: 5 → 4 → 3 → 2 → 1 Input: head = 1 → 2 Output: 2 → 1 Input: head = null Output: null (empty list — edge case) Complexity: O(n) time, O(1)…

• 3. Merge Two Sorted Lists

  Combine two sorted linked lists into one sorted list. Sample Input / Output Input: l1 = 1 → 3 → 5, l2 = 2 → 4 → 6 Output: 1 → 2 → 3 → 4 → 5 → 6 Input: l1 = null, l2 = 1 → 2 → 3 Output: 1 → 2 → 3 (one list empty — edge case) Input: l1 = 1…

• 4. Detect and Find Cycle Start

  Sample Input / Output Input: 1 → 2 → 3 → 4 → 5 → (back to 3) (node 5's next points to node 3) Output: node with value 3 — the start of the cycle. Input: 1 → 2 → 3 → null Output: null — no cycle. Input: 1 → (back to 1) (single node pointi…

• 5. Remove N-th Node From End

  Sample Input / Output Input: list 1 → 2 → 3 → 4 → 5, n = 2 Output: 1 → 2 → 3 → 5 (removed node 4, the 2nd from the end). Input: list 1, n = 1 Output: null (removed the only node — the dummy makes this a normal case). Input: list 1 → 2, n…

• When to Use Linked Lists

• Use linked lists when:

  1. Frequent insertions/deletions at arbitrary positions -- O(1) with node reference vs. O(n) shifting in arrays 2. Size is unknown or highly variable -- no need to resize or pre-allocate 3. Implementing stacks -- push/pop at head is O(1)…

• Do NOT use linked lists when:

  1. You need random access -- accessing element at index i is O(n), not O(1) 2. Cache performance matters -- non-contiguous memory causes cache misses 3. Memory overhead is a concern -- extra 8-16 bytes per element for pointers 4. You nee…

• Comparison: Linked List vs Array

  | Criteria | Array | Linked List | |----------|-------|-------------| | Access by index | O(1) | O(n) | | Insert at beginning | O(n) | O(1) | | Insert at end | O(1) amortized | O(1) with tail | | Insert at middle | O(n) | O(1) if positio…

• Competitive Programming Patterns

• Pattern 1: Sentinel/Dummy Nodes

  Sample Input / Output Input: merge sorted lists 1 → 3 → 5 and 2 → 4 → 6 Output: 1 → 2 → 3 → 4 → 5 → 6 Input: delete target 3 from 1 → 3 → 5 → 7 Output: 1 → 5 → 7 Input: delete target 1 from 1 → 2 → 3 Output: 2 → 3 (head deletion without…

• Pattern 2: In-place Reversal (Sublist)

  Sample Input / Output Input: list 1 → 2 → 3 → 4 → 5, left = 2, right = 4 Output: 1 → 4 → 3 → 2 → 5 — nodes at positions 2..4 reversed, endpoints untouched. Input: list 1 → 2 → 3 → 4 → 5, left = 1, right = 5 Output: 5 → 4 → 3 → 2 → 1 (ent…

• Pattern 3: Partition Around a Value

  Sample Input / Output Input: list 1 → 4 → 3 → 2 → 5 → 2, x = 3 Output: 1 → 2 → 2 → 4 → 3 → 5 — all = 3 (also preserving order). Input: list 3 → 5 → 8, x = 2 Output: 3 → 5 → 8 (all nodes >= x — edge case) Input: list 1 → 2, x = 5 Output:…

• Pattern 4: Recursive Approach

  Sample Input / Output (recursive reverse) Input: 1 → 2 → 3 → 4 → 5 Output: 5 → 4 → 3 → 2 → 1 Input: 1 → 2 Output: 2 → 1 Input: 1 Output: 1 (single node base case — edge case) Many linked list problems have elegant recursive solutions. Co…

• Pattern 5: Fast/Slow + Reverse Half (Composite Pattern)

  Sample Input / Output Palindrome check: - Input: 1 → 2 → 3 → 2 → 1 → Output: true - Input: 1 → 2 → 3 → 4 → Output: false Reorder list (L0→Ln→L1→Ln-1→…): - Input: 1 → 2 → 3 → 4 → 5 → Output: 1 → 5 → 2 → 4 → 3 Several problems combine find…

• 6. Clone a Linked List with Random Pointers

  Sample Input / Output Input (each node is (value, randomtargetindex) where randomtargetindex = -1 means null): The next chain is 7 → 13 → 11 → 10 → 1; random pointers: 7→null, 13→7, 11→1, 10→11, 1→7. Output: an independent deep copy with…

• Related Topics

  - Fast-slow pointer algorithms in the Algorithms path cover cycle detection and meeting-point proofs in depth - Merge patterns in the Algorithms path extend the merge-two-sorted-lists idea to k-way merge using heaps - Stack and Queue imp…

• Summary of Key Insights

  1. Linked lists trade random access for efficient insertion/deletion 2. The pointer overhead is the cost of flexibility 3. Doubly linked lists trade more memory for O(1) deletion with node reference 4. Fast/slow pointer technique is the…