cf.completefrontend
LINKED LISTS · FOUNDATION

Linked list basics

Store items as a chain of nodes where each node holds a value and a link to the next node.

Time O(n)Space O(1)12 practice problemsStep-through picture

The idea

A linked list is a chain of small objects called nodes. Each node holds one value (val) and a link to the node after it (next). The last node's next is null, which means the chain ends there. You only keep the first node, called the head, and reach every other node by following next links.

An array keeps its items side by side in memory, so it can jump straight to item 500. A linked list can't jump: to reach the 500th node you follow 499 links. In return, adding or removing a node in the middle is cheap. You only change one or two links, and no other item has to move.

Most linked-list code walks the chain with a variable such as curr, and often keeps the node before it in prev, because changing the chain means changing the next link of the node before.

An everyday example

A scavenger hunt

In a scavenger hunt, each clue tells you where the next clue is hidden. You only know where the first clue is. To read the fifth clue you have to find clues one to four first. If the organizer wants to skip a clue, they don't move any hiding places: they rewrite the clue before it so it points past the skipped one.

How the example maps to the code
In the exampleIn the code
The first clue's hiding placehead
One clue carda node with val and next
"The next clue is under the bench"node.next
The last card says "you're done"next === null
Rewriting a clue to skip the next oneprev.next = curr.next

From the slow way to linked list basics

  1. Start with the obvious tool: an array. To remove every copy of a value from an array in place, you call splice each time you find one. But splice shifts every later item one slot to the left, so each removal can cost O(n), and removing many items costs O(n^2). Building a new filtered array avoids that, but it needs a second array as big as the first.
  2. The waste comes from one fact: an array keeps its items side by side, so a gap must be closed by moving items. If each item instead knew only where the next item lives, a gap would not need closing. You could skip an item by changing one link and leave every other item where it is. That is a linked list: nodes with a val and a next link.
  3. Skipping a node means changing the next of the node before it. So the walk keeps two variables: curr, the node being checked, and prev, the last node that stays. When curr must go, write prev.next = curr.next. When it stays, move prev up to it. Either way, curr steps to curr.next.
  4. One case still breaks the pattern: the first node has no node before it, so removing it would need its own branch, and removing several matches at the start would need a loop of its own. A placeholder node, dummy, placed in front of head gives every real node a node before it. That loop is the basic linked-list walk with a dummy node.

How it works

  1. Make a placeholder node, dummy, whose next is head. It gives even the first real node a node before it.
  2. Set prev to dummy and curr to head. prev is always the last node that stays in the list.
  3. While curr is not null, look at curr.val.
  4. To remove curr, link around it: prev.next = curr.next. prev stays where it is.
  5. To keep curr, move prev forward to curr.
  6. Either way, move curr to curr.next. When curr is null, return dummy.next, the new head.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class ListNode {
  2. constructor(val, next = null) {
  3. this.val = val;
  4. this.next = next;
  5. }
  6. }
  8. function removeValue(head, target) {
  9. const dummy = new ListNode(0, head);
  10. let prev = dummy;
  11. let curr = head;
  12. while (curr !== null) {
  13. if (curr.val === target) {
  14. prev.next = curr.next;
  15. } else {
  16. prev = curr;
  17. }
  18. curr = curr.next;
  19. }
  20. return dummy.next;
  21. }

How fast it is

TimeO(n)
Extra memoryO(1)

The loop visits each node once. It only keeps three references (dummy, prev, curr) no matter how long the list is, and it reuses the existing nodes.

  • Best caseO(n)

    A list with no matching node at all. Even then, the loop must look at all n nodes, because the very last one could match.

  • Average caseO(n)

    Matches spread through the list. Each loop does one comparison and at most one link change, whatever the answer.

  • Worst caseO(n)

    Every node matches, like 6 -> 6 -> 6. The loop still runs once per node; it just rewrites dummy.next each time.

