Linked lists, singly and doubly

A linked list is the first data structure where you stop trusting the language to keep things in order and start doing it yourself. Every operation is a small pointer surgery, which is exactly why interviewers love it: there is nowhere to hide a misunderstanding.

The problem it solves

An array is a single block of memory, and that has a price. Inserting at the front means shifting every element one slot to the right. Growing past capacity means allocating a bigger block and copying everything over. If you only ever add and remove at the ends, or in the middle of a sequence you are already holding a reference into, you are paying O(n) for something that should cost a couple of pointer writes.

A linked list removes the block. Each value lives in its own small object, called a node, and the only thing connecting it to the rest is a reference to the next node.

• Insert or remove next to a node you already hold: O(1), no shifting.
• Growth is free: allocate one node, link it in. Nothing is ever copied.
• The price: no index arithmetic. Finding the third element means walking from the head, O(n).

Structure

Two parts and nothing else:

• A node holding a value and a next reference.
• A head variable pointing at the first node. Lose it and the whole list is unreachable.

class ListNode {
  constructor(val, next = null) {
    this.val  = val;
    this.next = next;
  }
}

const head = new ListNode(1, new ListNode(3, new ListNode(5)));

A "linked list" is not a built-in type. It is this class plus a head variable, and everything else is pointer work on top of it. The shape is identical in every language: only the syntax for "a field on an object" changes.

What each operation costs

Two rows deserve a second look. "A node you hold" is the whole pitch: the O(1) only exists when you already have the reference, because finding the node costs O(n). And deleting from a singly linked list needs the previous node, since that is the one whose next you rewrite. This is what a doubly linked list fixes.

Insertion is two pointer writes

Order matters. new.next = B.next first, then B.next = new. Reverse them and B.next already points at new, so new.next = B.next makes the node point at itself and the rest of the list is gone.

function insertAfter(node: ListNode, val: number): ListNode {
  const created = new ListNode(val, node.next); // 1. new points at the old successor
  node.next = created;                          // 2. only now cut the old link
  return created;
}

The dummy sentinel, the one trick worth memorising

Building or merging a list has an annoying edge case: the very first node has no "previous node" to attach to, so the code for the head looks different from the code for every other node. A throwaway sentinel node placed before the real head removes the special case.

function buildList(arr) {
  const dummy = new ListNode(0);   // never part of the real list
  let cur = dummy;
  for (const v of arr) {
    cur.next = new ListNode(v);
    cur = cur.next;
  }
  return dummy.next;                // skip the sentinel on the way out
}

Every node, including the first, is attached the same way. No if (head === null) branch. The same trick simplifies merging two sorted lists, removing every node with a given value, partitioning a list and any other problem where the head might change.

Reversing a list in place

Reversal is the most repeated linked-list question, and the whole answer is one loop that flips a pointer at a time.

function reverse(head) {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    const next = curr.next; // 1. remember the rest before you cut it
    curr.next = prev;       // 2. flip
    prev = curr;            // 3. advance
    curr = next;
  }
  return prev;
}

O(n) time, O(1) space. Capture next before you overwrite curr.next, always: that single line is what the interviewer is watching for.

Detecting a cycle: the tortoise and the hare

A corrupted list can have a tail that points back at an earlier node, so a naive walk never ends. You could remember every visited node in a Set, but that costs O(n) memory. Floyd's algorithm does it in O(1) with two pointers moving at different speeds.

• Move slow one node and fast two nodes per step.
• If fast reaches null, the list ends: no cycle.
• If they ever meet, there is a cycle. Fast gains one node per step on slow, so inside a loop it must catch up.
• To find where the cycle starts, reset one pointer to the head and advance both one node at a time. They meet again exactly at the cycle's entry. The distance from the head to the entry equals the distance from the meeting point to the entry, going around the loop.

function cycleStart(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      let entry = head;
      while (entry !== slow) { entry = entry!.next; slow = slow!.next; }
      return entry;
    }
  }
  return null;
}

