4.7 — Linked Lists, Stacks, Queues & Deques

An array pays for O(1) random access with O(n) insertion. A linked list makes the opposite trade: it gives up the address formula entirely, so it can never jump to element 500,000, but it can splice a new element into the middle in constant time — if you are already standing there.

That last clause is where most of the confusion lives, so we build the structure first and then get very precise about what "constant time insertion" actually promises.

1. The node, and what changes when you drop the address formula

class ListNode<T> {                    // (1)
  value: T;
  next: ListNode<T> | null = null;     // (2)
  constructor(value: T) { this.value = value; }
}

1. A node holds one value.
2. And a reference to the next node, or null if it is the last one. That reference is the entire structure — there is no block of memory, no capacity, no length field built in.

Because the nodes are allocated separately, they can sit anywhere in memory. Node 3 might live at address 8000 and node 4 at address 12,376,192. There is no formula from index to address, so finding element k means starting at the head and following k references. Access is O(n), and there is nothing clever to do about it.

The array keeps its promise of consecutive addresses, so it can compute where element i lives. The list keeps no such promise, so it must walk — but inserting X means writing two pointer fields and moving no data at all.

Now the precise version of "O(1) insertion". Inserting after a node you already hold is two assignments, so it is genuinely O(1):

function insertAfter<T>(node: ListNode<T>, value: T): void {
  const fresh = new ListNode(value);   // (1)
  fresh.next = node.next;              // (2)  ← must come first
  node.next = fresh;                   // (3)
}

1. Allocate the new node.
2. Point the new node at whatever came after node. This line must come before line 3. If you overwrite node.next first, you have lost the reference to the rest of the list and it is gone.
3. Now point node at the new node.

But inserting at index k is O(n), because you have to walk to index k first. So the honest statement is: a linked list has O(1) insertion given a reference to the position, and O(n) to find that position. The structure only wins when the reference comes to you for free — which happens in exactly two situations, and they are the two situations where linked lists actually get used in real systems:

• You are already iterating, so you hold the node anyway. This is how a garbage collector's free list or a scheduler's run queue works.
• Something else is holding the node for you. This is the important one, and it is the design behind the LRU cache in Chapter 9.7.30: a hash map stores key → node, so the map hands you the node in O(1), and then unlinking it is O(1). Neither structure could do it alone.

2. Singly, doubly, and circular

Singly linked is what we built: one next pointer per node. Cheapest in memory, and you can only move forward. Deleting a node requires a pointer to its predecessor, which is why singly linked deletion is usually written as "delete the node after this one".

Doubly linked adds a prev pointer:

class DListNode<T> {
  value: T;
  prev: DListNode<T> | null = null;
  next: DListNode<T> | null = null;
  constructor(value: T) { this.value = value; }
}

function unlink<T>(node: DListNode<T>): void {   // (1)
  if (node.prev) node.prev.next = node.next;     // (2)
  if (node.next) node.next.prev = node.prev;     // (3)
  node.prev = node.next = null;                  // (4)
}

1. This function is the reason doubly linked lists exist. Given only the node, it removes it from the list in constant time. A singly linked list cannot do this, because it cannot find the predecessor without walking from the head.
2. The predecessor now skips over us.
3. The successor now points back past us.
4. Clearing our own pointers is not required for correctness but it matters for memory: a removed node still pointing into the live list keeps those nodes reachable, and in a reference-counted runtime (Chapter 3.4) that is a leak.

The two if checks in lines 2 and 3 are the head and tail special cases, and they are the single most common source of bugs in list code. The standard fix is sentinel nodes: allocate one permanent dummy node at each end that holds no real value. Now every real node is guaranteed to have both a predecessor and a successor, the ifs vanish, and the code has one path instead of four. This is not a micro-optimisation — it is a correctness technique, and Chapter 9.7.30 uses it for exactly that reason.

Circular lists have the last node point back to the first. They are used for round-robin scheduling (Chapter 2.3) and for ring buffers, because "advance to the next one" never needs a wrap-around check.

3. The honest verdict: when is a linked list the right answer?

Almost never, on its own, in application code. That is not a fashionable thing to say about a structure that half of all DSA courses open with, so here is the argument in full.

The cache argument. Chapter 1.6 and 4.2 covered this: an array's elements share cache lines, so walking one is a stream of cheap sequential reads that the CPU prefetches ahead of you. A list's nodes are scattered, so every next is a potential cache miss costing around 100 nanoseconds. Traversing 1,000 array elements might cost a few microseconds; traversing 1,000 scattered list nodes can cost 100 microseconds. Big-O calls both O(n) and they differ by a factor of 20 or more.