Common mistakes

  • Returning head after removing nodes. If the first node was removed, head still points to it. Return dummy.next.
  • Moving prev forward after a removal. Then prev points to a removed node, and the next removal changes a node that is no longer in the list. Only move prev when the node stays.
  • Reading curr.next.val without checking that curr.next isn't null. Check before you follow a link.
  • Changing curr.next before saving it, which cuts off the rest of the list. Save it in a variable first.

When to use it

Look for these clues in a problem:

  • The input is the head of a list of ListNodes with val and next.
  • The task asks you to remove, insert, or regroup nodes, often in place without making new nodes.
  • The answer is a list, so you must return its new first node.
  • Items are added and removed often in the middle of a sequence, and you already hold the node where the change happens.

Check yourself

Answer each one in your head first, then open it.

Why does prev stay put after a removal?

Because the removed node is no longer in the list, so the last node that stays is still prev. If prev moved to the removed node, the next removal would change a link in a node nobody can reach.

If a list has n nodes and k of them match, how many next links does the loop write?

Exactly k, one per removal. Matches that sit next to each other all write the same link, prev.next, again and again.

What does the function return if every node matches?

null. dummy.next is overwritten on every loop and finally set to the last node's next, which is null.

Why is reading curr.next after a removal still safe?

Removing curr only changes prev.next. The removed node's own next still points to the rest of the list, so curr = curr.next steps to the right node.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 12 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule, true at the top of every loop: following next links from dummy to prev gives exactly the nodes before curr that do not match target, in their original order, and prev.next is curr. At the start, prev is dummy, no nodes have been checked yet, and dummy.next is head, so the rule holds.

Each branch keeps the rule. If curr matches, prev.next = curr.next drops it and then curr = curr.next moves on, so prev.next is again curr. If curr stays, prev = curr adds it to the kept part, and since its next was not changed, prev.next is the new curr after the step. No link other than prev.next is ever written.

The loop ends because curr moves one node forward every time, and a list without a cycle has an end. When curr is null, the rule says the chain from dummy holds every non-matching node in order, and prev.next is null, so the chain is closed. Its first real node is dummy.next, which is exactly what the function returns.

Going deeper

3 more ideas

Why a dummy node saves special cases

Removing a node means changing the next of the node before it. The head has no node before it, so without help you would need a separate branch for "remove the head". The dummy node sits in front of the head, so every real node has a node before it and one rule handles all of them. At the end, dummy.next is the real head, even if the old head was removed.

What each operation costs

Walking the whole list is O(n) because you visit each node once. Finding the node at position k is O(k), since you can't jump. Inserting or removing next to a node you already hold is O(1): you change one or two links and nothing else moves. The walk itself needs only a few variables, so the extra space is O(1).

Losing the rest of the list

A node is only reachable through the link before it. If you overwrite curr.next before saving it, the nodes after curr are gone. When code changes a next link, first save what it pointed to in a variable such as next, then rewire.

Work it by hand

Every step in a table, with why

Remove every 6 from a five-node list where the first two nodes and the last node all hold 6.

head = 6 -> 6 -> 2 -> 9 -> 6, target = 6

Stepprevcurrcurr.val === targetList from dummy.nextWhat happensWhy
1dummy6 (first)true6 -> 2 -> 9 -> 6dummy.next = curr.nextThe head itself matches. Because prev is dummy, removing the head is the same one line as any other removal. prev stays at dummy.
2dummy6 (second)true2 -> 9 -> 6dummy.next = curr.nextTwo matches in a row. prev did not move after the first removal, so it still sits right before the new curr and can skip it too.
3dummy2false2 -> 9 -> 6Keep: prev = 22 stays, so it becomes the last node that stays. Only now does prev move.
429false2 -> 9 -> 6Keep: prev = 99 stays too, and prev moves up to it.
596 (last)true2 -> 99.next = nullThe last node matches. curr.next is null, so prev.next = curr.next makes 9 the new end of the list.
69null-2 -> 9curr is null: stopcurr stepped past the end, so the loop ends and the function returns dummy.next.

