4. Linked Lists

What Is a Linked List?

A linked list is a sequence of nodes, each storing a value and a pointer to the next node. Unlike an array, nodes can be scattered anywhere in memory — they're connected only by pointers.

Analogy: A scavenger hunt where each clue tells you where the next clue is. You can't jump to clue 5 directly — you must follow the chain from clue 1.

Operation	Array (list)	Linked List
Access by index	$O(1)$ ✓	$O(n)$ ✗
Insert/delete at start	$O(n)$ ✗	$O(1)$ ✓
Insert/delete at end	$O(1)$ ✓	$O(1)$ ✓ (with tail pointer)
Memory	Contiguous	Scattered (higher overhead)

In Python: You'll rarely build a linked list from scratch in production. Python's collections.deque is a doubly-linked list under the hood. But understanding linked lists trains your pointer reasoning, which applies to trees, graphs, and more.

---

4.1 Singly Linked List

class Node:
    def __init__(self, val: int):
        self.val  = val
        self.next: "Node | None" = None

class LinkedList:
    def __init__(self):
        self.head: Node | None = None

    def append(self, val: int) -> None:
        """Add to end — O(n) without tail pointer."""
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

    def prepend(self, val: int) -> None:
        """Add to front — O(1)."""
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node

    def delete(self, val: int) -> None:
        """Remove first node with given value — O(n)."""
        if not self.head:
            return
        if self.head.val == val:
            self.head = self.head.next
            return
        cur = self.head
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next   # skip the node to delete
                return
            cur = cur.next

    def to_list(self) -> list[int]:
        """Convert to Python list for easy inspection."""
        result = []
        cur = self.head
        while cur:
            result.append(cur.val)
            cur = cur.next
        return result

    def __repr__(self) -> str:
        return " → ".join(map(str, self.to_list())) + " → None"


# Usage
ll = LinkedList()
ll.append(1); ll.append(2); ll.append(3)
ll.prepend(0)
print(ll)         # 0 → 1 → 2 → 3 → None
ll.delete(2)
print(ll)         # 0 → 1 → 3 → None

---

4.2 Common Linked List Algorithms

# Standalone node class used throughout
class ListNode:
    def __init__(self, val=0, next=None):
        self.val  = val
        self.next = next

# --- Reverse a linked list ---
# Before: 1 → 2 → 3 → 4 → None
# After:  4 → 3 → 2 → 1 → None
def reverse(head: ListNode | None) -> ListNode | None:
    prev = None
    cur  = head
    while cur:
        next_node = cur.next   # save next before overwriting
        cur.next  = prev       # point backward
        prev      = cur        # advance prev
        cur       = next_node  # advance cur
    return prev   # prev is now the new head

# --- Find the middle node (slow/fast pointer) ---
# Slow moves 1 step, fast moves 2 steps.
# When fast reaches end, slow is at the middle.
def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# --- Detect a cycle (Floyd's cycle detection) ---
# If the list has a cycle, fast and slow pointers will eventually meet.
def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# --- Merge two sorted linked lists ---
def merge_sorted(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    dummy = ListNode(0)   # sentinel node — avoids edge cases for empty lists
    cur = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 if l1 else l2   # attach remaining nodes
    return dummy.next

---

When to Use a Linked List in the Real World

• Undo/redo history where insertions and deletions at arbitrary positions are frequent
• LRU Cache implementation (doubly linked list + hash map)
• Music playlist with next/previous navigation
• Python's collections.deque is a doubly-linked list — use it for fast O(1) front/back access

---