Sentinel node (Computer Science)

a.k.a. dummy node

A placeholder node that simplifies operations by eliminating the need to check for null values.

Example

import { LinkedListNode as Node } from '@coachmatt-io/data-structures';

const makeList = () => {
  return (
    new Node(0,
    new Node(1,
    new Node(0,
    new Node(0,
    new Node(2)))))
  );
};
makeList().toString();

'0 -> 1 -> 0 -> 0 -> 2'

function removeUsingSentinel(node, target) {
  const sentinel = new Node(null, node);
  node = sentinel;

  while (node.next) {
    if (node.next.val === target) {
      node.next = node.next.next;
    } else {
      node = node.next;
    }
  }
  return sentinel.next;
}

removeUsingSentinel(makeList(), 0).toString();

'1 -> 2'

function removeWithoutSentinel(node, target) {
  let head = node;

  while (node && node.next) {
    if (node.next.val === target) {
      node.next = node.next.next;
    } else {
      node = node.next;
    }
  }

  if (head && head.val === target) {
    head = head.next;
  }

  return head;
}

removeWithoutSentinel(makeList(), 0).toString();

'1 -> 2'