It returns the node 2, giving 2 -> 9, after 5 loops and 3 link changes. Returning head instead would be wrong: head still points at the first 6, whose own next was never changed, so it would show 6 -> 6 -> 2 -> 9.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Linked list basicsO(n)O(1)The data is already a linked list, or you often add and remove items next to a node you already hold.
Array filter into a new arrayO(n)O(n)The data is an array and you can afford a copy. It is the clearest code and keeps the original untouched.
Array splice in a loopO(n²)O(1)Only for small arrays that must change in place. Each splice shifts every later item, so many removals get slow.

Extra memory: O(1): three references, dummy, prev, and curr, whatever the length. The removed nodes are not copied; once nothing points to them, JavaScript's garbage collector frees them.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Linked list basics and the other approaches, on a scale where each line up is 10 times more steps.
  • Linked list basics, Array filter into a new array O(n)
  • Array splice in a loop O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Linked list basics101,0001 million
Array filter into a new array101,0001 million
Array splice in a loop1001 million1 trillion

Inputs that need care

6 tricky inputs
An empty list: head = null
curr starts as null, so the loop never runs and the function returns dummy.next, which is null. No special check is needed.
One node that matches: head = 6, target = 6
The only loop sets dummy.next = null, so the function returns null, an empty list.
Every node matches: 4 -> 4 -> 4, target = 4
prev never leaves dummy. Each loop writes dummy.next again, and the answer is null.
No node matches
prev simply follows curr to the end and no link is written. The function returns the same head it was given.
A list that loops back on itself
curr never becomes null, so the loop never ends. This walk assumes a list with an end; check for a cycle first with Floyd's method if the data can be broken.
target = "6" while the nodes hold the number 6
=== compares type as well as value, so nothing matches and nothing is removed. Convert the target to the same type before calling.

Variations and follow-ups

Twists interviewers add

Insert into a sorted list

Walk with prev and curr until curr is null or curr.val is bigger than the new value, then link the new node between them with prev.next = node and node.next = curr. The dummy node makes inserting before the first node work with the same two lines.

Delete a node when you only hold that node

Without head you can't reach the node before it. Instead, copy the next node's value into this node and skip the next node: node.val = node.next.val; node.next = node.next.next. It doesn't work for the last node, which has no next node to copy from.

Recursive removal

head.next = removeValue(head.next, target), then return head.next if head matches, or head if not. It is short and needs no dummy, but it uses one stack frame per node, so it is O(n) space and can overflow on very long lists.

Remove duplicates from a sorted list

In a sorted list, copies of a value sit next to each other. Keep curr and, while curr.next exists and curr.next.val === curr.val, skip it with curr.next = curr.next.next. It is the same skip-one-link move, with the node before always being curr itself.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from the signature: the input is head of a list of ListNodes, and the task says remove, insert, or return the new head. Reach for a dummy node right away and say why: the head should not need its own branch.
  • Explain the two pointers out loud: "prev is the last node that stays, curr is the node I'm checking." Then the rule "only move prev when the node stays" follows on its own.
  • Test by hand on three tiny lists before saying you're done: an empty list, a list where the head matches, and a list where two matches sit next to each other. Most bugs show up in the last one.
  • Expect the follow-up "can you do it without the dummy node?". Yes: first loop while (head !== null && head.val === target) head = head.next, then run the normal walk from the new head. It works, but it is two loops instead of one rule.

Where frontend code uses it

The same idea in real UI code
  • The DOM links nodes to each other: every node has nextSibling and previousSibling, and you can walk an element's children with firstChild and nextSibling just like a linked list.
  • React's Fiber tree links each fiber to its first child with child and to the next fiber at the same level with sibling, so React can walk the tree with plain links and pause between steps.
  • React stores the hooks of a component as a linked list: each hook object has a next link to the following hook, which is why hooks must run in the same order on every render.

Related algorithms