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, arrays win most of the time. But when you need constant-time insertion at arbitrary positions, or when the data structure must grow without copying, linked lists are the answer.

The Structure

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

type ListNode struct {
    Val  int
    Next *ListNode
}

// Build: 1 → 2 → 3 → nil
head := &ListNode{Val: 1}
head.Next = &ListNode{Val: 2}
head.Next.Next = &ListNode{Val: 3}

No contiguous memory. Each node lives wherever the allocator puts it. To reach element 5, you must walk through elements 0, 1, 2, 3, 4. That's O(n) access.

Singly vs Doubly Linked

Singly linked — each node points to the next. You can only traverse forward. Simpler, less memory.

Doubly linked — each node points to both next and previous. You can traverse both directions. Needed for O(1) deletion when you have a pointer to the node.

type DoublyNode struct {
    Val  int
    Next *DoublyNode
    Prev *DoublyNode
}

Go's container/list is a doubly linked list. In interviews, you usually implement your own singly linked list.

Operation Costs

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

The key insight: linked list insertion is O(1) only if you already know where to insert. Finding that position is O(n). So linked lists shine when you're iterating and modifying simultaneously.

Pattern: Reverse a Linked List

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

LeetCode 206 - Reverse Linked List

Given the head of a singly linked list, reverse the list and return the reversed list.

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next  // save next
        curr.Next = prev   // reverse pointer
        prev = curr        // advance prev
        curr = next        // advance curr
    }
    return prev
}

Three pointers: prev, curr, next. 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.

// Find middle of linked list — O(n)
func findMiddle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow // slow is at the middle when fast reaches the end
}

// Detect cycle — O(n)
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == 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 nil.

Pattern: Dummy Head

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

// Remove all nodes with a given value
func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    curr := dummy
    for curr.Next != nil {
        if curr.Next.Val == val {
            curr.Next = curr.Next.Next // skip the node
        } else {
            curr = curr.Next
        }
    }
    return dummy.Next
}

Without the dummy, you'd need special handling for "what if head itself should be 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)
• The data structure must never reallocate (real-time systems)
• Implementing other structures (hash map chaining, adjacency lists)

When NOT to Use Linked Lists

• You need random access → array
• You're iterating sequentially and rarely inserting → array (cache friendly)
• Memory is tight → linked lists have pointer overhead per node
• Almost always in Go → slices are better for 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. A slice with O(n) insert often beats a linked list with O(1) insert because of cache effects.

Linked lists matter for:

1. Interview problems (pointer manipulation is a common test)
2. Building other structures (LRU cache = hash map + doubly linked list)
3. Lock-free concurrent data structures

Practice Problems

Key Takeaways

• Linked lists trade O(1) access for O(1) insertion/deletion at known positions
• Singly linked: forward only, less memory. Doubly linked: both directions, O(1) delete with pointer
• Reverse, fast/slow pointers, and dummy head are the three core patterns
• Fast/slow detects cycles and finds midpoints without knowing the list length
• In practice, arrays/slices beat linked lists for most use cases due to cache effects
• Linked lists still matter for interviews and as building blocks for other structures (LRU cache)