These are the notes for JavaScript episode 35, part two of data structures. Adding coaches at the front of a train with unshift gets four times slower every time the train doubles, so we invent a linked list: nodes joined by next. Inserting after a coach that doesn't exist crashes with Cannot read properties of null, so we learn to check for null. Then Ravi's directory of a million contacts needs a million steps to find Neha, so we turn names into numbers with a hash function, handle collisions with buckets, build our own hash table, and meet JavaScript's built-in Map, which also fixes a nasty bug in plain-object word counters. Every output below is real Node.js output (Node 24). Timings change from run to run; the way they grow is what matters. Long stack traces are shortened with ....
Builds on: arrays (episode 7), objects (8), classes (16), prototypes (17), Map and Set (21), Big O, stacks and queues (34). Leads to: DSA in JavaScript 3: trees and graphs (36).
Why the front of an array is slow
In an array, items sit in numbered slots, side by side. Adding at the front (unshift) means every existing item must move one slot to the right. In a train, that would mean moving every coach to add one coach behind the engine.
function addAtFront(n) {
const coaches = [];
const start = performance.now();
for (let i = 1; i <= n; i++) coaches.unshift(i);
return Math.round(performance.now() - start) + " ms";
}
console.log("50,000 coaches:", addAtFront(50000));
console.log("100,000 coaches:", addAtFront(100000));
Output (one run):
50,000 coaches: 203 ms
100,000 coaches: 840 ms
Twice the coaches, about four times the time: each unshift is O(n), so n of them are O(n²).
Inventing a linked list: coaches and couplings
| In a train | In code |
|---|---|
| a coach | a node: { value, next } |
| the coupling to the next coach | next: a reference to the next node |
| the engine, where the train starts | the head |
| the last coach, nothing behind it | next is null |
A linked list is a chain of nodes. Each node holds a value and a reference (a pointer) to the next node. Nodes can sit anywhere in memory; the next references hold the chain together, so adding a node never moves the others.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
const engine = new Node("Engine");
const s1 = new Node("S1");
const s2 = new Node("S2");
engine.next = s1;
s1.next = s2;
let cur = engine;
while (cur !== null) {
console.log(cur.value);
cur = cur.next;
}
console.log(engine);
Output:
Engine
S1
S2
Node {
value: 'Engine',
next: Node { value: 'S1', next: Node { value: 'S2', next: null } }
}
Walking (traversing) a linked list: start at the head and follow next until you reach null.
A LinkedList class with prepend
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
prepend(value) {
this.head = new Node(value, this.head);
}
toString() {
const out = [];
for (let cur = this.head; cur !== null; cur = cur.next) out.push(cur.value);
return out.join(" -> ");
}
}
const train = new LinkedList();
train.prepend("S2");
train.prepend("S1");
train.prepend("Engine");
console.log(train.toString());
function addAtFront(n) {
const coaches = new LinkedList();
const start = performance.now();
for (let i = 1; i <= n; i++) coaches.prepend(i);
return Math.round(performance.now() - start) + " ms";
}
console.log("100,000 coaches:", addAtFront(100000));
console.log("1,000,000 coaches:", addAtFront(1000000));
Output (one run):
Engine -> S1 -> S2
100,000 coaches: 11 ms
1,000,000 coaches: 85 ms
prepend makes a new node whose next is the old head, and makes it the new head: two assignments, O(1), however long the list. Ten times more coaches than the array test, in a fraction of the time.
Inserting in the middle, and the null crash
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
const train = new Node("Engine", new Node("S1", new Node("S2")));
function show(head) {
const out = [];
for (let cur = head; cur !== null; cur = cur.next) out.push(cur.value);
console.log(out.join(" -> "));
}
function insertAfter(head, target, value) {
let cur = head;
while (cur.value !== target) cur = cur.next;
cur.next = new Node(value, cur.next);
}
insertAfter(train, "S1", "Pantry");
show(train);
insertAfter(train, "S9", "AC");
Output:
Engine -> S1 -> Pantry -> S2
main.js:15
while (cur.value !== target) cur = cur.next;
^
TypeError: Cannot read properties of null (reading 'value')
at insertAfter (main.js:15:14)
...
Why: there is no S9. The loop walked past the last node, cur became null, and null.value is an error. This is the most common linked list bug.
Order matters when you relink: cur.next = new Node(value, cur.next) reads the old cur.next first (to give the new node its next), then couples cur to the new node. If you first wrote cur.next = newNode and then newNode.next = cur.next, the new node would point to itself and the rest of the train would be lost.
The fix: keep walking only while cur is not null.
function insertAfter(head, target, value) {
let cur = head;
while (cur !== null && cur.value !== target) cur = cur.next;
if (cur === null) return false;
cur.next = new Node(value, cur.next);
return true;
}
insertAfter(train, "S1", "Pantry");
show(train);
console.log(insertAfter(train, "S9", "AC"));
show(train);
Output:
Engine -> S1 -> Pantry -> S2
false
Engine -> S1 -> Pantry -> S2
&& short-circuits: if cur !== null is false, cur.value is never read.
Array vs linked list
| Operation | Array | Linked list |
|---|---|---|
| read item i | O(1): jump to the index | O(n): walk i nodes |
| add/remove at the front | O(n): everything moves | O(1): one link |
| add at the end | O(1) | O(1) if you keep a tail pointer, else O(n) |
| insert/remove in the middle (once you're there) | O(n): items after it move | O(1): relink |
| find by value | O(n) | O(n) |
| memory | compact, cache friendly | an extra next per node |
In everyday JavaScript, arrays win most of the time. Linked lists matter when you add and remove at the front or in the middle a lot, and they are the building block of other structures (queues, LRU caches, hash table buckets) and a favourite in interviews.
Finding by name: a million contacts
const contacts = [];
for (let i = 0; i < 1000000; i++) contacts.push({ name: `User${i}`, phone: 9000000000 + i });
contacts.push({ name: "Neha", phone: 9876543210 });
let steps = 0;
const found = contacts.find((c) => {
steps++;
return c.name === "Neha";
});
console.log(found.phone, "steps:", steps);
Output:
9876543210 steps: 1000001
Every search by name is O(n). Arrays are fast with an index, so the idea is: turn the name into a number.
Hashing: the hostel rooms
| In a college hostel | In code |
|---|---|
| your roll number, e.g. 2041 | the key ("Neha") |
| the warden's rule: room = roll % 100 | a hash function: key → number |
| go straight to room 41 | the bucket index: jump there, O(1) |
| 2041 and 3041 both get room 41 | a collision: two keys, one bucket |
A hash function turns a key into a number, always the same number for the same key. The number (mod the table size) picks a bucket. A hash table is an array of buckets.
const SIZE = 10;
function hash(name) {
let sum = 0;
for (const ch of name) sum += ch.charCodeAt(0);
return sum % SIZE;
}
console.log("Neha ->", hash("Neha"));
console.log("Ravi ->", hash("Ravi"));
console.log("Asha ->", hash("Asha"));
console.log("Ahsa ->", hash("Ahsa"));
Output:
Neha -> 0
Ravi -> 2
Asha -> 1
Ahsa -> 1
charCodeAt(0) gives a character's number ("A" is 65, "a" is 97). Adding them up is a deliberately simple hash: "Asha" and "Ahsa" have the same letters, so the same sum, so the same bucket. Real hash functions mix the characters far better, so collisions are rare, but with more possible keys than buckets they can never be avoided.
A HashTable class with chaining
Chaining: every bucket holds a small list of [key, value] pairs, so colliding keys simply share a bucket.
class HashTable {
constructor(size = 10) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let sum = 0;
for (const ch of key) sum += ch.charCodeAt(0);
return sum % this.buckets.length;
}
set(key, value) {
const bucket = this.buckets[this.hash(key)];
const pair = bucket.find((p) => p[0] === key);
if (pair) pair[1] = value;
else bucket.push([key, value]);
}
get(key) {
const bucket = this.buckets[this.hash(key)];
const pair = bucket.find((p) => p[0] === key);
return pair ? pair[1] : undefined;
}
}
const phone = new HashTable();
phone.set("Neha", 9876543210);
phone.set("Asha", 9123456780);
phone.set("Ahsa", 9000011111);
console.log(phone.get("Asha"), phone.get("Ahsa"), phone.get("Ravi"));
console.log(phone.buckets[phone.hash("Asha")]);
Output:
9123456780 9000011111 undefined
[ [ 'Asha', 9123456780 ], [ 'Ahsa', 9000011111 ] ]
Array.from({ length: size }, () => []) makes size separate empty arrays. (new Array(size).fill([]) would put the same array in every slot, and every key would end up in one shared bucket.)
| Operation | Average | Worst case (every key in one bucket) |
|---|---|---|
set |
O(1) | O(n) |
get |
O(1) | O(n) |
The average stays O(1) when the hash spreads keys evenly and the table grows (real tables resize, roughly doubling, when they get too full; the ratio of keys to buckets is the load factor).
Map: the built-in hash map
JavaScript's Map (episode 21) is a hash table built into the engine: set, get, has, delete and size, all O(1) on average. Plain objects {} work as hash maps too, but they inherit keys from Object.prototype (episode 17), like constructor and toString.
const text = "the constructor of the house said the toString was fine";
const counts = {};
for (const word of text.split(" ")) {
counts[word] = (counts[word] || 0) + 1;
}
console.log(counts.the, counts.house);
console.log(counts.constructor);
console.log(counts.toString);
Output:
3 1
function Object() { [native code] }1
function toString() { [native code] }1
counts["constructor"] was not empty: it was the inherited Object function, so function + 1 glued "1" onto the function's text. With a Map:
const text = "the constructor of the house said the toString was fine";
const counts = new Map();
for (const word of text.split(" ")) {
counts.set(word, (counts.get(word) || 0) + 1);
}
console.log(counts.get("the"), counts.get("constructor"), counts.get("toString"));
console.log(counts.size, counts.has("roof"));
Output:
3 1 1
8 false
Plain object {} |
Map |
|
|---|---|---|
| inherited keys | yes (constructor, toString, ...) |
none |
| key types | strings and symbols only (1 becomes "1") |
anything: numbers, objects, ... |
| size | Object.keys(o).length (O(n)) |
m.size |
| order | mostly insertion order (integer-like keys first) | insertion order |
| best for | fixed records like { name, phone } |
lookups, counting, caches |
(Object.create(null) makes an object with no prototype, which avoids the inherited keys, but a Map is clearer.)
Array find vs Map get, a million contacts
const list = [];
const book = new Map();
for (let i = 0; i < 1000000; i++) {
list.push({ name: `User${i}`, phone: 9000000000 + i });
book.set(`User${i}`, 9000000000 + i);
}
let start = performance.now();
const a = list.find((c) => c.name === "User999999").phone;
console.log("array find:", a, (performance.now() - start).toFixed(3), "ms");
start = performance.now();
const b = book.get("User999999");
console.log("Map get: ", b, (performance.now() - start).toFixed(3), "ms");
Output (one run):
array find: 9000999999 17.855 ms
Map get: 9000999999 0.005 ms
Same answer, thousands of times faster: the array walks a million contacts, the Map jumps to one bucket.
Common mistakes (and what really happens)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
coaches.unshift(x) in a big loop |
100,000 items take hundreds of ms | every item moves: O(n²) | a linked list prepend, or push then reverse() once |
while (cur.value !== target) |
TypeError: Cannot read properties of null (reading 'value') |
walked past the last node | while (cur !== null && ...) |
newNode.next = cur.next after cur.next = newNode |
the node points to itself, the rest of the list is lost | read the old next too late |
create the node with the old next first |
list.get(i) on a linked list in a loop |
slow, O(n²) overall | no index: each get walks |
walk once with a for (cur...) loop, or use an array |
| counting with a plain object | function Object() { [native code] }1 |
inherited keys like constructor |
new Map() |
new Array(10).fill([]) for buckets |
every key lands in one shared bucket | fill puts the same array everywhere |
Array.from({ length: 10 }, () => []) |
| ignoring collisions | "Ahsa" overwrites "Asha" |
two keys, one bucket | chaining: a list per bucket |
Mini project: a complete LinkedList
head, a tail pointer (so append is O(1)), a size counter, and remove(value).
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
prepend(value) {
this.head = new Node(value, this.head);
if (this.tail === null) this.tail = this.head;
this.size++;
}
append(value) {
const node = new Node(value);
if (this.tail === null) this.head = node;
else this.tail.next = node;
this.tail = node;
this.size++;
}
remove(value) {
if (this.head === null) return false;
if (this.head.value === value) {
this.head = this.head.next;
if (this.head === null) this.tail = null;
this.size--;
return true;
}
let prev = this.head;
while (prev.next !== null && prev.next.value !== value) prev = prev.next;
if (prev.next === null) return false;
if (prev.next === this.tail) this.tail = prev;
prev.next = prev.next.next;
this.size--;
return true;
}
toString() {
const out = [];
for (let cur = this.head; cur !== null; cur = cur.next) out.push(cur.value);
return out.join(" -> ");
}
}
const train = new LinkedList();
train.append("S1");
train.append("S2");
train.prepend("Engine");
train.append("Guard");
console.log(train.toString(), "| size", train.size);
console.log(train.remove("S2"), train.toString());
console.log(train.remove("S9"), train.toString());
console.log(train.remove("Guard"), train.toString(), "| tail", train.tail.value);
Output:
Engine -> S1 -> S2 -> Guard | size 4
true Engine -> S1 -> Guard
false Engine -> S1 -> Guard
true Engine -> S1 | tail S1
To remove a node you stop at the node before it (prev) and skip over it: prev.next = prev.next.next. The removed node has no references left, so the garbage collector frees it.
Practice
1. Add has(key) and delete(key) to the HashTable.
Solution
class HashTable {
constructor(size = 10) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let sum = 0;
for (const ch of key) sum += ch.charCodeAt(0);
return sum % this.buckets.length;
}
set(key, value) {
const bucket = this.buckets[this.hash(key)];
const pair = bucket.find((p) => p[0] === key);
if (pair) pair[1] = value;
else bucket.push([key, value]);
}
get(key) {
const pair = this.buckets[this.hash(key)].find((p) => p[0] === key);
return pair ? pair[1] : undefined;
}
has(key) {
return this.buckets[this.hash(key)].some((p) => p[0] === key);
}
delete(key) {
const bucket = this.buckets[this.hash(key)];
const i = bucket.findIndex((p) => p[0] === key);
if (i === -1) return false;
bucket.splice(i, 1);
return true;
}
}
const phone = new HashTable();
phone.set("Asha", 9123456780);
phone.set("Ahsa", 9000011111);
console.log(phone.has("Asha"), phone.has("Ravi"));
console.log(phone.delete("Asha"), phone.delete("Asha"));
console.log(phone.get("Asha"), phone.get("Ahsa"));
Output:
true false
true false
undefined 9000011111
Deleting "Asha" leaves "Ahsa", which shares its bucket, untouched.
2. Find the first repeated word in a sentence, using a Map (or null if no word repeats).
Solution
function firstRepeated(sentence) {
const seen = new Map();
for (const word of sentence.toLowerCase().split(" ")) {
if (seen.has(word)) return word;
seen.set(word, true);
}
return null;
}
console.log(firstRepeated("the chai at the stall is the best"));
console.log(firstRepeated("every word here is new"));
Output:
the
null
One pass, O(n): each has and set is O(1) on average. (A Set works just as well here, since we only store "seen".)
3. Without running it: what is the Big O of reading the 500,000th item of a linked list with a million nodes? Of an array?
Solution
Linked list: O(n), you walk 499,999 next links from the head. Array: O(1), arr[499999] jumps straight there.
Quick quiz
let head = null;
for (const x of [1, 2, 3]) {
head = { value: x, next: head };
}
console.log(head.value, head.next.value);
A. 1 2 B. 3 2 C. 3 1 D. 2 3
Answer
B: 3 2. Each new node points to the old head and becomes the new head (that's prepend). After 1, 2, 3 the list is 3 -> 2 -> 1.
Interview questions
- When would you choose a linked list over an array? When you insert and remove at the front or in the middle often and rarely need index access.
- How do you reverse a singly linked list? Walk it with three references,
prev = null,cur = head,next: savenext = cur.next, setcur.next = prev, moveprev = cur,cur = next; at the endprevis the new head. O(n) time, O(1) space. - What is a hash collision, and how is it handled? Two keys that hash to the same bucket. Handled by chaining (a list per bucket) or open addressing (try the next free slot).
- Why is hash map lookup O(1) on average but O(n) in the worst case? If many keys land in one bucket, that bucket must be searched one by one.
- Map vs plain object for a lookup table? Map: no inherited keys, any key type,
size, made for frequent adds and deletes. Object: fixed-shape records. - What makes a good hash function? Fast, the same output for the same key, and it spreads keys evenly over the buckets.
- What is the load factor? Number of keys divided by number of buckets; when it gets high, tables resize to keep buckets short.
Glossary
| Term | Meaning | Example |
|---|---|---|
| node | a small object holding a value and link(s) to other nodes | { value: "S1", next: ... } |
| linked list | a chain of nodes, each pointing to the next | Engine → S1 → S2 |
next |
a node's reference to the following node | engine.next = s1 |
| pointer / reference | a value that refers to another object | next |
| head | the first node of a linked list | the engine |
| tail | the last node of a linked list | the guard's coach |
null |
"no object here"; the last node's next |
s2.next === null |
| traverse / walk | visit every node by following next |
for (let cur = head; cur !== null; cur = cur.next) |
| prepend | add at the front | train.prepend("Engine") |
| append | add at the end | train.append("Guard") |
| short-circuit | && stops as soon as the left side is false |
cur !== null && cur.value |
| key | what you look a value up by | "Neha" |
| hash function | turns a key into a number, always the same for the same key | sum of char codes % 10 |
| bucket | one slot of a hash table | buckets[1] |
| hash table / hash map | an array of buckets, indexed by the key's hash | HashTable, Map |
| collision | two keys with the same bucket | "Asha" and "Ahsa" |
| chaining | each bucket holds a list of pairs | [["Asha", ...], ["Ahsa", ...]] |
| load factor | keys ÷ buckets | 8 keys in 10 buckets = 0.8 |
charCodeAt(i) |
the number of the character at position i | "A".charCodeAt(0) is 65 |
Map |
JavaScript's built-in hash map | new Map() |
| prototype keys | properties every object inherits | constructor, toString |
Summary
unshiftmoves every item: O(n) each, O(n²) in a loop.- A linked list is nodes joined by
next, from the head tonull.prependis O(1); reading item i is O(n). Always checkcur !== nullwhile walking. - Searching an array by name is O(n). A hash function turns the key into a bucket number so you can jump there.
- Collisions always happen; chaining keeps a small list per bucket. Average O(1), worst case O(n).
- Use
Mapfor lookups and counting: plain objects inherit keys likeconstructor. - Next: trees and graphs, when a node points to more than one other node.