Stacks, Queues and Linked Lists

Mental model: A data structure is a promise about which operations stay cheap. A stack promises the end, a queue promises both ends, a linked list promises anywhere you already hold a reference to.

Level: advanced · about 20 minutes

You already have one general purpose container, and it is very good: the array. What these three structures add is not capability, it is a guarantee. Each one gives up some access in exchange for keeping a particular operation constant no matter how big the collection gets, and knowing which guarantee you need is the whole skill.

Stack: last in, first out

A stack only lets you touch the top. Push a value on, pop the most recent one off, peek at it without removing it. An array gives you exactly that for free, because push and pop both work at the cheap end.

const history = [];

function apply(state, action) {
  history.push({ action, previous: state });
  return action.next;
}

function undo(state) {
  const last = history.pop();
  if (!last) {
    console.log('nothing to undo');
    return state;
  }
  console.log('undoing', last.action.name);
  return last.previous;
}

let text = '';
text = apply(text, { name: 'type hello', next: 'hello' });
text = apply(text, { name: 'type world', next: 'hello world' });
console.log('now:', text);      // -> now: hello world
text = undo(text);              // -> undoing type world
console.log('now:', text);      // -> now: hello
text = undo(text);              // -> undoing type hello
console.log('now:', JSON.stringify(text)); // -> now: ""
console.log(undo(text) === '' ? 'still empty' : '?'); // -> nothing to undo, still empty

An undo history. The most recent action is the only one you can undo, which is why a stack fits.

