What is a Dummy Head?

Question

So I want to know for sure what is a dummy head/dummy node in a linked list. Can somebody tell me the definition and give me an example maybe?

Answer 1

Dummy nodes are more like a hack and are commonly used when you want to avoid writing additional code for edge cases.

Consider the following case of inserting at tail in a linked list:

void insertAtTail(Node oldTail, int i){
    Node newTail = new Node(i);
    oldTail.next = newTail;
    return newTail;
}

This works fine when oldTail is not null. But imagine the scenario where we are trying to perform insertAtTail() on an empty list. The above written code will not work if the node is null. Therefore, we've to handle the edge case of checking if oldTail is null:

Node insertAtTail(Node oldTail, int i){
    Node newTail = new Node(i);
    if(oldTail == null) {return newTail;}
    oldTail.next = newTail;
    return newTail;
}

It's in scenarios like these that dummy nodes come in handy. Imagine I've a dummy node as follows:

Node dummy = new Node(0);

Now we pass this dummy node to the calling function:

insertAtTail(dummy, 5);

When a dummy node is passed to the calling function, you'll see that there's no need to check if dummy is null here. Therefore, we can skip the check for empty node:

Node insertAtTail(Node dummy, int i){
    Node newTail = new Node(i);
    dummy.next = newTail;
    return newTail;
}

As you can see, I've removed the check for null here.

Answer 2

When the head of the Linked List doesn't point to any Node, you create a Dummy Head (Node) pointed from that head. So that you would always be able to reach e.g. head.val or head.next without doing any extra null checks.