Linked lists, stacks and queues patterns

Linked lists, stacks and queues are basic structures, but interviewers love them because they test careful thinking about pointers and order.

Linked list

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node (a doubly linked list also points to the previous one). There is no index: to reach the 5th node you walk from the head.

Operation	Cost
Access by position	O(n)
Search	O(n)
Insert or delete at the head	O(1)
Insert or delete after a node you already hold	O(1)

Compared with an array, a linked list is cheap to insert and remove in the middle once you have the node, but slow to reach it, and it has poor cache locality. Arrays are usually faster in practice, so linked lists matter mostly for interviews and in specific structures (LRU caches, queues).

class Node { constructor(val, next = null) { this.val = val; this.next = next; } }

Pattern 1: reverse a list

Walk through the list and flip each pointer, keeping track of the previous node.

function reverse(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;   // remember the rest
    cur.next = prev;         // flip
    prev = cur;
    cur = next;
  }
  return prev;               // new head
}
// Time O(n), space O(1)

Pattern 2: fast and slow pointers

Move one pointer one step and another two steps at a time.

Find the middle: when the fast pointer reaches the end, the slow one is in the middle.
Detect a cycle: if there is a cycle, the fast pointer eventually meets the slow one (Floyd's algorithm).

Pattern 3: dummy head

A dummy node before the head removes special cases when the head itself may change, for example when merging two sorted lists or removing a node.

function mergeTwoLists(a, b) {
  const dummy = new Node(0);
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

Common mistakes with linked lists

Losing the rest of the list by overwriting next before saving it.
Not handling an empty list, a single node, or removing the head.
Infinite loops when a cycle exists.
Off-by-one when removing the Nth node from the end (use two pointers N apart).

Stack

A stack is last in, first out (LIFO): like a pile of plates. Operations: push, pop, peek, each O(1). In many languages an array works as a stack.

Uses: undo, the function call stack, parsing, backtracking, and matching brackets.

Pattern: matching brackets

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}
// Time O(n), space O(n)

Pattern: monotonic stack

Keep the stack in increasing or decreasing order, popping items that can no longer be the answer. It solves "next greater element" style problems in O(n).

function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];                    // holds indices with no answer yet
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

Each index is pushed and popped once, so it is O(n). Related problems: daily temperatures, largest rectangle in a histogram, stock span.

Queue

A queue is first in, first out (FIFO), like a line at a shop. Operations: enqueue at the back and dequeue from the front, both O(1) with a proper implementation.

Warning: in JavaScript, array.shift() can be O(n). For real queues use an index pointer, a linked list or a deque library.

Uses: task scheduling, buffering, and breadth-first search (BFS) on trees and graphs, which explores level by level.

Deque (double-ended queue): add and remove at both ends. A monotonic deque solves the sliding window maximum in O(n).
Priority queue (heap): removes the smallest or largest first, in O(log n).

Classic puzzles

Implement a queue using two stacks, and a stack using two queues.
Min stack: a stack that returns the minimum in O(1) (store the running minimum with each element).
Evaluate a postfix expression with a stack.

Choosing between them

Need	Use
Most recent first, undo, matching, DFS	Stack
Oldest first, level by level, scheduling	Queue
Fast insert and remove at both ends	Deque
Always the smallest or largest next	Heap / priority queue
Quick insert in the middle with a node in hand	Linked list

Practice problems

Reverse Linked List, Merge Two Sorted Lists, Linked List Cycle, Remove Nth Node From End, Valid Parentheses, Min Stack, Daily Temperatures, Implement Queue using Stacks, Sliding Window Maximum.

Takeaway: for linked lists, draw the pointers, use a dummy head and fast/slow pointers. Use a stack for nested or "most recent" problems, and a queue for level-by-level processing.

Interview prep and DSA series, Part 2 (data structures and behaviour): 1 of 5.

Linked lists, stacks and queues: patterns for interviews