Doubly and circular linked lists

Doubly linked lists

Each node holds prev as well as next. That second pointer costs memory and buys the operation singly linked lists cannot do: remove a node you hold a reference to, in O(1), without walking to find its predecessor.

function unlink(node) {
  if (node.prev) node.prev.next = node.next;
  if (node.next) node.next.prev = node.prev;
  node.prev = node.next = null;      // help the garbage collector
  return node;
}

That single capability is why doubly linked lists sit at the heart of LRU caches, browser history, undo stacks, and the ready queues inside operating system schedulers.

They also traverse backwards, which makes them the natural fit for a text editor's cursor or a media playlist with "previous track".

Sentinel nodes — a permanent dummy head and tail — remove every null check from insertion and removal. Production implementations nearly always use them.

Circular linked lists

Point the tail's next back at the head. There is no end, so traversal must stop on a condition rather than on null:

let node = head;
do {
  visit(node);
  node = node.next;
} while (node !== head);      // stop when you come back round

Circular lists model anything that cycles: round-robin scheduling, a turn-based game, a ring buffer of fixed capacity, the Josephus problem.

The hazard is obvious and still catches people — any while (node) loop over a circular list runs forever.

Choosing between them

The memory argument

A doubly linked list of numbers spends two pointers plus object overhead per element — often several times the payload. An array of the same numbers is contiguous and cache-friendly. Unless you need O(1) removal by reference or genuinely unbounded growth without reallocation, the array wins on real hardware even where Big O says otherwise.