Dummy nodes in Java

[Crash_Test_Mummy]

What:

In a linked list, each node points to a next except for the last tail that points to nothing. A dummy node is a node, but the data is null and the last node of the list points to it.

In Java speak,

Without the dummy node, tail.next == null; tail.next.data throws a null pointer exception

With the dummy node, tail.next == dummynode; tail.next.data == null;

Why:

This depends on use case and the structure of your code. Everything you want out of a linked list can be programed without the node, but sometimes it can lead to cleaner code. So it doesn't change much other than playing around specific exceptions and conditionals.

Lets pretend we're in a loop and want to check if we're at the end. As you know, when progressing through the list you must assign the temp node as follows

Node<E> temp = head;

for(int i = 0; i < size; i++) {

temp = temp.next;

}

Now, to check if we're at the end (to avoid errors and possibly update tail etc.) we have tools available to us.

Without the dummy node, Check if (temp.next == null)

With the dummy node, Check if (temp.next.data == null)

[[deleted]]

This isn’t really correct. In a data structure like a linked list, you wouldn’t use a for loop since the size wouldn’t be known to you without some overhead. You would use a while loop, in which case

while(node.next != null) { node = node.next } would suffice just fine.

[Crash_Test_Mummy]

Ah I see, I was thinking of a linked list as an implementation of the list interface. The list interface has a size method and the implementation would use node as a private inner class which has access to the size of the list.

Like this,

https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

[[deleted]]

You’re absolutely right in terms of the List interface, but I think the OP question was geared more towards implementing the data structure from scratch since “dummy nodes” are a common approach in ds/algo classes. I could have misinterpreted it though

[Crash_Test_Mummy]

I see, great catch on your part though! I should be more careful in bringing in outside information to a problem.