Academy — Sanjib Sikder

Why Build What Already Exists?

JavaScript gives you Array, Map, Set, and Object out of the box. You will never ship a linked list to production. So why build one?

Because understanding why Map.get is O(1) and Array.includes is O(n) changes every architectural decision you make at scale. When you have 100,000 records and your page freezes, the cause is almost always a data structure mismatch — the wrong tool for the access pattern. Building each structure from scratch makes the performance characteristics visceral, not theoretical.

Big-O — The One Concept That Ties Everything Together

Big-O notation describes how the time or space cost of an operation grows as the input grows. Not the exact time — the shape of the growth:

JavaScript

Ctrl+Enter to run

function bench(label, fn, sizes = [100, 1000, 10000, 100000]) {
  const times = sizes.map(n => {
    const data = Array.from({ length: n }, (_, i) => i);
    const t = performance.now();
    fn(data, n);
    return (performance.now() - t).toFixed(2);
  });
  console.log(`${label.padEnd(25)} ${times.map(t => t.padStart(8) + "ms").join("")}`);
}

console.log("Operation".padEnd(25), [100,1000,10000,100000].map(n => String(n).padStart(9)).join(""));
console.log("-".repeat(70));

// O(1) — constant: doesn't matter how large the array is
bench("O(1) array[0]", (arr) => arr[0]);

// O(log n) — logarithmic: doubles input, adds one step
bench("O(log n) binary srch", (arr, n) => {
let lo = 0, hi = n - 1, target = Math.floor(n / 2);
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] === target) break;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
});

// O(n) — linear: doubles input, doubles time
bench("O(n) array.includes", (arr, n) => arr.includes(Math.floor(n * 0.9)));

// O(n²) — quadratic: doubles input, quadruples time (only for small sizes)
bench("O(n²) nested loop", (arr, n) => {
if (n > 1000) return; // skip — too slow
let count = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
count++;
});

console.log("Operation".padEnd(25), [100,1000,10000,100000].map(n => String(n).padStart(9)).join(""));
console.log("-".repeat(70));

// O(1) — constant: doesn't matter how large the array is
bench("O(1) array[0]", (arr) => arr[0]);

// O(log n) — logarithmic: doubles input, adds one step
bench("O(log n) binary srch", (arr, n) => {
let lo = 0, hi = n - 1, target = Math.floor(n / 2);
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] === target) break;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
});

// O(n) — linear: doubles input, doubles time
bench("O(n) array.includes", (arr, n) => arr.includes(Math.floor(n * 0.9)));

// O(n²) — quadratic: doubles input, quadruples time (only for small sizes)
bench("O(n²) nested loop", (arr, n) => {
if (n > 1000) return; // skip — too slow
let count = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
count++;
});

The timing ratios tell the story. O(1) stays flat. O(n) doubles as input doubles. O(n²) would take hours at 100,000 items — which is why we cap it. Every data structure below is designed to give you O(1) or O(log n) for its primary operation.

Linked List — Sequential Access, O(1) Insert at Head

An array stores elements in contiguous memory — fast random access (arr[i] is O(1)) but slow insert/delete in the middle (everything shifts). A linked list stores elements anywhere in memory, connected by pointers — O(1) insert/delete at any known position, but O(n) to reach position i.

JavaScript

Ctrl+Enter to run

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

