Linked lists

Nodes, not slots

Each node holds a value and the address of the next one. Nothing is contiguous, so there is no arithmetic that jumps to element 500 000 — you follow 500 000 pointers. That is the whole trade in one sentence: you give up the index to gain the insert.

const node = { value: "a", next: null };

/* a list is just the first node */
const list = { value: "a", next: { value: "b", next: { value: "c", next: null } } };

let current = list;
while (current) {            // walking it is the only way to reach anything
  use(current.value);
  current = current.next;
}

The costs, against an array

Read that table carefully: the list only wins when you already have the node. "Insert at position 5000" is O(n) on both, because finding position 5000 is the expensive part. Almost every benchmark that shows linked lists winning is quietly comparing "insert where I am" with "insert where I must search".

Why the array usually wins anyway

Each node is a separate allocation, somewhere else in memory. Walking the list is a chain of cache misses: the processor cannot predict where the next node is, so it waits for memory every step. Walking an array is the opposite — the hardware has already fetched what you are about to ask for.

In practice that is often a factor of ten on the same O(n) operation, which is why real programs use a growable array almost everywhere and reach for a list only when the O(1) splice genuinely matters: an LRU cache, an allocator’s free list, the undo stack in an editor.

Singly, doubly, circular

A doubly linked list costs one more pointer per node and buys delete(node) in O(1) with nothing else known — which is exactly what an LRU cache needs when it moves an entry to the front.

A sentinel head node (a dummy that always exists) removes almost every if (head === null) from the code. Insert and delete then have one case instead of three, and the bugs go with them.

/* singly: to delete a node you must know the one BEFORE it */
prev.next = node.next;

/* doubly: the node knows both neighbours, so it can remove itself */
node.prev.next = node.next;
node.next.prev = node.prev;

The two classic manipulations

The two-pointer trick also detects a cycle: if the list loops, the fast pointer eventually catches the slow one; if it ends, it reaches null. That is Floyd’s algorithm, and it uses O(1) memory where a Set of seen nodes would use O(n).

let prev = null;
let current = head;
while (current) {
  const next = current.next;   // hold on to it before overwriting
  current.next = prev;
  prev = current;
  current = next;
}
return prev;                   // the old tail is the new head

let slow = head, fast = head;
while (fast && fast.next) {    // fast moves two, slow moves one
  slow = slow.next;
  fast = fast.next.next;
}
return slow;                   // slow is halfway when fast reaches the end