Skip to content

Linked Lists, Stacks, and Queues

Linked lists, stacks, and queues are the building blocks of more complex data structures. This file covers their mechanics, then builds up the key patterns; fast/slow pointers, monotonic stacks, and heap-based priority queues, through progressively harder problems, with common pitfalls at each step.

  • Arrays give you fast random access but expensive insertions. Linked lists give you fast insertions but no random access. Stacks and queues restrict access to one or two ends, and this restriction is what makes them powerful: by limiting what you can do, they simplify what you need to think about.

Linked Lists

  • A singly linked list is a chain of nodes. Each node stores a value and a pointer to the next node. The last node points to null.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

  • Advantages over arrays: inserting or deleting at a known position is \(O(1)\) (just repoint the pointers). No need to shift elements.

  • Disadvantages: accessing element \(i\) requires \(O(i)\) traversal (no random access). Poor cache locality (nodes are scattered in memory).

  • Doubly linked lists add a prev pointer, enabling backward traversal. Used in LRU caches (constant-time removal of any node) and browser history (back/forward).

Operation Singly Doubly
Access by index \(O(n)\) \(O(n)\)
Insert at head \(O(1)\) \(O(1)\)
Insert at tail \(O(n)\) or \(O(1)\)* \(O(1)\)
Delete given node \(O(n)\)** \(O(1)\)
Search \(O(n)\) \(O(n)\)

with tail pointer. *need predecessor, which requires traversal.

  • Sentinel nodes (dummy head/tail) simplify edge cases. Without a dummy head, inserting at the head or deleting the head requires special-case code. With a dummy, every real node has a predecessor.
# Without dummy: special case for head deletion
def delete_head(head):
    if not head:
        return None
    return head.next

# With dummy: uniform logic
dummy = ListNode(0)
dummy.next = head
# now every deletion is: prev.next = prev.next.next
  • Pitfall: forgetting to handle the empty list (head is None) or the single-element list. Always test these edge cases.