The same two-speed idea finds the middle of a list (when fast reaches the end, slow is halfway) and the k-th node from the end (start one pointer k nodes ahead of the other).

Doubly linked: paying a second pointer for a backward walk

A singly linked list can only be walked forward. A doubly linked list adds a prev pointer to every node, which costs one extra pointer to maintain on every insert and delete, and buys two things: walking backward, and deleting a node in O(1) when all you hold is the node itself.

class DListNode {
  constructor(val) {
    this.val  = val;
    this.prev = null;
    this.next = null;
  }
}

function unlink(node) {
  if (node.prev) node.prev.next = node.next;
  if (node.next) node.next.prev = node.prev;
  node.prev = node.next = null;
}

Where linked lists are used in real systems

Linked lists you already use

• The DOM. Every node has nextSibling, previousSibling, firstChild and parentNode: it is a linked structure, and insertBefore is pointer surgery.
• React Fiber. The work-in-progress tree is a linked list of fibers connected by child, sibling and return pointers, so React can pause and resume rendering.
• Node.js `EventEmitter` and timers. Timers with the same duration are kept in a linked list, so adding and removing one is O(1).
• The prototype chain. obj.__proto__.__proto__... is a singly linked list that property lookup walks until it reaches null.
• Git. Each commit points at its parent commit: history is a linked list (a graph, once merges appear).
• Python `collections.deque` is a doubly linked list of fixed-size blocks, and OrderedDict keeps order with a linked list.

When not to use a linked list

In practice, a plain array beats a linked list far more often than the complexity table suggests.

• You need indexing. Anything like "give me item 400" belongs in an array or a hash map.
• You mostly iterate. Arrays are contiguous, so the CPU cache prefetches the next elements. Linked nodes are scattered across memory, and every hop can be a cache miss. An O(n) array scan can beat an O(n) list walk by an order of magnitude.
• You insert in the middle but must find the spot first. The O(1) insert is free, but reaching the position is O(n), so you gained nothing over splice on a small array.
• Memory is tight. Every node pays for one or two pointers and an allocation header.
• Your language is garbage-collected and lists are short. JavaScript engines optimise arrays heavily. Reach for a linked list when you need O(1) removal from the middle or stable node identities, not by reflex.

What interviewers ask

• "Reverse a linked list." Three pointers, one loop, O(n) time and O(1) space. Then reverse it recursively, and reverse only a sub-range.
• "Detect a cycle, and find where it starts." Floyd's tortoise and hare, O(1) space.
• "Find the middle node." Slow and fast pointers again.
• "Merge two sorted lists." A sentinel node and relinking, with no new nodes allocated.
• "Remove the n-th node from the end." Two pointers n apart, plus a sentinel so removing the head is not a special case.
• "Why not use an array?" Say what the linked list buys (O(1) insert or delete given a node) and what it costs (no indexing, poor cache behaviour).
• "Singly or doubly linked?" Doubly when you need to delete a node you hold, or walk backward. Singly when memory and simplicity matter.

The bugs that show up every time

• Losing the head. Reassigning cur.next before you have saved the old cur.next severs the rest of the list.
• Dereferencing null. while (node.next) crashes the moment node itself is null. Check the thing you are about to dereference.
• Forgetting the tail. After deleting the last node, the tail pointer still points at the deleted node. Update it, or you will append to a ghost.
• Comparing values instead of nodes. Lists can hold duplicates, so cycle detection and "is this the same node" must use reference equality.
• No sentinel, so the head is a special case. If you find yourself writing a separate branch for the first node, add a dummy node instead.

Interviewers keep asking for a from-scratch linked list not because you will build one at work, but because pointer manipulation forces you to reason about state one mutation at a time. That is the same skill you need to debug a DOM tree, a doubly linked cache or a queue. None of it is JavaScript-specific: the same three-pointer reversal and the same sentinel trick are what you would write in Python or any language with references.