Linked Structures, Stacks, Queues, and Deques

What is allowed to leave next?

Reverse the chain A -> B -> C. If you begin by setting A.next = null, where is B?

Unless another reference already points to it, the rest of the chain has disappeared from the algorithm. The assignment is locally plausible and the list rooted at A even looks valid. The missing suffix reveals the real problem: linked algorithms are governed by reachability, not by the value in the current node.

Stacks, queues, and deques impose comparable rules on their own state. A stack allows the newest unresolved item to leave first. A queue allows the earliest scheduled item to leave first. A deque may remove old candidates from one end and dominated candidates from the other. In each case, the container is less important than the promise it makes about departure.

That gives these structures one useful question:

What does an entry mean while it is here, and what event permits it to leave?

Answer it before choosing an API. It produces the invariant that explains the code, exposes most boundary bugs, and often supplies the correctness proof.

A linked list is a chain of ownership

An array keeps elements reachable through indexes. A linked list keeps the next element reachable only through a reference in the current node. Random access requires a walk, and finding a predecessor also requires a walk unless the structure or caller already supplies it. The familiar claim that linked insertion and deletion are O(1) is therefore conditional: the position must already be known.

Reversal makes the ownership problem visible:

def reverse_list(head):
    previous = None
    current = head

    while current is not None:
        following = current.next
        current.next = previous
        previous = current
        current = following

    return previous

At the start of every iteration, previous owns the reversed prefix and current owns the unread suffix. Saving following preserves the suffix while current.next changes direction. After the reassignment, advancing both references restores the same division one node farther along.

This is a better explanation than “use three pointers.” The names are incidental; the two regions and the transfer of one node between them are the algorithm. It also tells you what to test. An empty chain never enters the loop. A one-node chain transfers once. A two-node chain exposes an update-order mistake immediately. A longer chain reveals whether the new tail was closed or accidentally left pointing into a cycle.

Dummy nodes remove a false special case

Suppose every node equal to target must be removed. The head might survive, or it might need to be replaced several times. A dummy predecessor lets the same operation handle both:

def remove_value(head, target, node_type):
    dummy = node_type(0)
    dummy.next = head
    previous = dummy
    current = head

    while current is not None:
        if current.value == target:
            previous.next = current.next
        else:
            previous = current
        current = current.next

    return dummy.next

previous advances only when current survives. When a node is removed, previous.next already points at the next candidate, so consecutive matches need no special branch. The dummy is not a linked-list trick to memorize. It is a stable owner for a boundary that might otherwise move.

Bounded rewrites require two more anchors: the node before the segment and the node after it. For reversing groups of k, first prove that a complete group exists, save group_next, and reverse only until that reference. Initializing the local previous to group_next makes the new tail connect to the untouched suffix as part of the reversal rather than as a later repair. If fewer than k nodes remain, the contract says to leave them alone; discovering that fact after rewiring has begun is too late.

Relative motion can replace stored length

Fast and slow pointers work when a fixed difference in speed or position reveals structure that a single walk would otherwise have to remember.

For cycle detection, move slow one edge and fast two. In an acyclic list, fast reaches a null boundary. Inside a cycle, fast gains one position per iteration relative to slow, so their node identities eventually coincide. Values are irrelevant: two distinct nodes may contain the same value.

def has_cycle(head):
    slow = head
    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

Finding the cycle entry adds a second phase. After a meeting, put one pointer at the head and move both one edge at a time; their next meeting is the entry. The proof comes from distances modulo the cycle length, not from the pointers somehow “knowing” the entrance. State that argument if the interviewer asks for more than detection.

The same family finds a midpoint or maintains an offset between two references, but the boundary convention must be explicit. Which middle should an even-length list return? Does “nth from the end” accept n = 0? If a lead pointer starts at a dummy node, how many advances put the follower immediately before the node to remove? Mixing two correct variants without carrying their starting positions is how the off-by-one error appears.

Linked-list work is complete only after deciding whether mutation is visible to the caller. A palindrome check that reverses the second half may need to restore it. A merge that reuses nodes changes the input chains. Node identity, aliasing, and ownership are part of the contract even when a small interview example makes them easy to overlook.

A stack holds unresolved obligations

The best stack entries describe unfinished work. In a delimiter parser, an opening bracket creates an obligation for a particular closer:

def delimiters_are_balanced(text):
    expected_for = {"(": ")", "[": "]", "{": "}"}
    expected = []

    for character in text:
        if character in expected_for:
            expected.append(expected_for[character])
        elif character in ")]}":
            if not expected or expected.pop() != character:
                return False

    return not expected

Storing the expected closer makes the entry’s meaning executable. The newest opening must close first because it is the innermost unfinished region. A premature closer fails on an empty or mismatched stack; leftover entries fail at the end.

The raw value is often not enough. An error-reporting parser also needs the opening position. An iterative depth-first traversal may need a node plus a phase so that pre-visit and post-visit actions remain distinct. A histogram algorithm needs an index because the answer depends on width. Before pushing, ask what later resolution will need; before popping, name the evidence that the obligation is finished.

Monotonic stacks wait for the first decisive value

Consider daily temperatures: for each day, return the number of days until a warmer temperature, or zero if none arrives. Scanning ahead separately from every day repeats work. Instead, keep the indexes of days that have not yet seen a warmer future day:

def daily_temperatures(temperatures):
    waits = [0] * len(temperatures)
    unresolved = []

    for index, temperature in enumerate(temperatures):
        while (
            unresolved
            and temperature > temperatures[unresolved[-1]]
        ):
            earlier = unresolved.pop()
            waits[earlier] = index - earlier
        unresolved.append(index)

    return waits

For [73, 74, 75, 71, 69, 72, 76, 73], the stack after reading 69 contains indexes for [75, 71, 69]. They remain unresolved and their temperatures decrease toward the top. When 72 arrives, it resolves 69 and 71, but it cannot resolve 75. Then 76 resolves both 72 and 75.

The strict comparison is part of the prompt: an equal temperature is not warmer. The entries are indexes because distance and answer position matter. For a different problem, equal values might be safely coalesced or one might dominate another; derive the comparison instead of importing it.

The nested loop is still O(n). Each index is pushed once and popped at most once, so all executions of the inner loop together perform at most n pops. “Push once, pop once” is not a slogan pasted onto every stack algorithm; it is the progress argument for this one.

Largest-rectangle and span problems add boundary information, but the same questions apply. What remains unresolved? In what monotonic order? Does the current item answer a popped entry or merely prove its right boundary? Which index establishes the left boundary after popping? Those decisions are the algorithm.

An expression stack depends on a grammar

“Evaluate a string” is not yet a problem statement. Before choosing one or two stacks, settle the language:

• Which numeric forms are valid?
• Are unary + and - operators allowed?
• Are parentheses allowed?
• What precedence and associativity does each operator have?
• How does integer division round?
• What happens on malformed input or division by zero?

For nonnegative integers with +, -, *, and / but no parentheses or unary operators, one stack of signed terms is sufficient. Multiplication and division can consume the most recent term immediately; addition and subtraction can leave signed terms to be summed at the end. Add parentheses and the grammar needs nested parser state. Add unary minus and a minus sign can no longer be classified without context.

Splitting on operator characters hides these distinctions and usually fails as soon as the language becomes honest. Two operator/value stacks or a small recursive-descent parser can both be correct. The durable choice is to make pending operators, values, and nesting explicit.

A queue makes the frontier a first-in, first-out promise

In an unweighted graph, breadth-first search discovers states in nondecreasing distance from the start. FIFO order is what makes that true: states one edge away are scheduled before states two edges away.

from collections import deque


def shortest_unweighted_distance(start, target, neighbors):
    frontier = deque([(start, 0)])
    visited = {start}

    while frontier:
        state, distance = frontier.popleft()
        if state == target:
            return distance

        for neighbor in neighbors(state):
            if neighbor not in visited:
                visited.add(neighbor)
                frontier.append((neighbor, distance + 1))

    return None

Mark a state visited when it is enqueued. Marking it only when dequeued lets several incoming edges schedule the same state before any copy reaches the front. The result may remain correct, but the frontier can grow dramatically and any “one entry per state” proof is false.

The visited key must describe the whole state. A grid position may be enough when legal moves depend only on location. If the traveler can collect keys, spend a limited resource, or change a switch, (row, column) merges states whose futures differ. The queue order can be perfect while the state model is wrong.

Store a parent only when the path itself is required. Store distance with each entry when that makes the invariant clearer; otherwise process a fixed number of entries per level. Either representation works if the explanation and code agree about when distance increases.