Pattern: Fast and Slow Pointers (Floyd's)

  • Use two pointers moving at different speeds to detect properties of linked lists. The slow pointer moves one step at a time; the fast pointer moves two steps.

Easy: Linked List Cycle

  • Problem: determine if a linked list has a cycle.

  • Pattern: if there is a cycle, the fast pointer will eventually lap the slow pointer (they will meet). If there is no cycle, the fast pointer reaches null.

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

  • Why it works: if the cycle has length \(c\), the fast pointer closes the gap by 1 node per step. They must meet within \(c\) steps of the slow pointer entering the cycle.

  • Pitfall: checking fast and fast.next (not just fast.next). If fast is None, calling fast.next crashes.

Medium: Find the Middle of a Linked List

  • Problem: return the middle node.

  • Pattern: when the fast pointer reaches the end, the slow pointer is at the middle.

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # slow is at the middle (or second middle if even length)

Medium: Linked List Cycle II (Find Cycle Start)

  • Problem: return the node where the cycle begins.

  • Pattern: after fast and slow meet, reset one pointer to the head. Move both at speed 1. They meet at the cycle start.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # reset one pointer to head
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None
  • Why this works: let the distance from head to cycle start be \(a\), and the distance from cycle start to meeting point be \(b\). The slow pointer travelled \(a + b\). The fast pointer travelled \(2(a + b)\). The difference is one full cycle: \(a + b = c\) (cycle length). So \(a = c - b\): the distance from head to cycle start equals the distance from meeting point to cycle start (going forward around the cycle).

Hard: Reverse Linked List in Groups of K

  • Problem: reverse every \(k\) consecutive nodes in a linked list.
def reverse_k_group(head, k):
    # check if we have k nodes left
    node = head
    for _ in range(k):
        if not node:
            return head
        node = node.next

    # reverse k nodes
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # head is now the tail of the reversed group
    # recursively process the rest
    head.next = reverse_k_group(curr, k)
    return prev  # prev is the new head of this group
  • Pitfall: the in-place reversal pattern (prev, curr, nxt) is worth memorising. Draw it out: at each step, you point curr.next backward to prev, then advance all three pointers. Getting the order wrong corrupts the list.

Stacks

  • A stack is LIFO (Last In, First Out): the most recently added element is removed first. Think of a stack of plates.

  • Operations: push(x) adds to the top, pop() removes from the top, peek() looks at the top without removing. All \(O(1)\).

  • Stacks are the implicit structure behind recursion (the call stack), expression evaluation (converting infix to postfix), and undo operations (each action is pushed, undo pops the last one).

Easy: Valid Parentheses

  • Problem: given a string of brackets ()[]{}, determine if they are balanced.

  • Pattern: push opening brackets onto the stack. When you see a closing bracket, check that the top of the stack is the matching opener.

def is_valid(s):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in matching:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
        else:
            stack.append(char)

    return len(stack) == 0
  • Pitfall: forgetting len(stack) == 0 at the end. The string "(((" has no mismatches but is not valid because unclosed brackets remain.

Pattern: Monotonic Stack

  • A monotonic stack maintains elements in sorted order (either increasing or decreasing). When a new element would violate the order, you pop elements until the order is restored.

  • When to use: problems asking "for each element, find the next/previous greater/smaller element." The stack gives \(O(n)\) total because each element is pushed and popped at most once.

Medium: Daily Temperatures

  • Problem: given daily temperatures, for each day find how many days until a warmer temperature.

  • Pattern: use a stack of indices. When the current temperature is higher than the stack's top, pop and record the distance.

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # stack of indices, temperatures in decreasing order

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev = stack.pop()
            result[prev] = i - prev
        stack.append(i)

    return result

  • Each element is pushed once and popped at most once: \(O(n)\) total.

  • Pitfall: storing indices on the stack (not values). You need the index to compute the distance.

Hard: Largest Rectangle in Histogram

  • Problem: given an array of bar heights, find the area of the largest rectangle.

  • Pattern: for each bar, find how far left and right it can extend (i.e., the nearest shorter bar on each side). A monotonic increasing stack tracks this efficiently.

def largest_rectangle(heights):
    stack = []  # stack of indices, heights in increasing order
    max_area = 0
    heights.append(0)  # sentinel to flush the stack at the end

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx  # this bar can extend back to where the popped bar started
        stack.append((start, h))

    heights.pop()  # remove sentinel
    return max_area

  • Pitfall: the start = idx line is subtle. When we pop a bar that is taller than the current bar, the current bar can extend backward to where the popped bar started (because all bars in between were at least as tall as the popped bar). Missing this line gives incorrect areas.

  • Pitfall: the sentinel heights.append(0) ensures all remaining bars in the stack are processed. Without it, bars that never encounter a shorter bar to their right are missed.

Queues

  • A queue is FIFO (First In, First Out): elements are added at the back and removed from the front. Think of a line at a shop.

  • A deque (double-ended queue) supports \(O(1)\) insertion and removal at both ends. Python's collections.deque is the standard implementation.

  • Queues are the structure behind BFS (breadth-first search, chapter 14 file 4), task scheduling, and message passing.

Easy: Implement Queue Using Stacks

  • Problem: implement a queue using only two stacks.

  • Pattern: use one stack for pushing and one for popping. When the pop stack is empty, transfer all elements from the push stack (reversing the order).

class MyQueue:
    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

    def push(self, x):
        self.push_stack.append(x)

    def pop(self):
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack.pop()

    def peek(self):
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack[-1]

    def empty(self):
        return not self.push_stack and not self.pop_stack
  • Amortised \(O(1)\) per operation: each element is moved between stacks at most once.

Priority Queues and Heaps

  • A priority queue returns the smallest (or largest) element first, regardless of insertion order. The standard implementation is a binary heap.

  • A min-heap is a complete binary tree where every parent is smaller than its children. The minimum is always at the root. Stored as an array: the children of node \(i\) are at positions \(2i + 1\) and \(2i + 2\).

Operation Time
Insert \(O(\log n)\)
Get min \(O(1)\)
Extract min \(O(\log n)\)
Build heap from array \(O(n)\)
  • Python's heapq module provides a min-heap. For a max-heap, negate the values.
import heapq

# Min-heap
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
print(heapq.heappop(h))  # 2 (smallest)

# Max-heap trick: negate values
heapq.heappush(h, -10)
print(-heapq.heappop(h))  # 10 (largest)

Medium: Kth Largest Element in an Array

  • Problem: find the kth largest element.

  • Pattern: maintain a min-heap of size \(k\). The heap's root is the kth largest. If the heap has \(k\) elements and a new element is larger than the root, replace the root.

import heapq

def find_kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)  # O(k)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)  # pop min, push num: O(log k)

    return heap[0]

  • \(O(n \log k)\) time, \(O(k)\) space. Much better than sorting (\(O(n \log n)\)) when \(k \ll n\).

  • Pitfall: using a max-heap of size \(n\) and popping \(k\) times also works but is slower: \(O(n + k \log n)\). The min-heap of size \(k\) is the optimal approach.

Hard: Merge K Sorted Lists

  • Problem: merge \(k\) sorted linked lists into one sorted list.

  • Pattern: use a min-heap containing the head of each list. Pop the smallest, add it to the result, and push its next node onto the heap.

import heapq

def merge_k_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))

    dummy = ListNode(0)
    curr = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

  • \(O(n \log k)\) where \(n\) is the total number of nodes. The heap always has at most \(k\) elements.

  • Pitfall: the i (index) in the heap tuple is a tiebreaker. Without it, Python tries to compare ListNode objects when values are equal, which crashes because ListNode does not support <. The index ensures a valid comparison.

Common Pitfalls Summary

Pitfall Example Fix
Null pointer on fast.next Cycle detection with while fast.next Check fast and fast.next
Not handling empty list Reverse of None Add if not head guard
Stack underflow Popping from empty stack Check len(stack) > 0 or if stack
Forgetting sentinel Histogram misses last bars Append 0 to flush the stack
Missing tiebreaker in heap Comparing uncomparable objects Add index to heap tuple
Modifying list during iteration Removing nodes while traversing Use prev/curr pattern or dummy head

Take-Home Problems (NeetCode)

Linked Lists

Stacks

Heaps / Priority Queues