Scrolls
4 min read
On this page

Stacks, Queues & Linked Lists

These three structures are simpler than trees and graphs, but they appear in interviews more often than most candidates expect. Stacks solve matching and nesting problems. Queues power BFS and order-preserving processing. Linked lists test pointer manipulation and careful edge-case handling. The problems are not conceptually difficult — they are mechanically tricky, and the difference between passing and failing is usually handling edge cases correctly.

Stacks

A stack is last-in, first-out (LIFO). Push adds to the top, pop removes from the top. Both operations are O(1).

Stack operations:
  push(item)    O(1)   Add to top
  pop()         O(1)   Remove and return top
  peek()/top()  O(1)   View top without removing
  is_empty()    O(1)   Check if empty

Matching & Nesting

The canonical stack problem is parentheses matching. Any problem involving nested or paired structures — brackets, tags, undo/redo — is a stack problem.

Problem: Determine if a string of brackets is valid.
  Input: "({[]})"  -> True
  Input: "({[}])"  -> False
  Input: "((("     -> False

Approach:
  matching = {')': '(', '}': '{', ']': '['}
  stack = []

  for char in s:
      if char in '({[':
          stack.push(char)
      elif char in ')}]':
          if stack is empty or stack.pop() != matching[char]:
              return False

  return stack is empty

Why a stack works: The most recently opened bracket must be the
first one closed. This is exactly LIFO order.

Monotonic Stack

A monotonic stack maintains elements in sorted order (either increasing or decreasing). It solves "next greater element" and "next smaller element" problems efficiently.

Problem: For each element in an array, find the next greater element.
  Input:  [4, 5, 2, 10, 8]
  Output: [5, 10, 10, -1, -1]

Approach:
  stack = []      # stores indices, maintains decreasing values
  result = [-1] * len(arr)

  for i in range(len(arr)):
      while stack and arr[i] > arr[stack[-1]]:
          idx = stack.pop()
          result[idx] = arr[i]
      stack.push(i)

How it works: When we encounter a value larger than the stack's
top, we have found the "next greater" for that top element.
We keep popping until the stack's top is no longer smaller.
Time: O(n) because each element is pushed and popped at most once.

Expression Evaluation

Stacks evaluate mathematical expressions, especially when converting from infix to postfix notation or evaluating postfix directly.

Problem: Evaluate a postfix (reverse Polish notation) expression.
  Input: ["2", "3", "+", "4", "*"]
  Meaning: (2 + 3) * 4 = 20

Approach:
  stack = []
  for token in tokens:
      if token is a number:
          stack.push(int(token))
      else:
          b = stack.pop()
          a = stack.pop()
          if token == '+': stack.push(a + b)
          if token == '-': stack.push(a - b)
          if token == '*': stack.push(a * b)
          if token == '/': stack.push(int(a / b))

  return stack.pop()

Undo Operations

Any system with undo/redo is naturally modeled with stacks. The action stack records operations; undo pops the last action; redo pops from a second stack.

undo_stack = []
redo_stack = []

def perform(action):
    undo_stack.push(action)
    redo_stack.clear()    # redo invalidated by new action

def undo():
    action = undo_stack.pop()
    redo_stack.push(action)
    reverse(action)

def redo():
    action = redo_stack.pop()
    undo_stack.push(action)
    replay(action)

Queues

A queue is first-in, first-out (FIFO). Enqueue adds to the back, dequeue removes from the front. Both operations are O(1).

Queue operations:
  enqueue(item)  O(1)   Add to back
  dequeue()      O(1)   Remove and return front
  peek()/front() O(1)   View front without removing
  is_empty()     O(1)   Check if empty

BFS

The primary interview use of queues is BFS traversal. The queue ensures nodes are processed in order of their distance from the source.

Problem: Find the shortest path in a maze from start to end.

  queue = [(start_row, start_col, 0)]   # row, col, distance
  visited = set()
  visited.add((start_row, start_col))

  while queue:
      row, col, dist = queue.popleft()
      if (row, col) == end:
          return dist
      for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
          nr, nc = row + dr, col + dc
          if is_valid(nr, nc) and (nr, nc) not in visited:
              visited.add((nr, nc))
              queue.append((nr, nc, dist + 1))

  return -1   # no path found

Order-Preserving Processing

Queues maintain processing order. When tasks must be handled in the order they arrive, a queue is the natural structure.

Problem: Given a stream of tasks with timestamps, process them
in arrival order.

  task_queue = Queue()

  def on_task_arrival(task):
      task_queue.enqueue(task)

  def process_next():
      if not task_queue.is_empty():
          task = task_queue.dequeue()
          execute(task)

Deque (Double-Ended Queue)

A deque supports push and pop from both ends in O(1). It is useful when you need both stack and queue behavior or when you need a sliding window maximum/minimum.

Problem: Find the maximum in every sliding window of size k.

  deque = []   # stores indices in decreasing order of values
  result = []

  for i in range(len(arr)):
      # Remove elements outside the window
      while deque and deque[0] <= i - k:
          deque.popleft()

      # Remove elements smaller than current (they can never be max)
      while deque and arr[deque[-1]] < arr[i]:
          deque.pop()

      deque.append(i)

      if i >= k - 1:
          result.append(arr[deque[0]])

  return result

Time: O(n). Each element enters and leaves the deque at most once.

