What is a linked list?
A linked list stores a sequence of values in separate pieces called nodes. Each node holds exactly two things: one value (
val) and a pointer to the next node (next). Unlike an array, the values are not glued together in one block of memory — the chain of pointers is the only thing holding the sequence in order, and the last node's pointer is null (the end).In this lesson you'll learn how a chain of nodes is built, how to walk it, and how the list's one superpower — inserting and removing without shifting anything — actually works.
Why would anyone un-glue an array? You're building a music player. The queue plays in order —
3 → 7 → 1 → 9 — but the user constantly inserts a song in the middle and removes ones they're bored of. In an array, every insert or delete near the front forces every later song to shift over, all day long. In a linked list, inserting between two songs just rewires two pointers — nothing moves.It's a treasure hunt: each clue holds a bit of treasure and directions to the next clue. You hold onto the head (the first node) and follow
next until you hit null. The price of this flexibility: there is no jumping to "position 5" — you must walk there from the head, one pointer at a time.3→
7→
1→
9∅
∅
Quick check
Reaching the 5th node of a linked list requires…
Answer it in the interactive lesson to keep your progress.
The core operations: build a chain, then walk it
Everything is built from one tiny piece: a node — an object with just
val and next. You create one with new ListNode(value) and link two nodes by setting .next. Keep a reference to the first node — the head — because it is your only way back into the list.With a chain built, the only way through it is the walk: start at the head and follow
.next until you fall off the end. This one move — while (curr) { …; curr = curr.next } — is the backbone of almost every list algorithm.Trace the walk on 3 → 7 → 1 → 9
| step | curr points at | collected so far |
|---|---|---|
| 1 | 3 | [3] |
| 2 | 7 | [3, 7] |
| 3 | 1 | [3, 7, 1] |
| 4 | 9 | [3, 7, 1, 9] |
| 5 | null | done — the walk ends |
Now the same walk on something real — the music player from the intro, with the songs named this time. Four songs where each one only knows which song comes next: Dawn plays, then hands over to Drive, then Echo, then Coda — whose "next" is nothing, so the music stops. Then the good part: add Intro as the new opener. Point Intro's "next" at Dawn, and declare Intro the start — two pointer moves, and not a single song shifted anywhere. Watch it below, then read the same two moves as code. (
buildList in the snippets is a course-provided helper that turns an array like [3, 7, 1, 9] into real linked nodes, so the examples stay short.)Building and Walking a List in JavaScript
This section has a step-by-step animation in the interactive lesson.
const a = new ListNode(1); // each node holds a value...
const b = new ListNode(2);
const c = new ListNode(3);
a.next = b; // ...and a link to the next node
b.next = c; // the chain is now 1 -> 2 -> 3
console.log(a.val, a.next.val, a.next.next.val); // 1 2 3
console.log(c.next); // null (c is the tail)
function printVals(head) {
const out = [];
let curr = head; // start at the head
while (curr) { // stop once we step past the tail (null)
out.push(curr.val); // read this node's value
curr = curr.next; // follow the pointer to the next node
}
return out;
}
console.log(printVals(buildList([3, 7, 1, 9]))); // [3,7,1,9]Quick check
The walk `while (curr) { curr = curr.next }` stops when…
Answer it in the interactive lesson to keep your progress.
Your first list problem: find a value
Searching is the same walk with a question at each stop: is this the node I want? Because there's no index, you compare values one node at a time until you match — or run off the end and report "not here".
The steps
- Walk from the head with a position counter
i. - At each node, check
curr.val === target; if it matches, returni. - Otherwise step forward and add one to
i. - If the walk ends, the value isn't in the list — return
-1.
Trace it — find 1 in 3 → 7 → 1 → 9
| node | is it 1? | action |
|---|---|---|
3 | no | step on, i = 1 |
7 | no | step on, i = 2 |
1 | yes | return position 2 |
Finding a Value in JavaScript
function indexOfVal(head, target) {
let i = 0, curr = head;
while (curr) {
if (curr.val === target) return i; // found it → its position
i++;
curr = curr.next;
}
return -1; // walked off the end → not here
}
const nums = buildList([3, 7, 1, 9]);
console.log(indexOfVal(nums, 1)); // 2
console.log(indexOfVal(nums, 8)); // -1Quick check
Predict: finding 9 (the LAST value) in 3 → 7 → 1 → 9 takes how many value checks?
Answer it in the interactive lesson to keep your progress.
Pointer surgery: insert and delete
Here is the payoff for all that walking — changing the list never shifts anything. Three moves cover it:
Insert at the head — the superpower,
O(1). Make a new node, point its .next at the current head, and the new node is the head. Two pointer writes, no matter how long the list is. (You watched this in the playlist animation — "Intro" became the opener without a single song moving.)Insert at the tail —
O(n) to get there. A singly linked list has no shortcut to its last node, so walk until curr.next is null, then hang the new node on with one write. The walk is where all the cost lives.Delete a value — rewire around it. Find the node just before the target, then point its
.next at the node after the target. Trace it — delete 1 from 3 → 7 → 1 → 9:| step | action | list |
|---|---|---|
| 1 | walk to 7, the node before 1 | 3 → 7 → 1 → 9 |
| 2 | point 7.next past 1, straight at 9 | 3 → 7 → 9 |
The deleted node is never touched — it is simply routed around and left behind.
Insert and Delete in JavaScript
function insertHead(head, val) {
const node = new ListNode(val); // the new front node
node.next = head; // point it at the old head
return node; // it becomes the new head
}
function insertTail(head, val) {
const node = new ListNode(val);
if (!head) return node; // empty list → the node is the list
let curr = head;
while (curr.next) curr = curr.next; // walk to the tail (O(n))
curr.next = node; // link the new node on
return head;
}
function deleteVal(head, target) {
if (!head) return null;
if (head.val === target) return head.next; // dropping the head itself
let curr = head;
while (curr.next && curr.next.val !== target) curr = curr.next;
if (curr.next) curr.next = curr.next.next; // skip over the target node
return head;
}
console.log(printVals(insertHead(buildList([7, 1, 9]), 3))); // [3,7,1,9]
console.log(printVals(insertTail(buildList([3, 7, 1]), 9))); // [3,7,1,9]
console.log(printVals(deleteVal(buildList([3, 7, 1, 9]), 1))); // [3,7,9]Quick check
To delete 1 from 3 → 7 → 1 → 9, the walk must stop at…
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Losing the head. The head is your only entry point — reassign it while walking without saving it and the whole list is gone. Always walk with a separate
curr. - Null dereference. Reading
curr.next.valwhencurr.nextisnullthrows. Guard the end of the chain before you step (while (curr.next)). - Rewiring in the wrong order. When you insert or delete, set the new node's
.nextbefore you overwrite the old link — otherwise you cut off the rest of the list. Save what you need first. (Inserting at the head,head = nodebeforenode.next = headpoints the new node at itself — the old list floats away.)
That third pitfall is why reversing a list — flipping every
.next to point backwards — is the interview's favorite pointer-surgery test: every single step must save next before flipping the arrow. The See it step animates it flip by flip.Quick check
If you overwrite a node's `.next` before saving it, you…
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, a linked list is the mirror image of an array:
| operation | cost | why |
|---|---|---|
| insert / remove at the head | O(1) | just relink — nothing shifts |
read node.val, step node.next | O(1) | one pointer hop |
| find or reach the k-th node | O(n) | no index — you must walk |
| insert at the tail | O(n) | walk to the end first |
| walk the whole list | O(n) time, O(1) space | visit each node once |
Storing
n nodes takes O(n) space.One honest caveat: even where both cost
O(n), scanning an array is usually faster in practice — its values sit side by side in memory, so the CPU cache pulls in the next few for free, while list nodes are scattered wherever they were allocated. Linked lists win on reshaping, not on raw scanning.And one upgrade worth knowing by name: the doubly linked list. Each node also keeps a
prev pointer, so you can walk backwards and delete a node you're standing on without hunting for its predecessor — at the price of one extra pointer per node to keep in sync on every insert and delete. Your browser's back/forward history and LRU caches are exactly this shape.Key takeaways:
- A node is
{ val, next }; the head is your only way in, and the tail's.nextisnull. - Front inserts/removes are
O(1); anything by position isO(n)— the opposite trade-off from an array. - Every operation is a walk plus a little pointer surgery; save
.nextbefore you overwrite it.
The See it step animates all seven moves one by one — the walk, find, both inserts, delete, the full reverse, and fast & slow pointers (two markers, one moving twice as fast — how you find the middle or catch a cycle in one pass). With the basics down, the famous list problems are each just the walk plus one idea, and each returns as its own lesson later: reverse a list (this topic's Level-2 challenge), detect a cycle, and merge two sorted lists. Next up in order: Binary Search — the first algorithm that beats a plain
O(n) scan by halving the search each step.