JS-201 · Lesson 3 of 12 · 27 min
Linked lists
▶ Video coming soon A video version of this lesson is on the way.
Lucy Tran has a problem with the grocery program's waitlist. Families who cannot get a pick-up slot are added to the end of a list, the family at the front is offered the next free slot, and families who find help elsewhere can leave from anywhere in the list. Since the pilot, the waitlist has been an array, and the dashboard calls shift() whenever a slot opens. With 40 families that is harmless. Gareth uses it at the third session, on Tuesday, September 14, to introduce the first data structure that JavaScript does not provide: the linked list.
"You will not often write a linked list in production JavaScript," he says. "Arrays are usually faster. But the idea of objects pointing to other objects is behind queues, trees, graphs and half the structures in this course, and once you can draw it you can build all of them."
Nodes and references
A linked list stores a sequence as a chain of small objects called nodes. Each node holds one value and a reference, usually called next, to the node after it. The last node's next is null, which marks the end. The list itself only needs to remember where the chain starts, in a reference called the head. Unlike an array, the nodes do not sit side by side in memory, and there are no indexes: the only way to reach the third node is to start at the head and follow next twice.
In JavaScript, a node is an ordinary object, and next holds a reference to another object, exactly as a variable can hold a reference to an array. Nothing is copied when you link nodes together; each next points to an object that already exists. The example below builds a three-node chain by hand and walks along it.
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
const chi = new Node('Chi family');
const ben = new Node('Ben family', chi);
const ana = new Node('Ana family', ben);
let head = ana;
let count = 0;
for (let n = head; n !== null; n = n.next) {
count++;
console.log(count + '.', n.value);
}
console.log('last node next:', chi.next);1. Ana family 2. Ben family 3. Chi family last node next: null
What this code does
Each Node holds a value and a reference to the next node, so building the chain from the end means each new node can point at one that already exists. The for loop starts at head and keeps following next until it reaches null. Counting the nodes requires visiting every one, which is O(n).
Walking the list is called traversal, and the loop shape for (let n = head; n !== null; n = n.next) appears in almost every linked list function. Many bugs come from losing the head: if you move head itself along the list, the nodes you pass are no longer reachable, and once nothing refers to them the engine's garbage collector frees them. Always walk with a separate variable.
A LinkedList class
Real code wraps the nodes in a class that keeps the head, a tail reference to the last node, and a size. The tail makes adding to the end O(1): without it, append would have to walk the whole list to find the last node. Keeping size as a field makes the length O(1) as well, as long as every method that adds or removes updates it.
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) { // O(1)
this.head = new Node(value, this.head);
if (this.tail === null) this.tail = this.head;
this.size++;
}
append(value) { // O(1), thanks to tail
const node = new Node(value);
if (this.tail === null) this.head = node;
else this.tail.next = node;
this.tail = node;
this.size++;
}
removeFirst() { // O(1)
if (this.head === null) return undefined;
const value = this.head.value;
this.head = this.head.next;
if (this.head === null) this.tail = null;
this.size--;
return value;
}
*[Symbol.iterator]() { // lets for...of and spread walk the list
for (let n = this.head; n !== null; n = n.next) yield n.value;
}
}
const waitlist = new LinkedList();
waitlist.append('Okafor');
waitlist.append('Nguyen');
waitlist.append('Haddad');
waitlist.prepend('Larsen'); // urgent case, moved to the front
console.log([...waitlist], 'size', waitlist.size);
console.log('offered a slot:', waitlist.removeFirst());
console.log('offered a slot:', waitlist.removeFirst());
console.log([...waitlist], 'size', waitlist.size, 'tail', waitlist.tail.value);[ "Larsen", "Okafor", "Nguyen", "Haddad" ] size 4 offered a slot: Larsen offered a slot: Okafor [ "Nguyen", "Haddad" ] size 2 tail Haddad
What this code does
append links a new node after the tail and moves tail to it, while prepend makes a new node that points at the old head. removeFirst moves head one node along and returns the old first value, and it resets tail when the list becomes empty. Each of these changes a fixed number of references, so each is O(1), and the generator method lets the spread operator list the values.
Look closely at the special cases. Adding to an empty list must set both head and tail. Removing the last remaining node must set both back to null. Most linked list bugs are in exactly these cases, so test every method on an empty list, a list of one and a list of several.
| Operation | Linked list | Array |
|---|---|---|
| Add at the front | O(1) | O(n) with unshift |
| Remove from the front | O(1) | O(n) with shift |
| Add at the end | O(1) with a tail reference | O(1) amortized with push |
| Read item number i | O(n): walk from the head | O(1) |
| Find a value | O(n) | O(n) |
| Remove a node you already hold | O(1) if doubly linked | O(n) with splice |
| Memory per item | A whole object with a next field | One slot |
Finding and removing
Finding a value in a linked list is a linear search, like indexOf on an array. Removing a value from the middle needs one extra idea: to unlink a node you have to change the next of the node before it, so the search keeps a reference to the previous node as it goes. Once the node is found, removal itself is just one reference change, but finding it took O(n).
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) { // O(1)
this.head = new Node(value, this.head);
if (this.tail === null) this.tail = this.head;
this.size++;
}
append(value) { // O(1), thanks to tail
const node = new Node(value);
if (this.tail === null) this.head = node;
else this.tail.next = node;
this.tail = node;
this.size++;
}
removeFirst() { // O(1)
if (this.head === null) return undefined;
const value = this.head.value;
this.head = this.head.next;
if (this.head === null) this.tail = null;
this.size--;
return value;
}
*[Symbol.iterator]() { // lets for...of and spread walk the list
for (let n = this.head; n !== null; n = n.next) yield n.value;
}
}
LinkedList.prototype.remove = function (value) {
let prev = null, steps = 0;
for (let n = this.head; n !== null; prev = n, n = n.next) {
steps++;
if (n.value === value) {
if (prev === null) this.head = n.next; else prev.next = n.next;
if (n === this.tail) this.tail = prev;
this.size--;
return steps;
}
}
return -1;
};
const waitlist = new LinkedList();
for (const f of ['Okafor', 'Nguyen', 'Haddad', 'Silva', 'Moreau']) waitlist.append(f);
console.log('removed Haddad after', waitlist.remove('Haddad'), 'steps');
console.log('removed Moreau after', waitlist.remove('Moreau'), 'steps');
console.log([...waitlist], 'tail', waitlist.tail.value, 'size', waitlist.size);
console.log('missing family:', waitlist.remove('Tanaka'));removed Haddad after 3 steps removed Moreau after 4 steps [ "Okafor", "Nguyen", "Silva" ] tail Silva size 3 missing family: -1
What this code does
remove walks the list while remembering the previous node. When it finds the value it points the previous node's next past the found node, or moves head if the found node was first, and moves tail back if the found node was last. The step counts show that removal costs as much as the search that finds the node.
Reversing a list
Reversing a linked list in place is a classic exercise because it needs exactly the right order of reference changes. Walk the list once, and at each node point its next back at the previous node instead of forward. Three variables are needed: the previous node, the current node and the next node, saved before the link is changed so that the rest of the list is not lost.
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) { // O(1)
this.head = new Node(value, this.head);
if (this.tail === null) this.tail = this.head;
this.size++;
}
append(value) { // O(1), thanks to tail
const node = new Node(value);
if (this.tail === null) this.head = node;
else this.tail.next = node;
this.tail = node;
this.size++;
}
removeFirst() { // O(1)
if (this.head === null) return undefined;
const value = this.head.value;
this.head = this.head.next;
if (this.head === null) this.tail = null;
this.size--;
return value;
}
*[Symbol.iterator]() { // lets for...of and spread walk the list
for (let n = this.head; n !== null; n = n.next) yield n.value;
}
}
function reverse(list) {
let prev = null, current = list.head;
list.tail = list.head;
while (current !== null) {
const next = current.next; // save the rest of the list
current.next = prev; // turn this link around
prev = current; // move both pointers along
current = next;
}
list.head = prev;
}
const route = new LinkedList();
for (const stop of ['Hub', 'Library', 'School', 'Church']) route.append(stop);
reverse(route);
console.log([...route], '| head', route.head.value, '| tail', route.tail.value);[ "Church", "School", "Library", "Hub" ] | head Church | tail Hub
What this code does
reverse visits each node once and turns its next reference to point at the node before it. It saves current.next first, because changing current.next would otherwise cut it off from the rest of the list. At the end prev is the old last node, which becomes the new head, so the reversal is O(n) time and O(1) extra space.
Doubly linked lists
In a doubly linked list, each node also has a prev reference to the node before it. The extra field costs memory and every insertion has to set two references instead of one, but it buys two things. The list can be walked backwards from the tail, and a node can be removed in O(1) if you already hold a reference to it, because its neighbours can be reached directly through prev and next without searching.
That second property is why doubly linked lists sit inside many caches. A least recently used cache, or LRU cache, keeps a fixed number of recent results and throws away the one used longest ago when it is full. Classic implementations combine a Map from key to node, for O(1) lookup, with a doubly linked list in order of use, for O(1) moving and removal. In JavaScript, a Map already keeps keys in insertion order, so a small LRU cache can use that order instead of a hand-made list.
class LruCache {
constructor(limit) { this.limit = limit; this.map = new Map(); }
get(key) {
if (!this.map.has(key)) return undefined;
const value = this.map.get(key);
this.map.delete(key); // move the key to the newest end
this.map.set(key, value);
return value;
}
set(key, value) {
this.map.delete(key);
this.map.set(key, value);
if (this.map.size > this.limit) {
const oldest = this.map.keys().next().value; // first key = least recently used
this.map.delete(oldest);
}
}
}
const weather = new LruCache(2);
weather.set('Mon', 'Sunny');
weather.set('Tue', 'Rain');
weather.get('Mon'); // Mon is now the most recent
weather.set('Wed', 'Cloudy'); // evicts Tue
console.log([...weather.map.keys()]);[ "Mon", "Wed" ]
What this code does
The cache keeps its entries in a Map, whose keys stay in insertion order. Reading a key deletes it and sets it again, which moves it to the newest end, so the first key in the Map is always the least recently used. When the Map grows past the limit, that first key is removed, and every operation is O(1) on average.
The Map version works because deleting and re-adding a Map key is O(1) on average, which is effectively the doubly linked list built into the engine's Map. In other languages, and in interviews, expect to build the list yourself. The idea is the same: a fast way to find an entry and a fast way to move it to the front of the line.
Two pointers on a list
Some linked list problems are solved by walking two references along the list at different speeds. To find the middle node in one pass, move one reference one step at a time and another two steps at a time. When the fast one reaches the end, the slow one is in the middle. The same trick detects a cycle, a list whose last node points back into the list by mistake so that a normal traversal never ends: if the fast reference ever lands on the same node as the slow one, the list has a loop. This is known as Floyd's cycle-finding algorithm, or the tortoise and the hare.
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) head = new Node(values[i], head);
return head;
}
function hasCycle(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
const good = build(['A', 'B', 'C', 'D', 'E']);
console.log('good list has a cycle?', hasCycle(good));
const bad = build(['A', 'B', 'C', 'D', 'E']);
bad.next.next.next.next.next = bad.next; // E points back to B by mistake
console.log('bad list has a cycle?', hasCycle(bad));good list has a cycle? false bad list has a cycle? true
What this code does
hasCycle moves slow one node at a time and fast two nodes at a time. In a list that ends, fast reaches null and the function returns false. In a list with a loop, fast keeps going round and must eventually land on the same node as slow, so the check uses O(n) time and only two variables of extra space.
When to use a linked list in JavaScript
On paper the linked list wins at the front and the array wins at random access. In practice, arrays in JavaScript are faster than linked lists for most jobs, even some that the Big-O table says a list should win. Array elements sit together in memory, so the processor's cache loads many of them at once, while each list node is a separate object that may be anywhere. Each node also carries the overhead of an object. Big-O describes how cost grows; it does not include these constant factors.
Use a linked list, or a structure built on the same idea, when you need many insertions and removals at the front or in the middle at positions you already hold references to, and rarely need item number i. That describes queues, the subject of the next lesson, and the internals of caches, editors and memory allocators. For the waitlist, Gareth suggests that the dashboard keep its array for now: with 40 families, the clearest code wins, and Lesson 4 gives a queue that is fast at the front without giving up the array.
Try it yourself
Count the nodes
Complete countNodes(head) so that it returns the number of nodes in a chain that starts at head. An empty chain is null and has 0 nodes.
Use a separate variable to walk the chain.
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
function countNodes(head) {
return 0;
}
const list = new Node('A', new Node('B', new Node('C')));
console.log(countNodes(list));
console.log(countNodes(null));
console.log(countNodes(new Node('only')));Try it yourself
Find the middle
Complete middle(head) so that it returns the value of the middle node, using the slow and fast pointer technique in one pass. When the list has an even number of nodes, return the second of the two middle values.
Assume the list has at least one node.
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) head = new Node(values[i], head);
return head;
}
function middle(head) {
return head.value;
}
console.log(middle(build(['Hub', 'Library', 'School', 'Church', 'Rink'])));
console.log(middle(build(['Hub', 'Library', 'School', 'Church'])));
console.log(middle(build(['Hub'])));Try it yourself
Insert after a value
Complete insertAfter(head, target, value) so that it adds a new node holding value straight after the first node whose value is target, and returns true. If target is not found, change nothing and return false.
The program prints the list after two insertions.
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
function insertAfter(head, target, value) {
return false;
}
function show(head) { const out = []; for (let n = head; n; n = n.next) out.push(n.value); return out.join(' -> '); }
const route = new Node('Hub', new Node('School', new Node('Church')));
console.log(insertAfter(route, 'Hub', 'Library'));
console.log(insertAfter(route, 'Rink', 'Clinic'));
console.log(show(route));Common mistakes
MistakeMoving head along the list to traverse it.
InsteadWalk with a separate variable; moving head loses the nodes before it.
MistakeForgetting the tail when the list becomes empty or a last node is removed.
InsteadUpdate head, tail and size together, and test with empty, one-item and multi-item lists.
MistakeChanging current.next before saving it while reversing.
InsteadSave const next = current.next first, or the rest of the list is cut off.
MistakeAssuming a linked list is faster than an array because the Big-O table says so.
InsteadArrays have better memory locality; measure, and prefer arrays unless the front or middle operations dominate.
MistakeReading item i of a list in a loop, as with an array.
InsteadEach read walks from the head, so a loop that reads items 0 to n is O(n²). Traverse once instead.
Summary and key terms
- A linked list stores a sequence as nodes, each holding a value and a reference to the next node, with null marking the end.
- The list keeps a head reference, and usually a tail and a size.
- Traversal follows next from the head and is O(n), and there is no O(1) access by index.
- Adding or removing at the front is O(1), and adding at the end is O(1) with a tail reference.
- Removing a value requires finding it first, keeping a reference to the previous node, so it is O(n).
- Reversal turns each next around in one pass, saving the rest of the list first.
- A doubly linked list adds prev references, allowing backward traversal and O(1) removal of a node you already hold, which is how classic LRU caches work.
- In JavaScript a Map's insertion order gives a simple LRU cache.
- Slow and fast pointers find the middle and detect cycles.
- Arrays usually beat linked lists in practice because of memory locality.
- linked list
- A sequence stored as nodes, each referring to the next.
- node
- One element of a linked structure, holding a value and references to other nodes.
- head
- The reference to the first node of a linked list.
- tail
- The reference to the last node of a linked list.
- traversal
- Visiting every node of a structure, one after another.
- doubly linked list
- A linked list whose nodes refer to both the next and the previous node.
- LRU cache
- A cache of fixed size that discards the least recently used entry when it is full.
- cycle
- A chain of references that loops back on itself, so traversal never reaches null.
- garbage collection
- The engine's automatic freeing of objects that nothing refers to any more.
- memory locality
- How close together related data sits in memory, which affects how fast the processor can read it.
Practice problems
Work each problem on paper first, then reveal the answer to check.
Why does append need a tail reference to be O(1)?
Show answer
Without it, append must walk the whole list to find the last node.
What must change when removing the only node in a list?
Show answer
head and tail both become null and size becomes 0.
What is the cost of reading the 500th value of a linked list?
Show answer
O(n): the code must follow next from the head 499 times.
What does Floyd's algorithm detect, and how much extra memory does it need?
Show answer
A cycle in a linked list, using two pointer variables, so O(1) extra space.
How does the Map-based LRU cache know which key is least recently used?
Show answer
Every use deletes and re-adds the key, so the first key in insertion order is the least recently used.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.