Skip to content

level 5 · Linear structures

Linked List

No shelves, no addresses — just a chain of notes saying 'next'.

11 min 75 XP

what is it

Start here

An array is a row of boxes side by side. A linked list is nothing like that. Each node sits wherever it likes in memory, and holds a note saying where the *next* one is. Follow the notes and you walk the whole list.

This has one big cost: there are no indexes. You cannot jump to the 500th node — you have to walk there from the front, one note at a time. Everything an array does instantly, a linked list does slowly.

So why bother? Because inserting and deleting cost nothing once you're standing in the right place. No shuffling, no shifting, no 'everyone move down one'. You just re-aim one arrow. An array insert can move a million items; a linked list insert moves zero.

That is the trade, and it's the first real lesson in data structures: there is no best structure, only the right one for what you're about to do.

real-life analogy

Picture it

A treasure hunt

Each clue tells you where the next clue is. There's no map and no shortcut — to get to clue 8, you must follow clues 1 through 7. But adding a new clue in the middle is trivial: rewrite one note to point at your new clue, and point your new clue at whatever came next.

interactive visualization

Watch it run

Each value is added at the tail — watch the walk get longer every time.

  1. NULL

A linked list is a treasure hunt. Each node holds a value and a note saying where the next one is. There are no numbered shelves — the only way in is through the front door.

step 01/26

  • comparing
  • moving
  • in final place
  • found it
1class Node {
2 constructor(value) {
3 this.value = value;
4 this.next = null;
5 }
6}
7
8function insertAtTail(head, value) {
9 const node = new Node(value);
10 if (head === null) return node;
11 let cur = head;
12 while (cur.next !== null) {
13 cur = cur.next;
14 }
15 cur.next = node;
16 return head;
17}
18
19function deleteValue(head, value) {
20 if (head === null) return null;
21 if (head.value === value) return head.next;
22 let cur = head;
23 while (cur.next !== null && cur.next.value !== value) {
24 cur = cur.next;
25 }
26 if (cur.next !== null) cur.next = cur.next.next;
27 return head;
28}

variables right now

length
0
comparisons 0moves 0

the dry run · every step, in words

26 steps

complexity

What it costs

best case
O(1) insert at head
average
O(n) to find
worst case
O(n) to reach the tail
extra memory
O(n)

Reading the 500th item costs 500 steps, where an array costs 1. But inserting or deleting once you're there costs 1 step, where an array can cost n. Opposite strengths, exactly.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Losing the head pointer.

    The head is the only way in. Overwrite it while walking and the entire list is unreachable — gone, with no way to get it back.

  • Deleting a node by pointing at the node itself.

    To unlink a node you need the node *before* it, because the arrows only point forwards. Keep track of the previous node as you walk.

  • Forgetting to check for null before following .next.

    The last node points at nothing. Follow that and you crash. Every walk needs a `while (cur !== null)` guard.

  • Expecting a linked list to be fast because it 'has no shifting'.

    Finding the spot is the slow part, and finding is what you do most. In practice arrays usually win — they sit together in memory, and CPUs love that.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+75 XP

01How do you reach the 100th node of a linked list?

02To delete a node, which node do you actually need to be holding?

03What's the linked list's real advantage over an array?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.