Head node in linked lists
I have problems with understanding what is the nature of the first node, or the so called head, in a linked list data structure. A linked list consists of nodes, and each node contains some data and a link to another node in the list. But is the very first node a node which contains data and a link to the second node? Or is it contain only a link (and no data) to a node? I thought that the very first node in a linked list has both data and a link to another node, but in one introductory book it is explained that the head is a node but a link that gets you to the first node. At the same time head is a variable of the type of the node. Why is it like this? (I am working in Java, if that matters). Thanks you.
Answer
These are called "dummy" header nodes, and they allow you to write general code that works for empty and non-empty lists.
Regularly, if you want to insert a Node at the end of your list, you need two cases. If head is null, indicating the list is empty, then you would set head to the new Node. If head is not null, then you follow the next pointers until you have the last Node, and set the next pointer to the new Node.
However, if you use a dummy header, head will never be null. It will be a Node with a null next pointer, which you can point to your new Node, just how you would if the list did contain nodes.