4.1 Linked Lists & LRU Cache

1. What Is a Linked List?

An Array stores all of its items side-by-side in one single block of memory. A Linked List does the exact opposite: its items can live anywhere in memory, connected like a treasure hunt where each box (called a Node) holds two things:

1. val: The value stored inside this node (e.g., 10).
2. next: A pointer (memory address arrow) pointing to the next node in the chain, or null (None) at the end.

In a Doubly Linked List, each node also holds a prev arrow pointing backward to the previous node.

2. Why Do We Need Linked Lists & How Do They Work?

The Pain With Arrays (O(N) Middle Insert/Delete)

In an Array, inserting or deleting an item at the front or middle forces every subsequent item to shift over in memory (O(N)).

Why Linked Lists Win at Splicing (O(1))

If you already have a pointer to a node curr in a Linked List:

• Inserting a new node right after curr takes O(1) time: Just point new_node.next = curr.next, and then curr.next = new_node. Zero items shift in memory!
• Deleting the node after curr takes O(1) time: Just bypass it with curr.next = curr.next.next.
• The Trade-Off: You lose O(1) index lookup (arr[5]). To reach the 5th node in a Linked List, you must start at head and follow .next 5 times (O(N)).

3. Basic Operations & Walkthroughs (All 4 Languages)

class ListNode:
  def __init__(self, val=0, next=None):
      self.val = val
      self.next = next

# 1. Build 10 -> 20 -> 30
head = ListNode(10, ListNode(20, ListNode(30)))

# 2. Traverse from head to null -> O(N)
curr = head
while curr:
  # read curr.val
  curr = curr.next

# 3. Insert 15 right after head (10) -> O(1)
new_node = ListNode(15)
new_node.next = head.next
head.next = new_node      # 10 -> 15 -> 20 -> 30

# 4. Delete the node after head (removes 15) -> O(1)
head.next = head.next.next  # back to 10 -> 20 -> 30

4. The 4 Essential Interview Patterns

Pattern 1: In-Place Pointer Reversal (prev, curr, nxt)

To reverse a linked list in O(1) memory, walk curr forward while flipping each .next arrow backward toward prev. Golden Rule: Always save nxt = curr.next before you overwrite curr.next = prev, or you lose the rest of the list!

Pattern 2: Dummy Sentinel Node (dummy = ListNode(0, head))

Whenever the head of the list might change (merging lists, deleting the 1st node), create a dummy node before head. Attach everything to dummy, and return dummy.next!

Pattern 3: Fast & Slow Pointers (Floyd's Cycle & Middle Detection)

Move slow by 1 step and fast by 2 steps:

• When fast reaches null, slow is at the exact middle of the list.
• If there is a cycle, fast laps slow and they collide (slow == fast) in O(N) time and O(1) memory.

Pattern 4: LRU Cache (Hash Map + Doubly Linked List)

To get O(1) lookup AND O(1) recency updates:

• Store key -> Node in a Hash Map for instant O(1) lookup.
• Connect all nodes in a Doubly Linked List between dummy HEAD (LRU) and TAIL (MRU) so any accessed node can be unlinked from the middle and moved to TAIL in O(1) time!

# 1. Find Middle (slow stops at middle):
slow = fast = head
while fast and fast.next:
  slow = slow.next
  fast = fast.next.next

# 2. Reverse from slow onward:
prev, curr = None, slow
while curr:
  nxt = curr.next
  curr.next = prev
  prev = curr
  curr = nxt

5. Practice On Your Own (Curated Submodule Problems)