Linked List

Values live in separate nodes chained by pointers — instant insert at the head, but reaching the k-th element means walking the chain.

8 min read Watch it move Build it

A linked list stores each value in its own little box — a node — that also holds a pointer to the next node, chaining them together. Unlike an array, the boxes aren't packed side by side in memory; they can sit anywhere, linked only by those pointers. That single design choice flips an array's trade-offs on their head.

Node, head, and the chain

1A node holds a value plus a next pointer to the following node.
2The head is the first node — the entry point you always start from.
3The last node's next points to null, marking the end (the tail).
4To reach a position you traverse: follow next from the head, node by node.

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

// insert at head — O(1), just repoint two links
function prepend(head, value) {
  const node = new Node(value);
  node.next = head; // new node points at the old head
  return node;      // new node is the new head
}

The core trade-off vs an array

Adding at the front is O(1): you create a node and repoint one link — no shifting. But there's no random access: reaching the 10th item means following pointers from the head ten times, so access is O(n). An array is the mirror image — O(1) access by index, but O(n) to insert at the front because everything shifts.

Insert and delete: it's all about pointers

Once you *hold* a node, splicing around it is O(1) — you just rewire next pointers, no elements move. To insert after a node, point the new node at the node's successor, then point the node at the new node. To delete the next node, point node.next past it to node.next.next. The cost is never the rewiring; it's *getting to* the spot, which takes a traversal.

// delete the node after `node` — O(1) once you're there
function deleteAfter(node) {
  if (node.next) node.next = node.next.next; // skip over it
}

Lose the head, lose the list

The head is your only handle on the whole chain — there's no index to fall back on. Reassign or drop it carelessly and every node after it becomes unreachable (and garbage-collected). When inserting at the head, always return and keep the new head.

OperationTimeSpace

Access k-th element · must walk the chainO(n)O(1)

Insert / delete at head · repoint a linkO(1)O(1)

Insert / delete at a known node · rewire next pointersO(1)O(1)

Check yourself

Why is inserting at the head of a linked list O(1) while accessing the k-th element is O(n)?