Lesson 7 of 10 · 8 min

Linked lists, stacks and queues

Pointer manipulation without off-by-one bugs, and the two structures that model order.

Linked lists: why they exist and why they lose

A linked list gives O(1) insertion and deletion once you hold a reference to the node. That is its entire advantage.

It loses on everything else: no random access, poor cache locality because nodes are scattered in memory, and a pointer of overhead per element. In practice arrays win almost always — which is why linked lists appear in interviews far more than in production code.

Two techniques that solve most list problems

# 1. Dummy head — removes the 'what if it's the first node' branch
def remove_value(head, target):
    dummy = ListNode(0, head)
    prev, cur = dummy, head
    while cur:
        if cur.val == target:
            prev.next = cur.next     # works even for the original head
        else:
            prev = cur
        cur = cur.next
    return dummy.next

# 2. Fast and slow — cycle detection and midpoint, in O(1) space
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

Stacks and queues

A stack is last-in-first-out and models nesting: matching brackets, undo history, the call stack itself, and depth-first traversal. A Python list with append and pop is a perfectly good stack.

A queue is first-in-first-out and models fairness and level order: breadth-first search, task scheduling. Use collections.deque, never a list with pop(0).

The monotonic stack

This is the pattern worth internalising. Keep a stack whose values are always increasing (or always decreasing). When a new element arrives, pop everything it invalidates — and each pop resolves an answer.

It solves 'next greater element', 'previous smaller element', daily temperatures, largest rectangle in a histogram, and stock spans. Every index is pushed once and popped at most once, so it is O(n) despite looking quadratic.

Next greater element

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                       # indices, values DECREASING
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            result[stack.pop()] = value    # value resolves this index
        stack.append(i)
    return result

Note: Store indices, not values — you need the position to write the answer back.

Worth remembering

A dummy head removes every special case at the front of a list.
Fast and slow pointers find cycles and midpoints in O(1) space.
A monotonic stack answers 'next greater element' in linear time.

Test it now

Linked list surgery and monotonic stacks are core medium topics.

Medium DSA quiz →All levels