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

In algorithms questions, we always pass the head of the linked list as the argument. If you are changing the position of the head node and you need to return the new head node, the problem will be how are you gonna return the new head. That's why we initially create a dummy node and dummy.next will point to the head. So, if you are potentially modifying the head of list, use dummy node

One of Apple interview questions is to swap the pair of nodes and return the new head in one way linked list.

Since, the linked list is one way, after we swap the first 2 nodes (in question u need to swap all), how are we gonna keep the reference of the head node. That's where we use the dummy node.

 dummy=new ListNode(dummyValue, head)

dummy node will always point to the first node, so re return dummy.next

There is one common question in linked list questions: Remove the n'th node from the end.

To solve this, we initialize slow pointer and fast pointer. first we traverse the fast pointer n times so when we keep traversing the fast pointer and we reach the end of the list, slow pointer will be n node behind.

However, to remove a node from a linked list, we just have to cut the pointer to that node. If nothing points to that node, it will be garbage collected.

For example, if we have 5 nodes and we need to delete 2nd node from the end, the 3rd node from the end points to the node that we are trying to delete. So we actually have to keep a reference of 3rd node from the end and assign its next to the last node. So we create a dummy node and slow pointer will be starting from there. It will be easier to show on an image:

If the nth node was point to the head of the linked list, we would have returned null. since dummy.next is head, we will return dummy.next