Linked Lists

A linked list is a sequence of nodes where each node points to the next. The key advantage over arrays: O(1) insertion and deletion at any position (given a pointer to that position). The key disadvantage: no random access — finding the nth element requires O(n) traversal.

Linked list operations:
  Access by index:       O(n)
  Search:                O(n)
  Insert at head:        O(1)
  Insert at position:    O(1) if you have the pointer, O(n) to find it
  Delete at position:    O(1) if you have the pointer, O(n) to find it

Reversing a Linked List

The most common linked list interview problem. It tests pointer manipulation.

Reverse a singly linked list:
  prev = None
  curr = head

  while curr is not None:
      next_node = curr.next    # save next
      curr.next = prev         # reverse the link
      prev = curr              # advance prev
      curr = next_node         # advance curr

  return prev   # new head

Trace through example [1 -> 2 -> 3]:
  Step 1: prev=None, curr=1. 1.next=None. prev=1, curr=2.
  Step 2: prev=1,    curr=2. 2.next=1.    prev=2, curr=3.
  Step 3: prev=2,    curr=3. 3.next=2.    prev=3, curr=None.
  Result: 3 -> 2 -> 1

If you cannot write this from memory, practice until you can. It appears in interviews constantly and serves as a building block for harder linked list problems.

Detecting a Cycle

Floyd's cycle detection (tortoise and hare): use two pointers, one moving twice as fast as the other. If there is a cycle, they will meet.

  slow = head
  fast = head

  while fast is not None and fast.next is not None:
      slow = slow.next
      fast = fast.next.next
      if slow == fast:
          return True   # cycle detected

  return False   # no cycle (fast reached the end)

Why it works: If there is a cycle, the fast pointer enters it first.
The slow pointer then enters. Because the fast pointer moves 2 steps
per iteration while slow moves 1, the gap between them decreases by 1
each iteration. They must eventually meet.

Finding the Middle

Same two-pointer technique: when fast reaches the end, slow is at the middle.

  slow = head
  fast = head

  while fast is not None and fast.next is not None:
      slow = slow.next
      fast = fast.next.next

  return slow   # middle node

Merging Two Sorted Lists

  def merge(l1, l2):
      dummy = Node(0)
      current = dummy

      while l1 and l2:
          if l1.val <= l2.val:
              current.next = l1
              l1 = l1.next
          else:
              current.next = l2
              l2 = l2.next
          current = current.next

      current.next = l1 or l2   # attach remaining
      return dummy.next

The dummy node trick avoids special-casing the head of the result list.
This is a standard technique — use it whenever you are building a new
linked list.

When These Simple Structures Are the Right Tool

Use a stack when:
  - Matching or nesting (brackets, tags, expressions)
  - Most recent first processing (undo, back button)
  - Next greater/smaller element problems
  - DFS (iterative implementation)

Use a queue when:
  - BFS traversal
  - Order-preserving processing
  - Scheduling (process in arrival order)
  - Sliding window max/min (deque variant)

Use a linked list when:
  - Frequent insertion/deletion at arbitrary positions
  - Building an LRU cache (doubly linked list + hash map)
  - Merging sorted sequences
  - Problems that explicitly use linked lists (many interview
    questions give you a linked list as input)

The Dummy Node Pattern

When building or modifying linked lists, a dummy (sentinel) node at the head simplifies code by eliminating special cases:

Without dummy node:
  if head is None:
      head = new_node
  else:
      ... find the right position and insert ...

With dummy node:
  dummy = Node(0)
  dummy.next = head
  ... always the same logic, no special case for head ...
  return dummy.next

Use the dummy node pattern by default in interviews. It prevents bugs and makes your code cleaner.

Common Pitfalls

  • Null pointer errors in linked lists: The most common linked list bug. Always check node is not None before accessing node.next or node.val.
  • Losing the reference to head: When modifying a linked list, keep a reference to the head (or use a dummy node). If you lose it, you lose the entire list.
  • Forgetting to handle empty input: Empty stack, empty queue, empty list (null head). Always handle these cases first.
  • Off-by-one in fast/slow pointers: For finding the middle of an even-length list, whether slow ends up at the first or second middle node depends on the exact loop condition. Trace through a 4-element example to verify.
  • Stack overflow with recursive linked list operations: Reversing a linked list recursively works but uses O(n) stack space. For very long lists, prefer the iterative version.
  • Using an array as a queue: Removing from the front of an array is O(n) because all elements shift. Use a proper queue (deque in Python, LinkedList in Java) for O(1) operations.
  • Not recognizing stack problems: If the problem involves "most recent" processing, nesting, or "undo," think stack immediately. Engineers often reach for complex solutions when a simple stack solves the problem.

Key Takeaways

  • Stacks solve matching, nesting, and "most recent first" problems. If brackets, parentheses, or undo/redo appear in a problem, reach for a stack.
  • Queues power BFS and any problem requiring FIFO processing. The deque variant handles sliding window max/min in O(n).
  • Linked list problems test careful pointer manipulation. Practice reversing a list and detecting cycles until you can write them without thinking.
  • The dummy node pattern eliminates edge cases in linked list problems. Use it by default.
  • These structures are simple, but the problems they solve trip up candidates who overcomplicate things. Sometimes the right answer to a hard-looking problem is just a stack.