class Stack {
  #items = [];
  push(v) { this.#items.push(v); return this; }
  pop() { return this.#items.pop(); }
  peek() { return this.#items.at(-1); }
  get size() { return this.#items.length; }
}

function makeStack() {
  const items = [];
  return {
    push: (v) => { items.push(v); },
    pop: () => items.pop(),
    peek: () => items.at(-1),
    get size() { return items.length; },
  };
}

Stacks turn up whenever the most recent thing is the thing you care about: undo history, breadcrumb navigation, matching brackets, depth-first traversal, and the call stack itself, which is why deep recursion overflows a stack rather than a queue.

function isBalanced(source) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const open = new Set(Object.values(pairs));
  const stack = [];

  for (const ch of source) {
    if (open.has(ch)) stack.push(ch);
    else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;   // wrong closer, or nothing open
    }
  }
  return stack.length === 0;                          // anything left open fails
}

console.log(isBalanced('a(b[c]{d})'));  // -> true
console.log(isBalanced('a(b[c)]'));     // -> false, crossed pairs
console.log(isBalanced('((('));         // -> false, never closed
console.log(isBalanced(')('));          // -> false, closed before opened

Balanced brackets: the classic stack problem, and a real one if you ever parse anything.

Queue: first in, first out

A queue serves the oldest item first: a print spool, a task runner, the breadth-first traversal in the next lesson. Written with an array it is two lines, and one of those lines is the quadratic one from 16.1.

function shiftQueue(n) {
  const q = [];
  const t0 = performance.now();
  for (let i = 0; i < n; i += 1) q.push(i);
  let sum = 0;
  while (q.length) sum += q.shift();          // O(n) per call
  return performance.now() - t0;
}

function indexQueue(n) {
  const q = [];
  let head = 0;
  const t0 = performance.now();
  for (let i = 0; i < n; i += 1) q.push(i);
  let sum = 0;
  while (head < q.length) sum += q[head++];   // O(1) per call
  return performance.now() - t0;
}

for (const n of [10000, 20000, 40000]) {
  console.log('n =', n, '| shift', shiftQueue(n).toFixed(1) + 'ms', '| head index', indexQueue(n).toFixed(2) + 'ms');
}
// -> n = 10000 | shift 20.7ms  | head index 9.14ms
// -> n = 20000 | shift 180.7ms | head index 0.66ms
// -> n = 40000 | shift 984.6ms | head index 2.25ms

Same queue semantics, two implementations. Give this a couple of seconds.

The fix is to stop moving the data and move the reader instead. Dequeue reads items[head] and increments head, so nothing is renumbered and every operation is constant. The cost is memory: the slots before head are still allocated and still hold references, so a long-lived queue leaks. Two habits fix that. Null out the slot as you pass it (items[head] = undefined) so the value can be collected, and compact occasionally, for example when head has passed half the array, by replacing items with items.slice(head) and resetting head to zero. Compaction is O(n), it happens once per half-length, so it amortises to constant.

after 3 enqueues, 0 dequeues        after 2 dequeues
  head                                          head
   v                                             v
[ a , b , c ,   ,   ]                 [ x , x , c ,   ,   ]
               ^                                     ^
              tail                                  tail

dequeue: read items[head], set items[head] = undefined, head += 1
compact when head > items.length / 2:  items = items.slice(head); head = 0

function makeQueue() {
  let inbox = [];      // new arrivals land here
  let outbox = [];     // reversed, so the oldest is on top

  return {
    enqueue(value) {
      inbox.push(value);
    },
    dequeue() {
      if (outbox.length === 0) {
        while (inbox.length) outbox.push(inbox.pop());   // flip once
      }
      return outbox.pop();
    },
    get size() {
      return inbox.length + outbox.length;
    },
  };
}

const q = makeQueue();
q.enqueue('a'); q.enqueue('b'); q.enqueue('c');
console.log(q.dequeue());   // -> a   (one flip moved all three)
q.enqueue('d');
console.log(q.dequeue());   // -> b   (no flip, outbox still has b and c)
console.log(q.dequeue());   // -> c
console.log(q.dequeue());   // -> d   (one flip, for d alone)
console.log(q.size, q.dequeue()); // -> 0 undefined

The two-stack queue: the version interviewers ask for, because the amortised argument is the point.

Any single dequeue can be O(n), because it may have to flip the whole inbox. But each value is pushed to the inbox once, popped from the inbox once, pushed to the outbox once and popped from the outbox once: four operations per value, forever, no matter how the calls interleave. So n values cost O(n) in total, which is amortised O(1) each. That is the same argument as array growth in 16.1, and it is worth being able to say out loud.

const q = [];
let head = 0;
q.push('a', 'b', 'c');

const first = q[head++];
const second = q[head++];

console.log(first, second, q.length, q.length - head);

Reading through a head index never removes anything, so q.length is still 3: the array holds a and b as dead slots. The live size of a queue like this is length - head, which is 1. Forgetting that distinction is how a head-index queue quietly grows forever, and it is why the exercise below asks for a size getter rather than exposing the array.

Deque: cheap at both ends

A double-ended queue adds and removes at either end in constant time. Arrays can only do it at one end, so the trick is to stop using positions as storage and use keys instead. A Map accepts negative integer keys quite happily, so growing leftwards costs nothing.

function makeDeque() {
  const cells = new Map();
  let head = 0;      // index of the first item
  let tail = 0;      // one past the last item

  return {
    pushBack(v) { cells.set(tail, v); tail += 1; },
    pushFront(v) { head -= 1; cells.set(head, v); },
    popFront() {
      if (head === tail) return undefined;
      const v = cells.get(head);
      cells.delete(head);
      head += 1;
      return v;
    },
    popBack() {
      if (head === tail) return undefined;
      tail -= 1;
      const v = cells.get(tail);
      cells.delete(tail);
      return v;
    },
    get size() { return tail - head; },
    toArray() {
      const out = [];
      for (let i = head; i < tail; i += 1) out.push(cells.get(i));
      return out;
    },
  };
}

const d = makeDeque();
d.pushBack('b'); d.pushBack('c'); d.pushFront('a');
console.log(d.toArray(), d.size);      // -> [ 'a', 'b', 'c' ] 3
console.log(d.popFront(), d.popBack()); // -> a c
console.log(d.toArray(), d.size);       // -> [ 'b' ] 1
console.log(d.popBack(), d.popBack());  // -> b undefined

A deque with no copying anywhere: two integers and a Map.

Linked list: a chain of objects

A linked list stores each value in its own node object, alongside a reference to the next node. There is no index arithmetic, so nothing ever has to move when you insert or delete. There is also no index arithmetic, so reading the thousandth element means following a thousand references.

head                                              tail
 |                                                 |
 v                                                 v
+-------+     +-------+     +-------+     +-------+
| 'a'   | --> | 'b'   | --> | 'c'   | --> | 'd'   | --> null
+-------+     +-------+     +-------+     +-------+

unshift('z'):  create a node, point it at head, move head.
               Nothing else in the chain is touched.

for (const n of [10000, 20000, 40000]) {
  const arr = [];
  let t0 = performance.now();
  for (let i = 0; i < n; i += 1) arr.unshift(i);        // every element renumbered, every time
  const asArray = performance.now() - t0;

  let head = null;
  t0 = performance.now();
  for (let i = 0; i < n; i += 1) head = { value: i, next: head };   // one allocation
  const asList = performance.now() - t0;

  console.log('n =', n, '| array.unshift', asArray.toFixed(1) + 'ms', '| list prepend', asList.toFixed(2) + 'ms');
}
// -> n = 10000 | array.unshift 33.0ms   | list prepend 1.97ms
// -> n = 20000 | array.unshift 180.6ms  | list prepend 0.28ms
// -> n = 40000 | array.unshift 1034.8ms | list prepend 2.94ms

Prepending 40,000 items, both ways. This is the one case where the list wins outright.

Be careful what you conclude from that. The list wins prepending and it wins deleting a node you already hold. It loses almost everything else, and not by a little: an array of numbers is one contiguous block that the CPU prefetches into cache, while a list of 40,000 nodes is 40,000 separate objects with a pointer each, so iterating it can be several times slower than iterating an array of the same length even though both are O(n). Big-O cannot see cache lines. In practice the honest advice for JavaScript is: use an array, use a head index when you need a queue, and reach for a real linked list when you specifically need O(1) removal from the middle while holding a reference to the node. That case is not hypothetical: it is exactly how the LRU cache in 16.4 keeps its recency order.

1. Hold three references Reversing a singly linked list in place is the classic pointer exercise. You need the node behind you, the node you are on, and the node ahead, because rewriting current.next destroys your only route forward.
2. Save the road ahead before you cut it Every iteration: remember current.next, point current.next backwards, then shuffle all three references forward one node.
3. Move the ends When the loop ends, current is null and previous is the old last node, which is the new head. If you keep a tail pointer, the old head is now the tail, so capture it before you start.

Try it yourself

Race two queues

const SIZE = 20000;   // change me

function timed(label, drain) {
  const t0 = performance.now();
  const total = drain();
  const ms = performance.now() - t0;
  console.log(label.padEnd(14), ms.toFixed(2) + 'ms', '| checksum', total);
}

timed('shift', () => {
  const q = [];
  for (let i = 0; i < SIZE; i += 1) q.push(i);
  let sum = 0;
  while (q.length) sum += q.shift();
  return sum;
});

timed('head index', () => {
  const q = [];
  for (let i = 0; i < SIZE; i += 1) q.push(i);
  let head = 0;
  let sum = 0;
  while (head < q.length) sum += q[head++];
  return sum;
});

Push SIZE to 100000 and watch only the shift version get slower, then add a third queue that nulls out each slot after reading it and check the timing is unchanged.

Walk a chain by hand

const fromArray = (values) => {
  let head = null;
  for (let i = values.length - 1; i >= 0; i -= 1) head = { value: values[i], next: head };
  return head;
};

const toArray = (head) => {
  const out = [];
  for (let node = head; node; node = node.next) out.push(node.value);
  return out;
};

const list = fromArray(['a', 'b', 'c', 'd']);
console.log(toArray(list));          // -> [ 'a', 'b', 'c', 'd' ]

// delete 'b' given the node before it: one assignment, no shifting
const first = list;
first.next = first.next.next;
console.log(toArray(list));          // -> [ 'a', 'c', 'd' ]

// insert 'z' after 'a'
first.next = { value: 'z', next: first.next };
console.log(toArray(list));          // -> [ 'a', 'z', 'c', 'd' ]

Add a find(head, value) that returns the node and counts how many nodes it had to touch, then build a list of 100000 nodes and find the last one. The count is the complexity.

Exercises

A queue that stays fast

Write class Queue with enqueue(value), dequeue(), peek() and a size getter. dequeue and peek return undefined on an empty queue. Every operation must be constant or amortised constant, so 100,000 enqueues followed by 100,000 dequeues has to finish quickly: no shift, no splice.

Singly linked list with push, unshift and reverse

Write class LinkedList with push(value) (add at the end), unshift(value) (add at the front), toArray(), reverse() (in place, returning the list) and a size getter. push and unshift must both be O(1), which means keeping a tail reference, and reverse must keep it correct so a push afterwards still lands at the end.

Check yourself

Why does a head-index queue need a size getter rather than exposing items.length?

because the slots before the head are still in the array, so length overcounts — Dequeuing moves the head forward and leaves the consumed slots in place, so items.length counts items that have already been served. The live count is items.length - head. This is also why you null out consumed slots: otherwise those references keep objects alive that the queue has logically finished with.

What does this log?

1 then 2 3 undefined — The first dequeue finds the outbox empty and flips the inbox into it, reversing [1, 2] into [2, 1], so popping gives 1. Enqueueing 3 goes to the inbox and does not disturb the outbox, so the next pop is 2. Only then is the outbox empty again, triggering a flip that brings 3 across. Fourth call: both empty, pop on an empty array is undefined.

You need to remove items from the middle of a 100,000 item collection, and you already hold a reference to each item. Which structure?

a doubly linked list — With a reference to the node, a doubly linked list unlinks it in constant time by joining its neighbours to each other. splice on an array is O(n) per removal because everything after the hole is renumbered, so 100,000 removals is quadratic. A singly linked list is not enough on its own: you also need the previous node, which is exactly why the doubly linked variant exists.

Iterating a linked list of 100,000 numbers versus an array of the same 100,000 numbers:

the array is usually several times faster despite both being O(n) — Both are O(n), and big-O deliberately ignores the constant. The array is one contiguous block, so the CPU prefetches the next elements into cache. The list is thousands of separate objects, so each hop can be a cache miss. This is the honest limit of complexity analysis: it tells you the shape of the curve, not the size of the constant, and both decide whether your page feels fast.

Common mistakes

• Building a queue on shift because it reads well, then meeting it again in a profiler.
• Using a head index but reporting items.length as the size.
• Never compacting a head-index queue, so a long-lived queue holds every value it ever saw.
• Forgetting to move the tail reference when reversing a list, so the next push attaches to the wrong end.
• Rewriting current.next before saving it, which loses the rest of the chain.
• Reaching for a linked list because the big-O table looks better, then losing to cache locality.
• Exposing the backing array from a stack or queue, so callers can splice the invariant away.

Takeaways

• A stack is an array used only at the cheap end: push and pop.
• Never build a queue on shift. Keep a head index, and compact when the dead prefix grows past half.
• The two-stack queue is amortised O(1) because each value moves exactly four times, however the calls interleave.
• A deque needs both ends cheap, which a Map with integer keys gives you without any copying.
• Linked lists trade indexed access for O(1) insertion and removal at a node you already hold.
• Reversing a list in place is three references: previous, current, and the saved next.
• Big-O cannot see cache locality, which is why arrays usually beat lists in practice.