The memory argument. A node for one 8-byte number costs 8 bytes of value, 8 bytes of next pointer, 8 more for prev if doubly linked, plus an object header (16 bytes on many runtimes) and allocator padding. Storing a million numbers costs 8 MB in an array and 40 MB in a doubly linked list.

The "but insertion is O(1)" argument, examined. For a middle insertion you must first find the position, which is O(n) pointer chases with cache misses. The array must shift, which is O(n) — but a shift is memmove, one of the most heavily optimised operations in existence, moving contiguous bytes at many gigabytes per second. In measured benchmarks the array wins for middle insertion up to surprisingly large sizes, often tens of thousands of elements.

So when does a list genuinely win?

• When something else holds the node reference for you (the LRU cache pattern).
• When you need stable references — an array's elements move when it resizes or shifts, so any pointer or index you saved becomes wrong. A list node's address never changes, which is why kernel data structures, intrusive lists in C, and undo/redo chains use them.
• When you need to splice whole sublists together in O(1), which arrays cannot do at all.
• When you cannot afford the worst case of a resize copy, as in a real-time system with a hard deadline.

In interviews, linked lists are a different thing entirely. They are tested not because you will build one, but because manipulating pointers correctly is a clean test of careful thinking — reversal, cycle detection, merging, finding the middle. Chapter 4.9 works through exactly those, and every one of them is really a test of whether you can hold three pointers in your head without losing the list.

4. Reversal: the three-pointer dance

This is the single most-asked linked list question, and it is worth walking one step at a time because the ordering of the four lines is the entire problem.

function reverse<T>(head: ListNode<T> | null): ListNode<T> | null {
  let prev: ListNode<T> | null = null;   // (1)
  let curr = head;                       // (2)
  while (curr !== null) {
    const next = curr.next;              // (3)  ← save before we destroy it
    curr.next = prev;                    // (4)  ← the actual reversal
    prev = curr;                         // (5)
    curr = next;                         // (6)
  }
  return prev;                           // (7)
}

1. prev starts as null, because the old head becomes the new tail and a tail points at nothing.
2. curr walks the original list.
3. Line 3 is why this works. The next line is about to overwrite curr.next, which is our only route to the rest of the list. Saving it first is not defensive style, it is mandatory — without it the remaining nodes become unreachable and (in a garbage-collected language) get collected.
4. Flip this node's arrow to point backwards.
5. and 6. Slide both pointers one step along.
6. When curr falls off the end, prev is sitting on the last node processed, which is the new head.

Trace it on A → B → C:

Step	prev	curr	list so far
start	null	A	A→B→C
after 1	A	B	A→null, B→C
after 2	B	C	B→A→null, C
after 3	C	null	C→B→A→null

O(n) time, O(1) space. The recursive version is elegant and O(n) space because of the call stack, which is a trade worth naming out loud in an interview rather than presenting as free.

5. Floyd's cycle detection, and why the fast pointer moves by two

"Does this list have a loop in it?" You could store every visited node in a set, which is O(n) time and O(n) space. Floyd's algorithm does it in O(1) space.

function hasCycle<T>(head: ListNode<T> | null): boolean {
  let slow = head, fast = head;                       // (1)
  while (fast !== null && fast.next !== null) {       // (2)
    slow = slow!.next;                                // (3)  one step
    fast = fast.next.next;                            // (4)  two steps
    if (slow === fast) return true;                   // (5)
  }
  return false;                                       // (6)
}

1. Both start at the head.
2. The guard checks fast and fast.next, because line 4 dereferences both. Getting this condition wrong is the classic crash.
3. and 4. The slow pointer takes one step per iteration, the fast pointer takes two.
4. If they ever land on the same node, there is a cycle.
5. If fast reaches the end, the list is a straight line and there is no cycle.

Why they must meet. Once both pointers are inside the loop, think about the gap between them measured along the loop. Each iteration, fast gains exactly one position on slow. A gap that shrinks by exactly 1 each step can never jump over zero — it must eventually be zero. That is the whole proof, and it is also why the fast pointer moves by two rather than three: with a step of three the gap shrinks by two per iteration, which can skip over zero on a loop of odd length, so you would have to compare more carefully.

Finding where the loop starts. After they meet, reset one pointer to the head and advance both one step at a time; they meet at the loop's entry point. The reason is a short piece of arithmetic. Let a be the distance from head to loop start, b the distance from loop start to the meeting point, and c the rest of the loop, so the loop length is b + c. When they meet, slow has travelled a + b and fast has travelled twice that, 2(a+b), and fast's distance is also a + b + k(b+c) for some number of extra laps k. Setting those equal gives a + b = k(b + c), so a = k(b+c) - b, which means a equals c plus some whole number of laps. Walking a steps from the head and a steps from the meeting point therefore lands on the same node: the loop's start.

That derivation is worth being able to reproduce, because "why does resetting to the head work?" is the standard follow-up and reciting the algorithm without it is exactly what interviewers are screening for.

