Dummy nodes in linked lists

Question

Q: When are they used? (Homework question)

1. 1st and last node in the list

2. Sometimes used as 1st and last nodes in the list

3. Never used as 1st and last nodes in the list

Wikipedia says,

A sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. A sentinel node does not hold or reference any data managed by the data structure.

I'm thinking B but I don't really know.

Answer 1

Yes, Answer is 2. Sometimes used as first and last nodes in the list.

To answer this question you need to understand need and use of dummy node. I will explain this with the help a link list problem.

Say you have Delete a node in a singly link list and only pointer to that node is given to you, How do you delete ?? Answer : If we have HEAD node we can simply traverse until we find that node and delete it, but this will not work if we have pointer of last node, because last node points to NULL. Here we need DUMMY node. which is a blank node that help us build new node of delete node later.

In case of doubly link list this problem can be in either direction. Definition of dummy node : a dummy node at the front/end of the list that is there only to reduce the need for special-case code in the linked-list operations. It is an empty template to build new nodes later. problem here is we don't have any head node. We only have pointer to target node only.

Solution will be like this we will copy data from next node to node what to delete and delete next node.

struct node *temp  = node_ptr->next;

node_ptr->data  = temp->data;

node_ptr->next  = temp->next;

free(temp);

but this will not work if we have pointer of last node, because last node points to NULL. Here we need DUMMY node. which is a blank node that help us build new node of delete node later.

In case of doubly link list this problem can be in either direction.

Definition of dummy node : a dummy node at the front/end of the list that is there only to reduce the need for special-case code in the linked-list operations. It is an empty template to build new nodes later.

Reference : http://pages.cs.wisc.edu/~vernon/cs367/notes/4.LINKED-LIST.html

Answer 2

Look, there is a significant difference between a "Dummy" node and a "Sentinel" node.

Dummy nodes "Sometimes get used as first and last nodes in the list".

When you initiate a linked list a common approach is to create a dummy node, and interestingly it's the last node at the same time.

Obviously not always first or last nodes of a LL are dummy records.

Please note that you can use a dummy node without any data and a null pointer as a sentinel that shows the last node in the LL.

You may wonder is it possible to have a LL without any dummy node?
Answer: Yes. You can hold initialization of your LL until the insertion of the first data entry, and to that point just have null pointer as the LL, and after insertion(s) hold a pointer to the head node and always use a null pointer as "Next" node of the tail node.

I refer you to this page for more insight.