Part 1 · 2 chapters · ~12 min

Arrays, Lists, Stacks and Queues

Arrays and dynamic arrays, linked lists and when they win, stacks and their uses, queues and deques, ring buffers, the monotonic stack and deque techniques, and choosing by the operations you need most.

3

What each structure makes cheap

Choose a structure by asking which operations happen most often, then pick the one that makes those cheap.

LINEAR STRUCTURES
what each makes cheap
arrayContiguous memory. O(1) index,cache-friendly scans; O(n) insertin the middle.linked listNodes with pointers. O(1)insert/delete at a known node;O(n) to find; cache-unfriendly.stack (LIFO)Push and pop at one end. Undo,call stacks, parsing, DFS.queue (FIFO)Enqueue at the back, dequeue atthe front. BFS, job queues,buffering.dequeBoth ends O(1). Sliding windowmaximum, work stealing.ring bufferFixed-size array with wrap-aroundindices. Logs, audio, networkbuffers.
swipe the figure sideways, or tap expand for full screen
1/6
arrays
Arrays are the default: contiguous memory makes scans fast (Computers part 2 measured 0.75 ns per element sequentially). Inserting in the middle shifts everything after it.
the default: fast scans, fast indexmiddle inserts are O(n)
4

Monotonic stacks and a ring buffer

code
// next greater element for every item, O(n) with a monotonic stack
function nextGreater(a: number[]): number[] {
  const out = Array(a.length).fill(-1), st: number[] = [];      // indices, values decreasing
  for (let i = 0; i < a.length; i++) {
    while (st.length && a[st[st.length - 1]] < a[i]) out[st.pop()!] = a[i];
    st.push(i);
  }
  return out;
}

// ring buffer: keep the last N values with no allocation
class Ring<T> {
  private buf: (T | undefined)[]; private head = 0; private size = 0;
  constructor(private cap: number) { this.buf = new Array(cap); }
  push(x: T) { this.buf[(this.head + this.size) % this.cap] = x; if (this.size < this.cap) this.size++; else this.head = (this.head + 1) % this.cap; }
  toArray(): T[] { return Array.from({ length: this.size }, (_, i) => this.buf[(this.head + i) % this.cap]!); }
}