FIFO stops being sufficient when edges have different costs. The first arrival is no longer necessarily cheapest. Edge weights of only zero and one admit a deque-based 0-1 BFS; arbitrary nonnegative weights call for a priority frontier, which is the subject of the next chapter.

A deque keeps only candidates that can still win

A sliding-window maximum needs two forms of removal. An index expires when it falls left of the window, while a new value can permanently dominate older, smaller candidates. A deque gives those events separate ends:

from collections import deque


def sliding_window_maximum(values, width):
    if width <= 0 or width > len(values):
        raise ValueError("width must describe a nonempty window")

    candidates = deque()
    maxima = []

    for index, value in enumerate(values):
        while candidates and candidates[0] <= index - width:
            candidates.popleft()

        while candidates and values[candidates[-1]] <= value:
            candidates.pop()

        candidates.append(index)

        if index >= width - 1:
            maxima.append(values[candidates[0]])

    return maxima

The front is the maximum valid candidate. Indexes increase from front to back; their values decrease. Expired indexes leave from the front. If a new value is at least as large as a value at the back, the older one can never win again: it is no larger and will expire sooner, so it leaves from the back.

For values = [1, 3, -1, -3, 5, 3, 6, 7] and width = 3, the first complete window leaves candidates [3, -1], so the answer is 3. After -3, the same front remains valid. When 5 arrives, the old 3 has expired and 5 dominates both negative candidates, leaving only the index of 5. The deque is not the window; it is a compressed set of values that might still become its maximum.

Changing <= to < when removing from the back keeps older equal values. That can also be correct, but it changes how duplicates survive and may affect which index represents the maximum. The expiry rule then has to carry the extra entries correctly. Explain the policy you implement.

The same push-once, remove-once argument gives O(n) time. Each index enters the deque once and leaves from one end at most once. Reverse the comparison for a minimum. Do not generalize the structure to arbitrary ranking: a heap or ordered structure is a better match when the best candidate is not maintained by this particular domination rule.

Derive the structure from the contract

When a prompt resembles several familiar patterns, postpone the container name and finish these sentences:

• A linked reference is safe to rewrite after ___ remains reachable through ___.
• A stack entry represents ___ and may pop when ___.
• A queue entry represents ___ and must be marked scheduled when ___.
• A deque index remains useful while it is neither ___ nor ___.

The blanks expose the choice. Linked pointers fit when identity, adjacency, or rewiring is central and the cost of locating a node is accounted for. A stack fits nested or last-unresolved work. A queue fits arrival order or equal-cost frontiers. A deque fits a boundary where expiration and domination operate at opposite ends.

Then test the claimed invariant at its boundary. Remove the head and two consecutive nodes. Give a cycle detector repeated values. Feed a delimiter parser a premature closer and an unfinished opener. Give a monotonic stack duplicates. Let two BFS paths converge on one state. Let the window maximum expire exactly as a larger value arrives. These are not a generic edge-case checklist; each test attacks the rule that permits an item to leave.

Practice by changing one rule

Start with the linked reversal and reverse only a closed segment. Then reverse groups of k, leaving a short final group untouched. The update loop changes less than the boundary proof: you now need references on both sides and must prove the group exists before mutation.

Start with balanced delimiters and add error positions, then quoted strings in which brackets are ordinary characters. Next, evaluate arithmetic under an explicit grammar. Each extension changes what a stack entry must remember; copying the original character stack cannot solve all three.

Start with daily temperatures and return the next warmer temperature rather than its distance. Then ask for the previous greater value, the largest histogram rectangle, or online stock span. For each variation, write the meaning and order of the unresolved stack before writing its comparison.

Start with shortest moves in a blocked grid. Add a key that opens doors, then give different terrain different costs. The first change expands the visited state; the second invalidates FIFO and changes the frontier itself.

Finally, implement the window maximum and change maximum to minimum. Decide how equal values behave. Then attempt a sliding-window median and notice what the deque cannot provide: domination no longer leaves only a useful prefix. That boundary motivates heaps and ordered multisets more honestly than a list of data-structure names.

These structures are small machines for preserving order. Reliable solutions say what remains reachable, unresolved, scheduled, unexpired, or undominated after every operation. Once that sentence is precise, the API calls are often the least interesting part of the work.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 33: Correctness Before Cleverness
• Chapter 40: Hash Maps and Sets
• Chapter 42: Heaps and Ordered Structures