6. Stack: last in, first out

A stack allows exactly two operations — push a value on the top, pop the top value off — plus usually a peek. That restriction is the point: by removing choices, the structure guarantees an ordering property that whole algorithms are built on.

In practice you never implement one; you use an array with push and pop, both of which are O(1) amortized, both of which operate at the end of the array where nothing has to shift.

function isBalanced(source: string): boolean {          // (1)
  const stack: string[] = [];
  const closes: Record<string, string> = { ')': '(', ']': '[', '}': '{' };  // (2)
  for (const ch of source) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);             // (3)
    else if (ch in closes) {
      if (stack.pop() !== closes[ch]) return false;                          // (4)
    }
  }
  return stack.length === 0;                                                 // (5)
}

1. Checking whether brackets in source code are correctly nested — the classic stack problem, and a real part of every parser (Chapter 3.1).
2. A lookup from each closing bracket to the opening one it must match.
3. An opener goes on the stack: "I am now waiting for this to be closed."
4. A closer must match the most recently opened bracket, which is exactly what pop gives. If it does not match, or the stack was empty (pop on an empty array returns undefined, which never equals a bracket), the string is malformed.
5. Anything left on the stack is an opener that was never closed.

The reason a stack and not a counter: a counter tells you ([)] has equal counts, and it is still wrong. The stack remembers the order, and nesting is an ordering property.

Stacks are everywhere once you know the shape. The call stack (Chapter 2.2) is one, and it is why recursion works — every recursive algorithm is a stack algorithm that lets the language manage the stack for you, and every recursive algorithm can be rewritten iteratively with an explicit stack. Undo history is a stack (Chapter 9.7.12). Expression evaluation, depth-first search, backtracking, the browser's back button, and the monotonic stack family in Chapter 4.8 are all stacks.

7. Queue: first in, first out, and the mistake everyone makes

A queue adds at one end and removes from the other. Fair ordering — the thing that has waited longest goes next.

Here is the mistake, and it is genuinely common in production JavaScript:

const queue: Task[] = [];
queue.push(task);           // O(1)  ✔
const next = queue.shift(); // O(n)  ✘  every remaining element shifts left one slot

shift removes from the front of an array, so all n−1 remaining elements move down one index. Processing a queue of 100,000 items this way costs 5 billion element moves. It works fine in testing with 50 items and falls over in production.

The fix is a circular buffer, which is what a real queue implementation uses: a fixed array with a head index and a tail index that wrap around.

class Queue<T> {
  private buffer: (T | undefined)[];
  private head = 0;                                     // (1)
  private tail = 0;
  private count = 0;

  constructor(capacity = 16) { this.buffer = new Array(capacity); }

  enqueue(value: T): void {
    if (this.count === this.buffer.length) this.grow();  // (2)
    this.buffer[this.tail] = value;
    this.tail = (this.tail + 1) % this.buffer.length;    // (3)  ← the wrap
    this.count++;
  }

  dequeue(): T | undefined {
    if (this.count === 0) return undefined;
    const value = this.buffer[this.head];
    this.buffer[this.head] = undefined;                  // (4)
    this.head = (this.head + 1) % this.buffer.length;
    this.count--;
    return value;
  }

  private grow(): void {
    const bigger = new Array(this.buffer.length * 2);
    for (let i = 0; i < this.count; i++) {
      bigger[i] = this.buffer[(this.head + i) % this.buffer.length];  // (5)
    }
    this.buffer = bigger; this.head = 0; this.tail = this.count;
  }
}

1. head is where the next dequeue reads; tail is where the next enqueue writes. Both march forward and wrap around, so the contents rotate through the array rather than being shifted.
2. Same doubling rule as the dynamic array in 4.2.
3. The modulo is the whole trick. When tail reaches the end of the array it wraps to 0, and since head has also moved forward, those early slots are free.
4. Clearing the slot is not needed for the index arithmetic, but it releases the reference so the garbage collector can free the task object. Leaving stale references in a buffer is a real memory leak.
5. On growth, the elements are un-rotated back to starting at index 0, which is why head resets to 0.

Every operation is O(1) amortized and nothing ever shifts. In a language with a proper deque — Python's collections.deque, Java's ArrayDeque — you get this for free and should never write it. In JavaScript there is no built-in deque, so for a hot queue you either write the above or use the two-index trick: keep pushing, and instead of shift, keep a head index into the array and only compact when the head passes half the length.

Where queues show up: BFS in Chapter 4.19 is defined by its queue — that is the only difference between BFS and DFS. Task scheduling (Chapter 2.3), message brokers (Chapter 10.8.1), the event loop's task queues (Chapter 3.6.8), and rate-limiter buckets (Chapter 9.7.5) are all queues.

