The Discipline of Pointers

The trade linked lists make

Arrays guarantee O(1) random access at the cost of O(n) mid-sequence insertion. Linked lists invert that bargain: O(1) insertion and deletion anywhere you already have a pointer, at the cost of O(n) indexed access. Everything else about linked lists follows from that single trade. You cannot ask "what is the 17th element?" without walking past the first 16. But you can splice a new element into the middle of a million-node list in constant time, as long as you know where to cut.

This is why linked lists appear inside other structures rather than on their own. LRU caches use doubly-linked lists so that moving a recently-used node to the front is O(1). Open-addressing-free hash tables chain collisions in linked lists. Modern operating systems thread processes, timers, and free-memory blocks on linked lists because the cost of maintaining them is bounded by what you touch, never by the size of the system.

The node type, and why it matters

In most languages, a linked-list node is a three-line declaration:

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next  = nxt

Two things are worth noticing. First, next is a reference, not a container: assigning a.next = b does not copy b; it records where b lives. Second, a list has no "list object" in the basic form; the whole structure is identified by a pointer to its first node. An empty list is a null pointer. That stark framing makes the algorithms easier, because the invariants are all stated in terms of node references, not a surrounding collection.

In-place reversal: the foundational drill

If you can write this loop without looking it up, you can write most linked-list code. The trick is that reassigning curr.next destroys the only reference to the original successor, so you must save it first:

def reverse(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next   # save, because we're about to overwrite
        curr.next = prev  # flip the arrow backwards
        prev = curr       # advance prev
        curr = nxt        # advance curr
    return prev           # new head

Trace it on a three-node list and the mechanics become permanent. After one iteration, the first arrow points backward to None. After two, the second points at the first. After three, the third points at the second, and curr falls off the end. prev is now the old tail, the new head. The loop runs n times, reassigns three local variables per iteration, and allocates nothing. O(n) time, O(1) memory. Any interview answer longer than those four lines is overcomplicating.

Floyd's cycle detection

Given a list that may contain a cycle, decide whether it does using only O(1) extra memory. The naive O(n) answer uses a hash set of visited nodes, but that fails the space constraint. Floyd's algorithm uses two pointers that advance at different speeds:

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Why it works: if there is a cycle, both pointers eventually enter it. From that moment, the fast pointer gains one step on the slow pointer per iteration. After at most L iterations (where L is the cycle length), they coincide. If there is no cycle, the fast pointer reaches the end in n/2 steps and the loop terminates. The proof is short; the mechanics are gorgeous. A modest extension (restart one pointer at the head, then advance both one step at a time) gives you the node at which the cycle begins. The derivation is a satisfying exercise in modular arithmetic.

Merging two sorted lists

Used as a building block in merge-sort on lists, and as an interview problem in its own right. Given two sorted heads, produce a third sorted list without allocating a new node. The technique is to maintain a dummy head, a node whose only purpose is to simplify the first step, and a tail pointer that always points at the last appended node:

def merge(a, b):
    dummy = Node(0)
    tail  = dummy
    while a and b:
        if a.value <= b.value:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

The dummy head earns its keep in the first iteration, where without it you'd need a conditional to decide whether to set the result head or to extend it. That conditional repeated in enough real code to justify naming the pattern.

Complexity, stated precisely

Random access a[i]: O(n). Insertion or deletion given a node reference: O(1). Insertion or deletion at position i: O(n), because you must first walk to the position. Finding an element by value: O(n). Reversal, cycle detection, merge-two: O(n), O(1) space. Merge-sort on a linked list: O(n log n) time, O(log n) stack space, and, uniquely, zero auxiliary array allocation, which is why it was the sort of choice on memory-constrained systems for decades.

When to use a linked list

Reach for a linked list when (a) you will insert and delete from the middle of the sequence frequently and already have references to the affected nodes, (b) the sequence length is unbounded and you want to avoid the occasional large copy of a resizing array, or (c) you are building a structure that composes linked lists internally: an LRU cache, a free list, a priority queue backed by a skew heap. Avoid linked lists when you need index access or when cache locality matters: a linked list with million-node traversals will thrash a CPU cache that an array would have loved.

Where beginners go wrong

• Losing the successor during reversal. Assigning curr.next = prev before saving curr.next into a temporary variable leaves you with no way to advance. The nxt = curr.next line is not a style preference.
• Forgetting the dummy head. Every insertion-at-head operation becomes a conditional if you don't maintain one. It's worth its weight.
• Assuming doubly-linked means "twice as expensive". It means O(1) deletion given a node reference, which is exactly the use case that makes linked lists worth it. The extra pointer is almost always a good trade.
• Confusing cycle detection with cycle removal. Floyd's algorithm tells you whether a cycle exists and where it starts. Setting node.next = None to remove it is a separate step, and the choice of which next pointer to null matters.

What to read next

Continue with Module 03 · Advanced String Manipulation, where the two-pointer patterns from Module 01 return in the guise of prefix hashing and KMP. The concept page on Sliding Window in Depth is a natural companion as well.