Linked Lists, Stacks & Queues

01Linked lists — what you buy by giving up contiguity

An array's superpower (O(1) indexing) comes from contiguous memory. Its weakness (O(n) insert/delete) comes from the same place. A linked list makes the opposite trade: scatter the nodes anywhere in memory, and have each node carry a pointer to the next.

Array:        [A][B][C][D]           one block; insert at front shifts everything

Linked list:  head ─► [A|•]─► [B|•]─► [C|•]─► [D|None]
                 each node = (value, pointer); nodes live anywhere in memory

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

Insert after a node you already hold — the linked list's party trick. Two pointer writes, O(1), nothing else moves:

before:  ... ─► [B|•] ───────► [C|...]
insert X:       [B|•]─► [X|•]─► [C|...]     X.next = B.next; B.next = X

So why do linked lists exist? Because sometimes you are already holding the node:

• LRU cache — the canonical justification. Redis's LRU-ish eviction, or any LRU you build: a hashmap gives O(1) access to the node; a doubly linked list gives O(1) "move to front" and "evict from back." Neither structure alone can do it; together they're O(1) everything.
• Queues/deques (each end is a held node), free lists in memory allocators, chaining in hashmaps.

Doubly linked lists

Add a prev pointer: now you can delete a node given only that node (rewire node.prev.next and node.next.prev), and walk both directions. Costs one extra pointer per node. collections.deque and every LRU cache use this.

None ◄─[A]◄──►[B]◄──►[C]─► None
         each node: (prev, val, next)

The dummy (sentinel) node — the #1 bug preventer

dummy = ListNode(0, head)
prev, cur = dummy, head
# ... surgery that might remove/replace the real head works uniformly ...
return dummy.next            # the possibly-new head

02Core techniques

Reversal — the "must write it cold" one

Walk the list, flipping each next pointer backwards. Three variables, one loop:

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next        # 1. save where we're going
        cur.next = prev       # 2. flip the arrow
        prev = cur            # 3. advance prev
        cur = nxt             # 4. advance cur
    return prev               # prev is the new head

The invariant to narrate out loud: "everything left of cur is already reversed and prev heads it; everything from cur onward is untouched." O(n) time, O(1) space.

Fast & slow pointers (tortoise and hare)

One pointer moves 1 step, the other 2. Two things fall out:

Middle of the list — when fast reaches the end, slow is at the middle:

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow = middle (second middle if even length)

Cycle detection (Floyd's algorithm) — if there's a cycle, fast laps slow and they must meet:

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

Why must they meet? Once both are inside the cycle, the gap between them shrinks by exactly 1 each step (fast gains 1 per step on a circular track). A shrinking non-negative gap hits 0. No set needed ⇒ O(1) space (the set version is fine too — say both, lead with Floyd).

Classic surgeries built from these parts

03Stacks: LIFO — "the undo button"

A stack is an access discipline, not a memory layout: push and pop at the same end. Last In, First Out.

push(A), push(B), push(C):      pop() → C  (most recent first)

        │ C │ ◄─ top
        │ B │
        │ A │
        └───┘

In Python, a plain list is a perfectly good stack — append/pop at the tail are O(1):

stack = []
stack.append(x)     # push
x = stack.pop()     # pop
top = stack[-1]     # peek

Valid Parentheses — the canonical stack problem

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack            # leftovers = unclosed openers

Three failure modes, all covered: wrong type (pop mismatch), close-with-nothing-open (not stack), unclosed leftovers (final check). Rattle those off and you're done.

Min Stack — O(1) minimum

"Design a stack that also returns the minimum in O(1)." The trick: a second stack recording the min-so-far at each depth; push/pop it in lockstep (or only push when a new min arrives).

class MinStack:
    def __init__(self):
        self.stack, self.mins = [], []
    def push(self, x):
        self.stack.append(x)
        self.mins.append(min(x, self.mins[-1]) if self.mins else x)
    def pop(self):
        self.mins.pop()
        return self.stack.pop()
    def get_min(self):
        return self.mins[-1]

Why it works: popping rewinds history, and mins is a snapshot of history — the min at every past depth is remembered, so rewinding restores it for free.

Monotonic stack — the pattern that feels like a superpower

When: "for each element, find the next/previous greater/smaller element" — or anything reducible to that (daily temperatures, stock span, largest rectangle in histogram, trapping rain water).

The idea: maintain a stack whose values are always e.g. decreasing. When a new element arrives that's bigger than the top, the top has just found its "next greater element" — pop it and record the answer. Keep popping while true; then push the new element.

def daily_temperatures(temps):
    ans = [0] * len(temps)
    stack = []                              # indices; temps decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j                  # today is j's next warmer day
        stack.append(i)
    return ans

temps: 73 74 75 71 69 72 76
   push 73 → 74 arrives: 74>73, pop 73 (ans=1), push 74
   75 arrives: pop 74 (ans=1), push 75
   71, 69 arrive: smaller, just pile up      stack: 75 71 69
   72 arrives: pop 69 (ans=1), pop 71 (ans=2), push 72
   76 arrives: pop 72, pop 75, push 76

Why the waiting elements can pile up: an element stays on the stack precisely while its answer is still unknown; the stack holds the "unresolved" elements, and they're necessarily in decreasing order (anything smaller than a newcomer would have been resolved by it).

04Queues & deques: FIFO — "the fair line"

Push at one end, pop at the other. First In, First Out. Queues model fairness and buffering: things are handled in arrival order.

enqueue ─► [ D │ C │ B │ A ] ─► dequeue
  (back)                       (front, oldest first)

q = [1, 2, 3]
x = q.pop(0)
# O(n) — shifts EVERY
# remaining element left

from collections import deque
q = deque()
q.append(x)      # enqueue (right)
x = q.popleft()  # dequeue — O(1)

A deque (double-ended queue, internally a doubly-linked list of blocks) does O(1) push/pop at both ends — it can impersonate both a stack and a queue, and it stars in the monotonic-deque solution to Sliding Window Maximum (keep indices of a decreasing sequence; front is always the window max — O(n) total).

Queue from two stacks (classic design question)

Two stacks: inbox and outbox. Enqueue → push to inbox. Dequeue → if outbox is empty, pour the entire inbox into it (reversing order — LIFO twice = FIFO), then pop outbox.

class MyQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []
    def push(self, x):
        self.inbox.append(x)
    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

Each element moves at most twice in its lifetime (in→over→out) ⇒ amortized O(1) per operation, even though a single pop can be O(n). (Yes — amortized analysis three times in one file. It's that common.)

05Choosing between them — the 10-second decision

06Common interview questions

07Self-test

1. Write iterative linked-list reversal from memory (4 lines inside the loop, in the right order). What's the loop invariant?
2. Why does a dummy node simplify deletion problems? Name two problems where you'd use one.
3. Floyd's cycle detection: why O(1) space, and why do the pointers necessarily meet?
4. Valid Parentheses: name the three distinct failure modes your code must catch.
5. Explain the Min Stack invariant in one sentence.
6. Daily Temperatures with a monotonic stack: what exactly is on the stack, and what does popping mean?
7. Prove (informally) the two-stack queue is amortized O(1).
8. list.pop(0) vs deque.popleft() — costs and why.
9. Find the middle of a linked list in one pass. For even length, which middle does your code return?
10. Sketch the LRU cache design: which structure gives O(1) lookup, which gives O(1) recency updates, and how are they wired together?