Singly linked lists and pointer discipline

A linked list is a chain of nodes; each holds a value and a reference to the next. There is no contiguous block and no arithmetic — to reach the tenth node you walk ten links.

const node = (value, next = null) => ({ value, next });

// 1 → 2 → 3 → null
const head = node(1, node(2, node(3)));

The costs, and the asterisk on them

That middle row is the whole appeal, and the one people misquote. "O(1) insertion" is true only when you already hold the predecessor. Finding it costs O(n), which is why inserting into a linked list at position k is not faster than inserting into an array.

The dummy head

Most bugs in list code are the special case where the head itself changes. A dummy node removes the special case entirely:

function removeAll(head, target) {
  const dummy = node(null, head);      // a node that is always before the head
  let prev = dummy;

  while (prev.next) {
    if (prev.next.value === target) prev.next = prev.next.next;
    else prev = prev.next;
  }

  return dummy.next;                   // the real head, possibly changed
}

Without the dummy you need a separate branch for "the head matched", and that branch is where the bug lives. Reach for a dummy head whenever the head might be removed or replaced.

Pointer discipline

Two habits prevent nearly every crash:

1. Check before you dereference. while (node && node.next) — the order matters.
2. Save what you are about to overwrite. Reassigning node.next before you have stored the old value loses the rest of the list.

const next = current.next;   // save first
current.next = previous;     // then overwrite

Draw three nodes on paper and move the arrows as you write the code. Every experienced engineer still does this; it is faster than debugging.