06. Linked Lists

Linked lists solve the one thing arrays can't do efficiently: insert and delete in the middle in O(1). The tradeoff is brutal — you lose O(1) random access, cache friendliness, and simplicity. In practice, Python lists (dynamic arrays) win most of the time. But linked lists appear constantly in interviews because they test pointer manipulation and edge-case thinking.

The Structure

A linked list is a chain of nodes. Each node holds a value and a reference to the next node:

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

# Build: 1 → 2 → 3 → None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

This is the standard LeetCode definition. Every linked list problem uses this class or something nearly identical. None marks the end of the list (like nil in Go).

Python OOP Basics for Interviews

You don't need deep OOP knowledge for linked list problems, but you need to understand:

self — the first parameter of every method, refers to the current instance:

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

Object references — Python variables are references. When you write a = b, both point to the same object. This matters for linked list manipulation:

a = ListNode(1)
b = a          # b and a point to the SAME node
b.val = 99     # a.val is also 99 now

is vs == — use is to check if two variables point to the same node (identity), == to check value equality. For cycle detection, you need is:

if slow is fast:   # same object in memory
    return True

Traversal

To visit every node, walk the chain until you hit None:

def print_list(head: ListNode) -> None:
    curr = head
    while curr:
        print(curr.val, end=" → ")
        curr = curr.next
    print("None")

No random access. To reach element 5, you walk through 0, 1, 2, 3, 4. That's O(n).

Operation Costs

*Amortized with list.append. **If you keep a tail pointer. ***If you already have a reference to the position.

Pattern: Reverse a Linked List

The most fundamental linked list operation. Appears in dozens of problems.

LeetCode 206 - Reverse Linked List

def reverse_list(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        nxt = curr.next    # save next
        curr.next = prev   # reverse pointer
        prev = curr        # advance prev
        curr = nxt         # advance curr
    return prev

Three pointers: prev, curr, nxt. Walk through once, flip each pointer. O(n) time, O(1) space.

Pattern: Fast and Slow Pointers

Two pointers moving at different speeds. Detects cycles and finds midpoints.

def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # slow is at the middle when fast reaches the end

LeetCode 141 - Linked List Cycle

def has_cycle(head: ListNode) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Why it works: if there's a cycle, fast enters it first and laps slow. They must meet. If there's no cycle, fast hits None.

Pattern: Dummy Head

A dummy node before the real head simplifies edge cases (empty list, deleting the head):

LeetCode 21 - Merge Two Sorted Lists

def merge_two_lists(list1: ListNode, list2: ListNode) -> ListNode:
    dummy = ListNode()
    curr = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next
    curr.next = list1 or list2
    return dummy.next

Without the dummy, you'd need special handling for "which node becomes the new head?"

Pattern: Two Pointers with Gap

Move one pointer ahead by n steps, then move both together. When the leader hits the end, the follower is at the target position.

LeetCode 19 - Remove Nth Node From End of List

Use two pointers with an n+1 gap. When fast hits None, slow is one before the target. The dummy node handles the edge case of removing the head (there's no "previous" node without it).

def remove_nth_from_end(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0, head)       # dummy → head, handles removing head itself
    fast = slow = dummy
    for _ in range(n + 1):          # create n+1 gap so slow stops ONE BEFORE target
        fast = fast.next
    while fast:                     # move both until fast hits end
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next      # skip the target node
    return dummy.next               # return new head (might differ if head was removed)

When to Use Linked Lists

• Frequent insertion/deletion at known positions (LRU cache, undo history)
• You need a queue with O(1) dequeue (doubly linked + tail pointer)
• Implementing other structures (hash map chaining, adjacency lists)
• Interview problems testing pointer manipulation

When NOT to Use Linked Lists

• You need random access → use a list
• You're iterating sequentially and rarely inserting → list (cache friendly)
• Memory is tight → linked lists have object overhead per node
• Almost always in Python → lists and deques cover 95% of use cases

The Reality

In modern software, linked lists are rarely the right choice. CPU caches make arrays faster even for operations where linked lists have better theoretical complexity. Python's list with O(n) insert often beats a linked list with O(1) insert because of cache effects and Python's object overhead.

Linked lists matter for:

1. Interview problems (pointer manipulation is a common test)
2. Building other structures (LRU cache = dict + doubly linked list)
3. Understanding how collections.deque and collections.OrderedDict work internally

Practice Problems

Key Takeaways

• Linked lists trade O(1) access for O(1) insertion/deletion at known positions
• The standard ListNode class has val and next — memorize it
• Reverse, fast/slow pointers, and dummy head are the three core patterns
• Fast/slow detects cycles and finds midpoints without knowing the list length
• Use is (not ==) when comparing node identity in Python
• In practice, Python lists and deques beat linked lists — but interviews love them
• LRU cache (dict + doubly linked list) is the most common real-world linked list use case