Linked lists

What you'll learn

How a linked list is built from nodes, and how it trades fast insertion for slow lookup compared to an array.

Why it matters

Linked lists teach you to think in references (pointers). They also power queues, undo chains and the history of many data structures.

Explanation

A linked list is a chain of nodes. Each node holds a value and a link to the next node. The first node is called the head. The last node points to null.

Because nodes are not side by side in memory, you cannot jump to "item 5". You must walk from the head, one link at a time: O(n) to find something.

The upside: adding or removing at the head is O(1). You only change a link, and nothing needs to shift.

Example

Step-by-step walkthrough

1

head

→

2

→

3

→

null

A linked list: each node points to the next one.

Play

1. The list starts as 1 -> 2 -> 3, where head is the node holding 1.
2. prepend 0 makes a new node that points at the old head, then moves head to it. No shifting.
3. append 4 has to walk to the end first.
4. find and delete walk one node at a time until they reach the target.
5. The program prints 0 -> 1 -> 2 -> 3.

Try it yourself

Add a function that returns the length of the list by walking it.

List lengthJavaScript

Editable codeclass Node { constructor(value, next = null) { this.value = value; this.next = next; } } const head = new Node("a", new Node("b", new Node("c"))); let count = 0; let cur = head; while (cur !== null) { count++; cur = cur.next; } console.log("length:", count);

Run ResetCopyCtrl+Enter to run

Common mistakes

• Losing the head. If you overwrite head without saving it, the rest of the list is gone.
• Walking past the end. Always check cur !== null.
• Expecting O(1) lookup by index. You have to walk.
• Forgetting to re-link when deleting, leaving a broken chain.

Quick quiz

Summary

• A linked list is nodes with next links, starting at the head.
• Insert or delete at the head is O(1); search is O(n).
• Arrays are better for index lookups, linked lists for cheap inserts at the front.

Next: sorting.

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

// build 1 -> 2 -> 3
let head = new Node(1, new Node(2, new Node(3)));

// prepend 0: O(1)
head = new Node(0, head);

// walk the list: O(n)
let cur = head;
const out = [];
while (cur !== null) {
  out.push(cur.value);
  cur = cur.next;
}
console.log(out.join(" -> "));