Linked lists are fundamental data structures frequently used in computer science. Often, programmers need to directly implement them. How can we implement an error-free linked list quickly, especially under time pressure and mental stress during job interviews? This post discusses an important trick: Using a dummy head/tail node.

Dummy Head/Tail Nodes in a Doubly Linked List

In doubly linked list implementations, we typically have list node objects that have the following data type (using TypeScript annotations):

// Doubly linked list node
interface DoublyListNode {
  next: DoublyListNode;
  prev: DoublyListNode;
  value: any;
}

Usually, we have a variable head, which points to the first node in the linked list, and tail, which points to the last node in the linked list. If the linked list is empty, both variables equal null. Below is such an implementation with a function to insert a node to head:

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // Insert data right after head.
  insertToHead(value) {
    if (this.head === null) {
      // empty linked list
      this.head = { prev: null, next: null, value };
      this.tail = this.head;
    } else if (this.head === this.tail) {
      // linked list with one element
      this.head = { prev: null, next: this.head, value };
      this.tail.prev = this.head;
    } else {
      // linked list with more than one element
      this.head = { prev: null, next: this.head.next, value };
      this.head.next.prev = this.head;
    }
  }
}

We refer to this implementation as a normal implementation.

A linked list implementation with a dummy head node and a dummy tail node always sees the first and last nodes as dummy nodes, i.e., nodes that don’t contain any data. Real data only starts from the second node and ends before the second last node. An implementation looks like this:

class DoublyLinkedList {
  constructor() {
    this.head = { prev: null, next: null, value: null };
    this.tail = { prev: this.head, next: null, value: null };
    this.head.next = this.tail;
  }

  // Insert data right after head.
  insertToHead(value) {
    // Three if-else branches in normal implementation
    const newNode = { prev: this.head, next: this.head.next, value };
    this.head.next = newNode;
    newNode.next.prev = this.head.next;
  }
}

The constructor initializes a dummy head node and a dummy tail node, and ensures that both head and tail nodes are always dummy. We refer to this implementation as a dummy-node implementation.

With this simple change, insertToHead has become surprisingly simple: We have eliminated those perplexing if-else branches! This simplification comes from the fact that we no longer need to worry about the edge cases in which head and tail behave differently from the cases in which the linked list contains no less than two nodes.

The figure below illustrates these two implementations:

Normal and Dummy-Node Implementations of Doubly Linked Lists

More Doubly Linked List Functions

With a dummy head node and a dummy tail node, other common functions have also become simpler:

class DoublyLinkedList {
  constructor() {
    // ...
  }

  // Insert after the given node reference.
  insertAfter(node, value) {
    // Three if-else branches in normal implementation
    const newNode = { prev: node, next: node.next, value };
    node.next = newNode;
    newNode.next.prev = newNode;
  }

  // Insert before the given node reference.
  insertBefore(node, value) {
    // Three if-else branches in a normal implementation
    const newNode = { prev: node.prev, next: node, value };
    node.prev = newNode;
    newNode.prev.next = newNode;
  }

  // Insert data right after head.
  insertToHead(value) {
    // Three if-else branches in a normal implementation
    this.insertAfter(this.head, value);
  }

  // Insert data right before tail.
  insertToTail(value) {
    // Three if-else branches in a normal implementation
    this.insertBefore(this.tail, value);
  }

  // Remove a given node reference.
  remove(node) {
    // Four if-else branches in a normal implementation
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  // Remove the first node.
  removeHead(value) {
    // Two if-else branches in a normal implementation
    if (!this.isEmpty()) {
      this.remove(this.head.next);
    }
  }

  // Remove the last node.
  removeTail(value) {
    // Two if-else branches in a normal implementation
    if (!this.isEmpty()) {
      this.remove(this.tail.prev);
    }
  }

  // Traverse all nodes.
  traverse(f) {
    // Two if-else branches in a normal implementation
    for (let node = this.head.next; node !== this.tail; node = node.next) {
      f(node.value);
    }
  }

  // Is the linked list empty?
  isEmpty() {
    return this.head.next === this.tail;
  }
}

What About Singly Linked Lists?

Singly linked list also benefits from a dummy head node, but to a lesser extent.

In singly linked list implementations, we typically have list node objects that have the following data type (using TypeScript annotations):

// Singly linked list node
interface SinglyListNode {
  next: SinglyListNode;
  value: any;
}

In a normal implementation, we have a variable head, which points to the first node in the linked list, or null if the singly linked list is empty. Below is such an implementation with a function to insert a node to head:

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Insert data right after head.
  insertToHead(value) {
    if (this.head === null) {
      this.head = { next: null, value };
    } else {
      newNode = { next: this.head.next, value };
      this.head = newNode;
    }
  }
}

A linked list implementation with a dummy head node always sees the first node as a dummy node, i.e., a node that doesn’t contain any data. Real data only starts from the second node. An implementation looks like this:

class SinglyLinkedList {
  constructor() {
    this.head = { next: null, value: null };
  }

  // Insert data right after head.
  insertToHead(value) {
    newNode = { next: this.head.next, value };
    this.head.next = newNode;
  }
}

The constructor initializes the linked list with a dummy head node, and ensures that the head node is always dummy. With this simple change, insertToHead has also become a little simpler: We have eliminated the annoying if-else branches to determine whether head is null.

However, this simplification isn’t that dramatic. Furthermore, unlike doubly linked lists, most functions don’t get simpler. For this reason, it is less useful to use a dummy head node to implement a singly linked list.

Conclusion

A dummy head node and a dummy tail node make the implementation of a doubly linked list much simpler and less error-prone. A dummy head node also makes the implementation of a singly linked list simpler, but to a much lesser extent.