Linked Lists

A linked list is a chain of little boxes. Each box — a node — holds a value and a pointer to the next box. There is no single contiguous block of memory; the nodes can live anywhere, and the next pointers are what stitch them into a sequence.

That design flips the array trade-off on its head. You lose instant indexing — to reach the 5th node you must walk from the head through four next hops. But once you are standing at a node, splicing a new node in or cutting one out is just a couple of pointer swaps, no shifting of everything after it.

Singly vs doubly

A singly linked list stores one pointer per node (next), so you can only travel forward. A doubly linked list adds a prev pointer, letting you walk backward and delete a node in O(1) when you only have a reference to it (no need to hunt for its predecessor). The cost is an extra pointer of memory per node.

Most implementations track a head reference; many also keep a tail so that appending is O(1) instead of an O(n) walk to the end. A doubly linked list with head and tail is the backbone of a deque.

Reversing a list

Reversal is the "hello world" of pointer manipulation and a near-guaranteed interview question. Walk the list once, and at each node flip its next pointer to point backward. Keep three references — prev, curr, and a saved next — so you never lose the rest of the chain.

function reverse(head) {
  let prev = null
  let curr = head
  while (curr) {
    const next = curr.next // save before we overwrite
    curr.next = prev       // flip the pointer
    prev = curr            // advance both
    curr = next
  }
  return prev // new head
}

Cycle detection — Floyd’s algorithm

What if a next pointer loops back into the list? A naive scan would run forever. Floyd’s tortoise and hare sends two pointers through the list at different speeds: slow moves one step, fast moves two. If there is a cycle, the fast pointer eventually laps the slow one and they meet — all in O(n) time and O(1) space, no extra hash set required.

function hasCycle(head) {
  let slow = head, fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) return true // they met -> cycle
  }
  return false // fast fell off the end -> no cycle
}

When to reach for a linked list

• You do frequent inserts/deletes at the ends or at held references — O(1) splices.
• You are building a queue, stack, or deque and want guaranteed O(1) edge operations with no resizing.
• You need a stable structure where node references stay valid even as the list grows.
• Avoid them when you need random access or tight, cache-friendly iteration — an array wins on both.