8. Deque: both ends, and the sliding-window maximum

A deque ("deck", double-ended queue) allows push and pop at both ends, all in O(1). The circular buffer above already supports it — just add operations that move head backwards and tail forwards.

A deque is what you reach for when you need to look at both the newest and the oldest thing. The standard use is the monotonic deque, which answers "what is the maximum in every window of size k" in O(n) total rather than O(nk):

function maxOfEachWindow(nums: number[], k: number): number[] {
  const out: number[] = [];
  const dq: number[] = [];                                   // (1) holds indices, not values
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0] <= i - k) dq.shift();          // (2) drop what fell out of the window
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();  // (3) drop the useless
    dq.push(i);                                              // (4)
    if (i >= k - 1) out.push(nums[dq[0]]);                   // (5)
  }
  return out;
}

1. Storing indices rather than values is what makes step 2 possible — you cannot tell whether a value has expired, but you can always tell whether an index has.
2. The front of the deque is the current maximum's index. If that index is older than the window, it is no longer eligible, so remove it from the front.
3. This is the insight. If the number arriving at index i is larger than the number at the back of the deque, that back number can never be the maximum of any future window — because i is inside every future window that contains it, and i is bigger. So it is not merely smaller, it is permanently useless, and we discard it. This keeps the deque sorted in decreasing order.
4. Now i goes on the back.
5. Once the first full window exists, the front of the deque is its maximum.

The complexity argument is worth stating carefully because it looks like a nested loop: each index is pushed exactly once and popped at most once, so across the whole run the inner while loops do at most n pops total. That is O(n) amortized, not O(nk). This "each element enters and leaves once" argument is the standard way to prove that a while inside a for is still linear, and it comes back in Chapters 4.6 and 4.10.

(In real code, line 2's shift should be a real deque operation; using an array's shift here reintroduces the O(n) problem from section 7. It is written this way only to keep the example readable.)

What the interviewer will push on

"Linked list insertion is O(1) — so is it better than an array for a list you insert into a lot?" The trap answer is yes. The real answer separates finding the position (O(n) with cache misses) from doing the insertion (O(1)), then notes that the array's O(n) shift is a single contiguous memmove that runs far faster per element. Then name the case where the list genuinely wins: when a hash map hands you the node, as in an LRU cache.

"Reverse a linked list — now do it recursively. What changed?" They are checking whether you notice the space. Iterative is O(1) space; recursive is O(n) because of the call stack, and on a million-node list it overflows. Volunteering that trade before being asked is the tell.

"Why does the fast pointer move by two?" The answer is the gap argument: the gap shrinks by exactly one per iteration, so it cannot skip zero. A candidate who has memorised the code cannot answer this; one who understands it can also tell you why step size three is riskier.

"You used array.shift() for your BFS queue. Any problem at scale?" This is asked more often than people expect, because it is a real production bug. shift is O(n), making BFS O(n^2). Fix: a head index into the array, or a proper deque.

"When would you use a doubly linked list over a singly linked one, given it costs 50% more memory?" When you must remove a node given only that node, in O(1). That single capability is the entire justification, and it is exactly what the LRU cache needs.

One thing to volunteer: mention sentinel nodes. Saying "I would put a dummy head and tail node in so that every real node has a neighbour and the insert and delete paths have no null checks" tells an interviewer you have written this code and got the edge cases wrong before, which is the most credible signal there is.

Recall

• A linked list trades the array's address formula for cheap splicing: access becomes O(n), and insertion is O(1) only if you already hold the node.
• Doubly linked exists for one reason — removing a node given only that node, in O(1). Sentinel head and tail nodes delete the null-check special cases.
• On real hardware arrays usually beat lists even for middle insertion, because of cache lines and memmove; lists win when a hash map holds the node, when references must stay stable, or when a resize copy would blow a deadline.
• Reversal needs three pointers and the next must be saved before the link is overwritten; the recursive version costs O(n) stack space.
• Floyd's two pointers must meet because the gap shrinks by exactly one per step; resetting one pointer to the head then finds the loop's entry, from a = c + k(b+c).
• A stack gives nesting, a queue gives fairness; in JavaScript array.shift() is O(n), so a real queue uses a circular buffer with head and tail indices.
• A monotonic deque answers sliding-window maximum in O(n) because each index is pushed once and popped at most once.

Self-test: Why must const next = curr.next come before curr.next = prev? · Give the one situation where a linked list genuinely beats an array, and say why. · What is wrong with queue.shift() in a BFS over a million nodes? · Prove that the monotonic deque loop is O(n) and not O(nk). · Why does storing indices rather than values matter in the sliding-window maximum?

Next: 4.8 puts the stack to work on seven problems, including the monotonic stack — the version that answers "next greater element" for a whole array in one pass.