Linked Lists: Practice

Linked Lists

Each node holds a value and a pointer to the next node, so the list can grow or rearrange without shifting anything else.

Loading visual…

Definition

A linked list is a sequence of nodes, where each node bundles a value together with a reference to the next node in the chain. The list itself is just a reference to the first node, the head; there is no single block of memory holding every element the way an array has, so nodes can live anywhere and the chain of `next` references is what actually defines the order. That structure changes the cost trade-offs compared to an array. Reaching the nth node means walking `next` pointers one at a time from the head, an O(n) walk, so linked lists give up the O(1) index access arrays have. In exchange, once you are already at a node, inserting or removing right there is O(1): it only means re-pointing a couple of `next` references, with nothing else in the list shifting. Some linked lists are doubly linked, giving each node a `previous` reference too, which makes walking backward or removing a node possible without needing a reference to the one before it.

Examples

function makeList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = { value: values[i], next: head };
  }
  return head;
}
let node = makeList([1, 2, 3]);
while (node) {
  console.log(node.value); // 1, then 2, then 3
  node = node.next;
}

Each node only knows its own value and the node after it, so reading the whole list means following next references one at a time from the head.

function insertAfter(node, value) {
  node.next = { value, next: node.next };
}
const a = { value: 1, next: { value: 2, next: null } };
insertAfter(a, 99); // a -> 99 -> 2

Inserting only re-points a's next reference to the new node, and the new node's next takes over the reference a used to hold; nothing else in the list moves.

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

A slow pointer moving one node at a time and a fast pointer moving two at a time will meet only if the list loops back on itself.

Common mistakes

Overwriting a node's next reference before saving what it used to point to, losing the rest of the list.
Forgetting to update the head (or tail) reference after inserting or removing the first (or last) node.
Assuming index access is O(1) like an array; reaching the nth node means walking next references one at a time, which is O(n).

Key takeaways

A node bundles a value with a reference to the next node, and the chain of references is the list.
Inserting or removing a node only touches the pointers immediately around it, not the rest of the list.
Linked lists trade an array's O(1) random access for O(1) insertion and removal at a known position.

Check your understanding

Node A currently points to node B. To insert a new node X between them, what has to happen?

Where you see this

Implementing undo history, playlists, or browser tab lists that are frequently reordered or spliced in the middle.
Building other data structures on top, such as a stack, queue, or a hash map's collision chains.
Representing a music playlist or browser back/forward history, where sequence matters more than random access.
Detecting cycles or finding the middle element of a sequence using fast and slow pointers.

Practice this

Middle Node (easy)Merge Two Sorted Lists (medium)Design a Linked List (medium)