Dummy Nodes in Linked Lists

Dummy nodes are fictitious or temporary nodes that are inserted into a data structure or algorithm to assist in handling special cases or simplifying complex scenarios.

For the most part, we will use dummy nodes as a reference to a head node. By introducing a dummy node before the head, we create a stable reference point.

Example Problem

Let's see how we can use a dummy node to solve a problem that we have seen before, "Remove Twos from a Linked List." Below is the problem description from the previous assignment:

// Given the head of a linked list, remove all
// occurrences of the value 2 from the linked list.

// Input:  1 -> 2 -> 3 -> 2 -> 4 -> null
// Output: 1 -> 3 -> 4 -> null

// Input:  2 -> 3 -> 2 -> null
// Output: 3 -> null

// Input:  null
// Output: null

If you remember the solution to the problem, you might remember that while iterating through the linked list, when we had a matching value, we also had to check if prev was null. If that was the case, we couldn't use prev.next = curr.next because this would raise an error. Instead, we had to update the head node to curr.next. This scenario happened when deleting a 2 from the beginning of the linked list.

This is the part of the code we are referring to:

function deleteTwos(head) {
  let prev = null;
  let curr = head;

  if (!head) {
    return head;
  }

  while (curr) {
    if (curr.val === 2) {
      #highlight
      if (!prev) {
        head = curr.next;
      #endhighlight
      } else {
        prev.next = curr.next;
      }
    } else {
      prev = curr;
    }
    curr = curr.next;
  }

  return head;
}

Instead of starting with prev = null, let's create a "dummy" node with a next pointer that points to the head node, and assign prev to this dummy node. With this setup, instead of reassigning head when we want to delete the first node, we can reassign prev.next, just like when we delete other nodes. dummy.next will always point to the current head node, even if we delete the initial head node.

Algorithm

Let's see the algorithm for this problem:

1. Initialize three pointers: dummy, prev and curr.
   • Set dummy to a new node and its next pointer to head.
   • Set prev to the dummy.
   • Set curr to the head of the linked list.
2. Begin iterating, checking the value of curr on each iteration.
   • If curr has a value of 2 (our target value):
     • Set prev.next to curr.next to bypass curr and remove it from the list.
   • If curr has a value that is not 2:
     • Update the prev pointer to curr.
   • Move the curr pointer to the next node.
3. Return dummy.next, which references the head node of our updated linked list.

Notice that step two has been simplified relative to the algorithm we used for the previous solution to this problem.

Walkthrough

Here's a step-by-step walkthrough of removing occurrences of the value 2 from the linked list 2 -> 2 -> 3 -> 2 -> 1. The output should be a linked list 3 -> 1. Since we are removing several nodes from the beginning, the "dummy" node will come in handy here.

Step 1

We initialize three pointers, dummy, prev, and curr. Next, we set the dummy's next pointer to head, prev to dummy, and curr to the head of the linked list (1).

Step 2

We begin iterating through the linked list, checking the value of curr on each iteration. At this step, curr's node has a value of 2, so we want to remove that node from the list. To do that, we first reassign the next pointer of the prev node to curr.next. Because dummy points to the same node as prev, an update to prev.next is also an update to dummy.next.

Next, we slide the curr pointer to point to the next node.

As a result, the head variable references a node that has been removed from the list. We needed head for the setup of this solution, but we won't use it in our iterations or thereafter.

Step 3

We continue traversing the linked list. At the beginning of the third step, our list looks like this.

The current node has the value 2. So, once again, we reassign the next pointer of the prev node to the curr.next.

Next, we slide the curr pointer.

Step 4

At the beginning of the fourth step, this is the state of the list.

We've encountered the node with the value 3. Since it is not the target node, we slide the prev and curr pointers. The prev pointer is updated to point to the node which contains the value 3 and the curr pointer is moved to the next node, which contains the value 2. Notice that dummy hasn't moved in this case, and its next pointer points to the new head of the linked list (node with the value 3).

Step 5

Let's see the list at the beginning of the fifth step.

Once again, we encounter the node with the value 2. We reassign the next pointer of the prev node to the curr.next, thus removing this node from the list.

Then, we move the curr pointer to the next node, which contains the value 1.

Step 6

At the beginning of this step, the list looks like this.

Now, the value of the current node is 1. It is not the target value, so we slide the prev and curr pointers. prev now points to the node with the value 1, and curr now points to null. Since curr points to null, we are at the end of the list, and we return dummy.next as the final result, the new head node with the value 3.

After removing all occurrences of the value 2, the resulting linked list is 3 -> 1.

Solution Code

Now, let's take a look at the code implementation of the algorithm:

function deleteTwos(head) {
  let dummy = new Node();
  dummy.next = head;
  let prev = dummy;
  let curr = head;

  while (curr) {
    if (curr.val === 2) {
      prev.next = curr.next;
    } else {
      prev = curr;
    }
    curr = curr.next;
  }

  return dummy.next;
}

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

function deleteTwos(head) {
  let dummy = new ListNode();
  dummy.next = head;
  let prev = dummy;
  let curr = head;

  while (curr) {
    if (curr.val === 2) {
      prev.next = curr.next;
    } else {
      prev = curr;
    }
    curr = curr.next;
  }

  return dummy.next;
}

// Helper function to format the linked list into a string
function stringifyList(head) {
  let curr = head;
  let result = "";
  while (curr !== null) {
    result += curr.val + " -> ";
    curr = curr.next;
  }
  result += "null";
  return result;
}

// Test case 1
const head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(2);
head1.next.next.next.next = new ListNode(4);

console.log("Input: ", stringifyList(head1));
console.log("Output:", stringifyList(deleteTwos(head1)));
// Input:  1 -> 2 -> 3 -> 2 -> 4 -> null
// Output: 1 -> 3 -> 4 -> null

// Test case 2
const head2 = new ListNode(2);
head2.next = new ListNode(3);
head2.next.next = new ListNode(2);

console.log("Input: ", stringifyList(head2));
console.log("Output:", stringifyList(deleteTwos(head2)));
// Input:  2 -> 3 -> 2 -> null
// Output: 3 -> null

Throughout this assignment, we have seen how to use dummy nodes to solve problems with linked lists. Using a dummy node, we can ensure that its next pointer always points to the head node, eliminating the need to handle certain edge cases where the head node changes or is removed from the list.