class LinkedList {
#head = null;
#size = 0;

prepend(value) { // O(1) — just update head
const node = new Node(value);
node.next = this.#head;
this.#head = node;
this.#size++;
return this;
}

append(value) { // O(n) — must walk to tail
const node = new Node(value);
if (!this.#head) { this.#head = node; this.#size++; return this; }
let curr = this.#head;
while (curr.next) curr = curr.next;
curr.next = node;
this.#size++;
return this;
}

delete(value) { // O(n) — must find the node
if (!this.#head) return this;
if (this.#head.value === value) {
this.#head = this.#head.next;
this.#size--;
return this;
}
let curr = this.#head;
while (curr.next && curr.next.value !== value) curr = curr.next;
if (curr.next) { curr.next = curr.next.next; this.#size--; }
return this;
}

has(value) { // O(n)
let curr = this.#head;
while (curr) { if (curr.value === value) return true; curr = curr.next; }
return false;
}

toArray() {
const result = [];
let curr = this.#head;
while (curr) { result.push(curr.value); curr = curr.next; }
return result;
}

get size() { return this.#size; }
}

const list = new LinkedList();
list.append(1).append(2).append(3).prepend(0);
console.log("List:", list.toArray()); // [0, 1, 2, 3]
console.log("Has 2:", list.has(2)); // true
console.log("Has 9:", list.has(9)); // false

list.delete(2);
console.log("After delete(2):", list.toArray()); // [0, 1, 3]
console.log("Size:", list.size);

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

class LinkedList {
#head = null;
#size = 0;

prepend(value) { // O(1) — just update head
const node = new Node(value);
node.next = this.#head;
this.#head = node;
this.#size++;
return this;
}

append(value) { // O(n) — must walk to tail
const node = new Node(value);
if (!this.#head) { this.#head = node; this.#size++; return this; }
let curr = this.#head;
while (curr.next) curr = curr.next;
curr.next = node;
this.#size++;
return this;
}

delete(value) { // O(n) — must find the node
if (!this.#head) return this;
if (this.#head.value === value) {
this.#head = this.#head.next;
this.#size--;
return this;
}
let curr = this.#head;
while (curr.next && curr.next.value !== value) curr = curr.next;
if (curr.next) { curr.next = curr.next.next; this.#size--; }
return this;
}

has(value) { // O(n)
let curr = this.#head;
while (curr) { if (curr.value === value) return true; curr = curr.next; }
return false;
}

toArray() {
const result = [];
let curr = this.#head;
while (curr) { result.push(curr.value); curr = curr.next; }
return result;
}

get size() { return this.#size; }
}

const list = new LinkedList();
list.append(1).append(2).append(3).prepend(0);
console.log("List:", list.toArray()); // [0, 1, 2, 3]
console.log("Has 2:", list.has(2)); // true
console.log("Has 9:", list.has(9)); // false

list.delete(2);
console.log("After delete(2):", list.toArray()); // [0, 1, 3]
console.log("Size:", list.size);

Stack — Last In, First Out

A stack is an array with restricted access: you can only push to the top and pop from the top. O(1) for both. The call stack in JavaScript is literally this data structure — every function call pushes a frame, every return pops one:

JavaScript

Ctrl+Enter to run

class Stack {
  #items = [];

push(item) { this.#items.push(item); return this; }
pop() { return this.#items.pop(); }
peek() { return this.#items[this.#items.length - 1]; }
isEmpty() { return this.#items.length === 0; }
get size() { return this.#items.length; }
toArray() { return [...this.#items].reverse(); } // top first
}

// Practical use: balanced bracket checker
function isBalanced(str) {
const stack = new Stack();
const pairs = { ")": "(", "]": "[", "}": "{" };
const openers = new Set(["(", "[", "{"]);

for (const ch of str) {
if (openers.has(ch)) stack.push(ch);
else if (ch in pairs) {
if (stack.isEmpty() || stack.pop() !== pairs[ch]) return false;
}
}
return stack.isEmpty();
}

const tests = [
"({[]})",
"function(a, b) { return [a, b]; }",
"({[}])",
"(((",
"",
];

tests.forEach(t => {
console.log(`${isBalanced(t) ? "✓" : "✗"} "${t.slice(0, 35)}"`);
});

// Undo/redo with two stacks
const history = new Stack();
const future = new Stack();
let doc = "";

function type(chars) {
history.push(doc);
future // clear redo on new action
while (!future.isEmpty()) future.pop();
doc += chars;
}
function undo() { if (!history.isEmpty()) { future.push(doc); doc = history.pop(); } }
function redo() { if (!future.isEmpty()) { history.push(doc); doc = future.pop(); } }

type("Hello");
type(", World");
type("!");
console.log("\nDoc:", doc);
undo();
console.log("After undo:", doc);
undo();
console.log("After undo:", doc);
redo();
console.log("After redo:", doc);

class Stack {
  #items = [];

push(item) { this.#items.push(item); return this; }
pop() { return this.#items.pop(); }
peek() { return this.#items[this.#items.length - 1]; }
isEmpty() { return this.#items.length === 0; }
get size() { return this.#items.length; }
toArray() { return [...this.#items].reverse(); } // top first
}

// Practical use: balanced bracket checker
function isBalanced(str) {
const stack = new Stack();
const pairs = { ")": "(", "]": "[", "}": "{" };
const openers = new Set(["(", "[", "{"]);

for (const ch of str) {
if (openers.has(ch)) stack.push(ch);
else if (ch in pairs) {
if (stack.isEmpty() || stack.pop() !== pairs[ch]) return false;
}
}
return stack.isEmpty();
}

const tests = [
"({[]})",
"function(a, b) { return [a, b]; }",
"({[}])",
"(((",
"",
];

tests.forEach(t => {
console.log(`${isBalanced(t) ? "✓" : "✗"} "${t.slice(0, 35)}"`);
});

// Undo/redo with two stacks
const history = new Stack();
const future = new Stack();
let doc = "";

type("Hello");
type(", World");
type("!");
console.log("\nDoc:", doc);
undo();
console.log("After undo:", doc);
undo();
console.log("After undo:", doc);
redo();
console.log("After redo:", doc);

Queue — First In, First Out

A queue is the opposite discipline: add to the back, remove from the front. O(1) enqueue, O(1) dequeue. Every task queue, event loop, and breadth-first search uses this structure:

JavaScript

Ctrl+Enter to run

// Naïve implementation — dequeue is O(n) due to array shift
class NaiveQueue {
  #items = [];
  enqueue(item) { this.#items.push(item); }
  dequeue()     { return this.#items.shift(); } // O(n) — everything shifts
  peek()        { return this.#items[0]; }
  get size()    { return this.#items.length; }
}

// Efficient implementation — O(1) dequeue using a head pointer
class Queue {
#items = {};
#head = 0;
#tail = 0;

enqueue(item) { this.#items[this.#tail++] = item; }
dequeue() {
if (this.isEmpty()) return undefined;
const item = this.#items[this.#head];
delete this.#items[this.#head++];
return item;
}
peek() { return this.#items[this.#head]; }
isEmpty() { return this.#head === this.#tail; }
get size() { return this.#tail - this.#head; }
}

// Benchmark: shift vs head-pointer
function benchQueue(QueueClass, n, label) {
const q = new QueueClass();
const t = performance.now();
for (let i = 0; i < n; i++) q.enqueue(i);
for (let i = 0; i < n; i++) q.dequeue();
console.log(`${label.padEnd(30)} ${(performance.now() - t).toFixed(2)}ms (n=${n})`);
}

benchQueue(NaiveQueue, 50000, "NaiveQueue (shift)");
benchQueue(Queue, 50000, "Queue (head pointer)");
benchQueue(NaiveQueue, 100000, "NaiveQueue (shift)");
benchQueue(Queue, 100000, "Queue (head pointer)");

// Naïve implementation — dequeue is O(n) due to array shift
class NaiveQueue {
  #items = [];
  enqueue(item) { this.#items.push(item); }
  dequeue()     { return this.#items.shift(); } // O(n) — everything shifts
  peek()        { return this.#items[0]; }
  get size()    { return this.#items.length; }
}

// Efficient implementation — O(1) dequeue using a head pointer
class Queue {
#items = {};
#head = 0;
#tail = 0;

enqueue(item) { this.#items[this.#tail++] = item; }
dequeue() {
if (this.isEmpty()) return undefined;
const item = this.#items[this.#head];
delete this.#items[this.#head++];
return item;
}
peek() { return this.#items[this.#head]; }
isEmpty() { return this.#head === this.#tail; }
get size() { return this.#tail - this.#head; }
}

// Benchmark: shift vs head-pointer
function benchQueue(QueueClass, n, label) {
const q = new QueueClass();
const t = performance.now();
for (let i = 0; i < n; i++) q.enqueue(i);
for (let i = 0; i < n; i++) q.dequeue();
console.log(`${label.padEnd(30)} ${(performance.now() - t).toFixed(2)}ms (n=${n})`);
}

benchQueue(NaiveQueue, 50000, "NaiveQueue (shift)");
benchQueue(Queue, 50000, "Queue (head pointer)");
benchQueue(NaiveQueue, 100000, "NaiveQueue (shift)");
benchQueue(Queue, 100000, "Queue (head pointer)");

The head-pointer queue pulls ahead dramatically as size grows — shift moves every remaining element in memory; the pointer just increments an integer.

Binary Search Tree — O(log n) Search, Insert, Delete

A BST organises data so that for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This invariant makes search O(log n) — each comparison eliminates half the remaining nodes:

JavaScript

Ctrl+Enter to run

class BSTNode {
  constructor(value) {
    this.value = value;
    this.left  = null;
    this.right = null;
  }
}

class BST {
#root = null;

insert(value) {
const node = new BSTNode(value);
if (!this.#root) { this.#root = node; return this; }
let curr = this.#root;
while (true) {
if (value < curr.value) {
if (!curr.left) { curr.left = node; break; }
curr = curr.left;
} else {
if (!curr.right) { curr.right = node; break; }
curr = curr.right;
}
}
return this;
}

has(value) { // O(log n) for balanced tree
let curr = this.#root;
while (curr) {
if (value === curr.value) return true;
curr = value < curr.value ? curr.left : curr.right;
}
return false;
}

// In-order traversal: left → node → right = sorted output
inOrder(node = this.#root, result = []) {
if (!node) return result;
this.inOrder(node.left, result);
result.push(node.value);
this.inOrder(node.right, result);
return result;
}

min() {
let curr = this.#root;
while (curr?.left) curr = curr.left;
return curr?.value;
}

max() {
let curr = this.#root;
while (curr?.right) curr = curr.right;
return curr?.value;
}
}

const bst = new BST();
[50, 30, 70, 20, 40, 60, 80, 35, 45].forEach(v => bst.insert(v));

console.log("In-order (sorted):", bst.inOrder());
console.log("Min:", bst.min(), " Max:", bst.max());
console.log("Has 40:", bst.has(40));
console.log("Has 55:", bst.has(55));

// Compare BST search vs array includes at scale
const n = 100000;
const vals = Array.from({ length: n }, (_, i) => i * 2); // even numbers
const arr = vals;
const tree = new BST();
vals.forEach(v => tree.insert(v));

const target = n; // middle value

let t = performance.now();
for (let i = 0; i < 1000; i++) arr.includes(target);
console.log(`\nArray includes (O(n)): ${(performance.now() - t).toFixed(2)}ms × 1000`);

t = performance.now();
for (let i = 0; i < 1000; i++) tree.has(target);
console.log(`BST has (O(log n)): ${(performance.now() - t).toFixed(2)}ms × 1000`);

class BSTNode {
  constructor(value) {
    this.value = value;
    this.left  = null;
    this.right = null;
  }
}

class BST {
#root = null;

insert(value) {
const node = new BSTNode(value);
if (!this.#root) { this.#root = node; return this; }
let curr = this.#root;
while (true) {
if (value < curr.value) {
if (!curr.left) { curr.left = node; break; }
curr = curr.left;
} else {
if (!curr.right) { curr.right = node; break; }
curr = curr.right;
}
}
return this;
}

has(value) { // O(log n) for balanced tree
let curr = this.#root;
while (curr) {
if (value === curr.value) return true;
curr = value < curr.value ? curr.left : curr.right;
}
return false;
}

// In-order traversal: left → node → right = sorted output
inOrder(node = this.#root, result = []) {
if (!node) return result;
this.inOrder(node.left, result);
result.push(node.value);
this.inOrder(node.right, result);
return result;
}

min() {
let curr = this.#root;
while (curr?.left) curr = curr.left;
return curr?.value;
}

max() {
let curr = this.#root;
while (curr?.right) curr = curr.right;
return curr?.value;
}
}

const bst = new BST();
[50, 30, 70, 20, 40, 60, 80, 35, 45].forEach(v => bst.insert(v));

console.log("In-order (sorted):", bst.inOrder());
console.log("Min:", bst.min(), " Max:", bst.max());
console.log("Has 40:", bst.has(40));
console.log("Has 55:", bst.has(55));

// Compare BST search vs array includes at scale
const n = 100000;
const vals = Array.from({ length: n }, (_, i) => i * 2); // even numbers
const arr = vals;
const tree = new BST();
vals.forEach(v => tree.insert(v));

const target = n; // middle value

let t = performance.now();
for (let i = 0; i < 1000; i++) arr.includes(target);
console.log(`\nArray includes (O(n)): ${(performance.now() - t).toFixed(2)}ms × 1000`);

t = performance.now();
for (let i = 0; i < 1000; i++) tree.has(target);
console.log(`BST has (O(log n)): ${(performance.now() - t).toFixed(2)}ms × 1000`);

Hash Map — O(1) Everything via Hashing

JavaScript's Map and {} are hash maps. The engine hashes your key to an integer, uses that as an array index, and stores the value there — O(1) get, set, and delete. The cost: extra memory for the hash table, and occasional O(n) when the table must resize. Building one reveals the mechanism:

JavaScript

Ctrl+Enter to run

class HashMap {
  #buckets;
  #size    = 0;
  #capacity;

constructor(capacity = 16) {
this.#capacity = capacity;
this.#buckets = Array.from({ length: capacity }, () => []);
}

#hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash * 31 + key.charCodeAt(i)) % this.#capacity;
}
return hash;
}

set(key, value) {
const idx = this.#hash(String(key));
const bucket = this.#buckets[idx];
const pair = bucket.find(([k]) => k === key);
if (pair) { pair[1] = value; }
else { bucket.push([key, value]); this.#size++; }

    // Resize when load factor exceeds 0.75
    if (this.#size / this.#capacity > 0.75) this.#resize();
    return this;

}

get(key) {
const bucket = this.#buckets[this.#hash(String(key))];
return bucket.find(([k]) => k === key)?.[1];
}

has(key) { return this.get(key) !== undefined; }

delete(key) {
const idx = this.#hash(String(key));
const bucket = this.#buckets[idx];
const i = bucket.findIndex(([k]) => k === key);
if (i !== -1) { bucket.splice(i, 1); this.#size--; return true; }
return false;
}

#resize() {
const old = this.#buckets;
this.#capacity *= 2;
this.#buckets = Array.from({ length: this.#capacity }, () => []);
this.#size = 0;
for (const bucket of old)
for (const [k, v] of bucket) this.set(k, v);
}

get size() { return this.#size; }

entries() {
return this.#buckets.flatMap(b => b);
}
}

const map = new HashMap();
map.set("name", "Rahul")
.set("marks", 82)
.set("city", "Kolkata");

console.log("name:", map.get("name"));
console.log("marks:", map.get("marks"));
console.log("has city:", map.has("city"));
console.log("size:", map.size);

map.delete("city");
console.log("after delete, has city:", map.has("city"));
console.log("entries:", map.entries());

// Practical: frequency count — O(n) total, O(1) per operation
function wordFrequency(text) {
const freq = new Map();
for (const word of text.toLowerCase().match(/\w+/g) ?? []) {
freq.set(word, (freq.get(word) ?? 0) + 1);
}
return [...freq.entries()].sort((a, b) => b[1] - a[1]);
}

const text = "the quick brown fox jumps over the lazy dog the fox";
console.log("\nWord frequency:", wordFrequency(text).slice(0, 5));

class HashMap {
  #buckets;
  #size    = 0;
  #capacity;

constructor(capacity = 16) {
this.#capacity = capacity;
this.#buckets = Array.from({ length: capacity }, () => []);
}

#hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash * 31 + key.charCodeAt(i)) % this.#capacity;
}
return hash;
}

set(key, value) {
const idx = this.#hash(String(key));
const bucket = this.#buckets[idx];
const pair = bucket.find(([k]) => k === key);
if (pair) { pair[1] = value; }
else { bucket.push([key, value]); this.#size++; }

// Resize when load factor exceeds 0.75
    if (this.#size / this.#capacity > 0.75) this.#resize();
    return this;

}

get(key) {
const bucket = this.#buckets[this.#hash(String(key))];
return bucket.find(([k]) => k === key)?.[1];
}

has(key) { return this.get(key) !== undefined; }

delete(key) {
const idx = this.#hash(String(key));
const bucket = this.#buckets[idx];
const i = bucket.findIndex(([k]) => k === key);
if (i !== -1) { bucket.splice(i, 1); this.#size--; return true; }
return false;
}

#resize() {
const old = this.#buckets;
this.#capacity *= 2;
this.#buckets = Array.from({ length: this.#capacity }, () => []);
this.#size = 0;
for (const bucket of old)
for (const [k, v] of bucket) this.set(k, v);
}

get size() { return this.#size; }

entries() {
return this.#buckets.flatMap(b => b);
}
}

const map = new HashMap();
map.set("name", "Rahul")
.set("marks", 82)
.set("city", "Kolkata");

console.log("name:", map.get("name"));
console.log("marks:", map.get("marks"));
console.log("has city:", map.has("city"));
console.log("size:", map.size);

map.delete("city");
console.log("after delete, has city:", map.has("city"));
console.log("entries:", map.entries());

// Practical: frequency count — O(n) total, O(1) per operation
function wordFrequency(text) {
const freq = new Map();
for (const word of text.toLowerCase().match(/\w+/g) ?? []) {
freq.set(word, (freq.get(word) ?? 0) + 1);
}
return [...freq.entries()].sort((a, b) => b[1] - a[1]);
}

const text = "the quick brown fox jumps over the lazy dog the fox";
console.log("\nWord frequency:", wordFrequency(text).slice(0, 5));

Graph — Connections Between Anything

A graph models relationships: social networks, road maps, dependency trees, the web itself. Nodes (vertices) connected by edges, which may be directed or weighted:

JavaScript

Ctrl+Enter to run

class Graph {
  #adj = new Map(); // adjacency list

addVertex(v) {
if (!this.#adj.has(v)) this.#adj.set(v, new Map());
return this;
}

addEdge(u, v, weight = 1) {
this.addVertex(u).addVertex(v);
this.#adj.get(u).set(v, weight);
this.#adj.get(v).set(u, weight); // undirected
return this;
}

neighbours(v) { return [...(this.#adj.get(v)?.keys() ?? [])]; }

// Breadth-First Search — shortest path in unweighted graph
bfs(start, target) {
const visited = new Set([start]);
const queue = [[start, [start]]];

    while (queue.length > 0) {
      const [node, path] = queue.shift();
      if (node === target) return path;

      for (const neighbour of this.neighbours(node)) {
        if (!visited.has(neighbour)) {
          visited.add(neighbour);
          queue.push([neighbour, [...path, neighbour]]);
        }
      }
    }
    return null; // no path

}

// Depth-First Search — find all reachable nodes
dfs(start, visited = new Set()) {
visited.add(start);
for (const neighbour of this.neighbours(start)) {
if (!visited.has(neighbour)) this.dfs(neighbour, visited);
}
return [...visited];
}

// Detect cycle
hasCycle() {
const visited = new Set();
const dfs = (node, parent) => {
visited.add(node);
for (const n of this.neighbours(node)) {
if (!visited.has(n)) { if (dfs(n, node)) return true; }
else if (n !== parent) return true;
}
return false;
};
for (const v of this.#adj.keys())
if (!visited.has(v) && dfs(v, null)) return true;
return false;
}
}

// Indian cities road network
const india = new Graph();
india
.addEdge("Kolkata", "Bhubaneswar", 440)
.addEdge("Kolkata", "Patna", 580)
.addEdge("Kolkata", "Guwahati", 990)
.addEdge("Patna", "Varanasi", 300)
.addEdge("Varanasi", "Lucknow", 330)
.addEdge("Lucknow", "Delhi", 550)
.addEdge("Delhi", "Jaipur", 280)
.addEdge("Delhi", "Mumbai", 1400)
.addEdge("Mumbai", "Pune", 150)
.addEdge("Bhubaneswar","Hyderabad", 760);

const path = india.bfs("Kolkata", "Delhi");
console.log("Shortest path Kolkata → Delhi:", path?.join(" → "));

const reachable = india.dfs("Kolkata");
console.log("Reachable from Kolkata:", reachable.sort().join(", "));

console.log("Has cycle:", india.hasCycle());

class Graph {
  #adj = new Map(); // adjacency list

addVertex(v) {
if (!this.#adj.has(v)) this.#adj.set(v, new Map());
return this;
}

addEdge(u, v, weight = 1) {
this.addVertex(u).addVertex(v);
this.#adj.get(u).set(v, weight);
this.#adj.get(v).set(u, weight); // undirected
return this;
}

neighbours(v) { return [...(this.#adj.get(v)?.keys() ?? [])]; }

// Breadth-First Search — shortest path in unweighted graph
bfs(start, target) {
const visited = new Set([start]);
const queue = [[start, [start]]];

while (queue.length > 0) {
      const [node, path] = queue.shift();
      if (node === target) return path;

for (const neighbour of this.neighbours(node)) {
        if (!visited.has(neighbour)) {
          visited.add(neighbour);
          queue.push([neighbour, [...path, neighbour]]);
        }
      }
    }
    return null; // no path

}

// Depth-First Search — find all reachable nodes
dfs(start, visited = new Set()) {
visited.add(start);
for (const neighbour of this.neighbours(start)) {
if (!visited.has(neighbour)) this.dfs(neighbour, visited);
}
return [...visited];
}

// Detect cycle
hasCycle() {
const visited = new Set();
const dfs = (node, parent) => {
visited.add(node);
for (const n of this.neighbours(node)) {
if (!visited.has(n)) { if (dfs(n, node)) return true; }
else if (n !== parent) return true;
}
return false;
};
for (const v of this.#adj.keys())
if (!visited.has(v) && dfs(v, null)) return true;
return false;
}
}

// Indian cities road network
const india = new Graph();
india
.addEdge("Kolkata", "Bhubaneswar", 440)
.addEdge("Kolkata", "Patna", 580)
.addEdge("Kolkata", "Guwahati", 990)
.addEdge("Patna", "Varanasi", 300)
.addEdge("Varanasi", "Lucknow", 330)
.addEdge("Lucknow", "Delhi", 550)
.addEdge("Delhi", "Jaipur", 280)
.addEdge("Delhi", "Mumbai", 1400)
.addEdge("Mumbai", "Pune", 150)
.addEdge("Bhubaneswar","Hyderabad", 760);

const path = india.bfs("Kolkata", "Delhi");
console.log("Shortest path Kolkata → Delhi:", path?.join(" → "));

const reachable = india.dfs("Kolkata");
console.log("Reachable from Kolkata:", reachable.sort().join(", "));

console.log("Has cycle:", india.hasCycle());

Priority Queue — Always Pop the Most Important

A priority queue returns the highest-priority item first, not the most recently added. The efficient implementation is a binary heap — a tree maintained in an array where every parent is smaller (min-heap) or larger (max-heap) than its children:

JavaScript

Ctrl+Enter to run

class MinHeap {
  #data = [];

push(value) {
this.#data.push(value);
this.#bubbleUp(this.#data.length - 1);
}

pop() {
if (this.size === 0) return undefined;
const min = this.#data[0];
const last = this.#data.pop();
if (this.size > 0) {
this.#data[0] = last;
this.#sinkDown(0);
}
return min;
}

peek() { return this.#data[0]; }
get size() { return this.#data.length; }

#bubbleUp(i) {
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.#data[parent] <= this.#data[i]) break;
[this.#data[parent], this.#data[i]] = [this.#data[i], this.#data[parent]];
i = parent;
}
}

#sinkDown(i) {
const n = this.size;
while (true) {
let smallest = i;
const l = 2 _ i + 1, r = 2 _ i + 2;
if (l < n && this.#data[l] < this.#data[smallest]) smallest = l;
if (r < n && this.#data[r] < this.#data[smallest]) smallest = r;
if (smallest === i) break;
[this.#data[smallest], this.#data[i]] = [this.#data[i], this.#data[smallest]];
i = smallest;
}
}
}

// Heap sort — build heap, pop everything out in order
function heapSort(arr) {
const heap = new MinHeap();
for (const n of arr) heap.push(n);
const sorted = [];
while (heap.size > 0) sorted.push(heap.pop());
return sorted;
}

const scores = [82, 91, 49, 78, 95, 63, 30, 55, 88, 71];
console.log("Unsorted:", scores);
console.log("Sorted: ", heapSort(scores));

// Practical: process tasks by urgency
class PriorityQueue {
#heap = [];

enqueue(item, priority) {
this.#heap.push({ item, priority });
this.#heap.sort((a, b) => b.priority - a.priority); // simple version
}

dequeue() { return this.#heap.shift()?.item; }
get size() { return this.#heap.length; }
}

const pq = new PriorityQueue();
pq.enqueue("Grade papers", 3);
pq.enqueue("Fix critical bug", 10);
pq.enqueue("Team meeting", 5);
pq.enqueue("Write lesson 27", 8);
pq.enqueue("Check email", 1);

console.log("\nTask order by priority:");
while (pq.size > 0) console.log(" ", pq.dequeue());

class MinHeap {
  #data = [];

push(value) {
this.#data.push(value);
this.#bubbleUp(this.#data.length - 1);
}

pop() {
if (this.size === 0) return undefined;
const min = this.#data[0];
const last = this.#data.pop();
if (this.size > 0) {
this.#data[0] = last;
this.#sinkDown(0);
}
return min;
}

peek() { return this.#data[0]; }
get size() { return this.#data.length; }

#bubbleUp(i) {
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.#data[parent] <= this.#data[i]) break;
[this.#data[parent], this.#data[i]] = [this.#data[i], this.#data[parent]];
i = parent;
}
}

#sinkDown(i) {
const n = this.size;
while (true) {
let smallest = i;
const l = 2 _ i + 1, r = 2 _ i + 2;
if (l < n && this.#data[l] < this.#data[smallest]) smallest = l;
if (r < n && this.#data[r] < this.#data[smallest]) smallest = r;
if (smallest === i) break;
[this.#data[smallest], this.#data[i]] = [this.#data[i], this.#data[smallest]];
i = smallest;
}
}
}

// Heap sort — build heap, pop everything out in order
function heapSort(arr) {
const heap = new MinHeap();
for (const n of arr) heap.push(n);
const sorted = [];
while (heap.size > 0) sorted.push(heap.pop());
return sorted;
}

const scores = [82, 91, 49, 78, 95, 63, 30, 55, 88, 71];
console.log("Unsorted:", scores);
console.log("Sorted: ", heapSort(scores));

// Practical: process tasks by urgency
class PriorityQueue {
#heap = [];

enqueue(item, priority) {
this.#heap.push({ item, priority });
this.#heap.sort((a, b) => b.priority - a.priority); // simple version
}

dequeue() { return this.#heap.shift()?.item; }
get size() { return this.#heap.length; }
}

const pq = new PriorityQueue();
pq.enqueue("Grade papers", 3);
pq.enqueue("Fix critical bug", 10);
pq.enqueue("Team meeting", 5);
pq.enqueue("Write lesson 27", 8);
pq.enqueue("Check email", 1);

console.log("\nTask order by priority:");
while (pq.size > 0) console.log(" ", pq.dequeue());

Choosing the Right Data Structure

JavaScript

Ctrl+Enter to run

// Decision guide — access pattern determines the structure

const guide = [
{
structure: "Array",
best: "Ordered, index access, iteration",
get: "O(1)", insert: "O(n)", search: "O(n)",
use: "Lists, stacks (with push/pop), ordered output",
},
{
structure: "Map / HashMap",
best: "Key → value lookup",
get: "O(1)", insert: "O(1)", search: "O(1)",
use: "Caches, frequency counts, any keyed access",
},
{
structure: "Set",
best: "Membership test, deduplication",
get: "O(1)", insert: "O(1)", search: "O(1)",
use: "Visited nodes, unique collections",
},
{
structure: "Linked List",
best: "Frequent insert/delete at known position",
get: "O(n)", insert: "O(1)*", search: "O(n)",
use: "Queues, LRU cache internals, undo chains",
},
{
structure: "BST",
best: "Sorted access + fast search",
get: "O(log n)", insert: "O(log n)", search: "O(log n)",
use: "Sorted data with frequent updates",
},
{
structure: "Heap",
best: "Always access min/max",
get: "O(1) peek", insert: "O(log n)", search: "O(n)",
use: "Priority queues, heap sort, Dijkstra's algorithm",
},
{
structure: "Graph",
best: "Relationships, paths, connectivity",
get: "—", insert: "O(1)", search: "O(V+E)",
use: "Networks, dependencies, routing, social graphs",
},
];

console.log("Structure".padEnd(14), "Get".padEnd(10), "Insert".padEnd(10), "Search".padEnd(10), "Best for");
console.log("-".repeat(75));
for (const g of guide) {
console.log(
g.structure.padEnd(14),
g.get.padEnd(10),
g.insert.padEnd(10),
g.search.padEnd(10),
g.use
);
}

// Decision guide — access pattern determines the structure

const guide = [
{
structure: "Array",
best: "Ordered, index access, iteration",
get: "O(1)", insert: "O(n)", search: "O(n)",
use: "Lists, stacks (with push/pop), ordered output",
},
{
structure: "Map / HashMap",
best: "Key → value lookup",
get: "O(1)", insert: "O(1)", search: "O(1)",
use: "Caches, frequency counts, any keyed access",
},
{
structure: "Set",
best: "Membership test, deduplication",
get: "O(1)", insert: "O(1)", search: "O(1)",
use: "Visited nodes, unique collections",
},
{
structure: "Linked List",
best: "Frequent insert/delete at known position",
get: "O(n)", insert: "O(1)*", search: "O(n)",
use: "Queues, LRU cache internals, undo chains",
},
{
structure: "BST",
best: "Sorted access + fast search",
get: "O(log n)", insert: "O(log n)", search: "O(log n)",
use: "Sorted data with frequent updates",
},
{
structure: "Heap",
best: "Always access min/max",
get: "O(1) peek", insert: "O(log n)", search: "O(n)",
use: "Priority queues, heap sort, Dijkstra's algorithm",
},
{
structure: "Graph",
best: "Relationships, paths, connectivity",
get: "—", insert: "O(1)", search: "O(V+E)",
use: "Networks, dependencies, routing, social graphs",
},
];

console.log("Structure".padEnd(14), "Get".padEnd(10), "Insert".padEnd(10), "Search".padEnd(10), "Best for");
console.log("-".repeat(75));
for (const g of guide) {
console.log(
g.structure.padEnd(14),
g.get.padEnd(10),
g.insert.padEnd(10),
g.search.padEnd(10),
g.use
);
}

What You Have Learned

Data structures are not academic — they are the difference between a feature that handles 100 users and one that handles 100,000.

The key ideas:

Big-O describes growth shape, not absolute time — O(1) is constant, O(log n) halves the problem each step, O(n) scales linearly, O(n²) becomes unusable at scale
Linked list: O(1) insert at known position, O(n) access by index — use when you insert/delete frequently at known nodes
Stack: O(1) push and pop, LIFO — the call stack, undo history, bracket matching
Queue: O(1) enqueue and dequeue (with head pointer), FIFO — task queues, BFS, event loops
BST: O(log n) search, insert, delete — in-order traversal yields sorted output
HashMap: O(1) get, set, delete via hashing — JavaScript's Map and {} are both hash maps
Graph: models connections — BFS finds shortest paths, DFS explores all reachable nodes
Heap / Priority Queue: O(1) peek at min/max, O(log n) insert and pop — the right tool whenever you need "give me the most important thing"

In the next lesson: Parsing & ASTs — how JavaScript reads your code before running it. Build a lexer, a parser, and a small interpreter. Understand how Babel, ESLint, and TypeScript process source code — and why this knowledge unlocks metaprogramming at the deepest level.

Data Structures from Scratch

Why Build What Already Exists?

Big-O — The One Concept That Ties Everything Together

Linked List — Sequential Access, O(1) Insert at Head

Stack — Last In, First Out

Queue — First In, First Out

Binary Search Tree — O(log n) Search, Insert, Delete

Hash Map — O(1) Everything via Hashing

Graph — Connections Between Anything

Priority Queue — Always Pop the Most Important

Choosing the Right Data Structure

What You Have Learned