PART II 4) What is the reason that we used a dummy node at the head and tail of
ID: 3708579 • Letter: P
Question
PART II 4) What is the reason that we used a dummy node at the head and tail of many of our linked list implementations?aue Why didn't we do this for the linked list implementation of the Stack or Queue? 5) Write a method to search for and remove an element from a linked list, thereby returning the data portion of the nodeeyc 6) a) When devising an algorithm for linked lists, why must vou be careful about the order in which you change the references? b) What code would be needed to change the references in a linked list when moving up one node? c) Why did we have a previous reference in our linked list implementation? d) Write a class for a linked list node with just one constructor that allows the initialization of all instance variables.Explanation / Answer
4)
Linked List, Stack, Queue all the three are types of data structure. Each one has its own properties.You answer is in those properties. STACK & QUEUES have propertie of LIFO(Last In First Our) & FIFO(First In First Our) respectively. Queue have Head and Tail. Each new element enteres from Head and remove from Tail (like a normal queue of people). Head and Tail are those nodes which helps to find the queue (as nodes carry refence of queue). But the Head and Tail nodes should have value too to fulfill queue properties. Similarly In stack we have a Front node. Each element pushed(insert) & popped(removed) from front(like a normal stack of paltes). But the Front nodes should have value too to fulfill queue properties. We can't make head node tail node and front node as dummy node .We have different set of operations to operate on Stack and Queue.
? In linked list we have different set of operations like we need to traverse the linked list to search specific element, insert a new element in any place in between or at edges of the list etc. thats why we need to us a head node to find the starting address of the linked list and make the head node as dummy node.
5)
Method to search for specific value node in the linked list
int inList(node *head, int val)
{
node *temp = head;
while (temp != NULL)
{
if(temp->val == val)
{
printf("%d Found... ",val);
return temp->val;
}
temp = temp->next;
}
printf("%d not Found... ",val);
return -1;
}
Method to remove for specific value node from the linked list
int deleteNode(node *head, int val)
{
node *temp = head;
node *t, *prev = NULL;
while (temp != NULL)
{
if(temp->val == val)
{
printf("%d Find And Removed... ",val);
if(temp->next!=NULL)
{
prev->next=temp->next;
}
else
{
prev->next=NULL;
}
return temp->val;
}
prev = temp;
temp = temp->next;
}
printf("%d did not find... ",val);
return -1
}
6)
a:- ?we need to be carefull about ordering of references because it is very importent to set right reference to next valid node while removing a node from list, adding a new node into list,searching a node into the list etc. We need to maintain the rest list as it is. and maintain its valid end(end->next should be NULL) and valid head of the linked list.
b:- ?If we have a head node called node *head_node; (node pointing to start of the linked list)
then we need to take a node called node *traverse; (to traverse linked list elements one by one).
we need to set the traverse node to head ?traverse=head;
change the traverse reference to traverse=traverse->next_node;
? ?we need to do it till traverse!=NULL? (to traverse the linled list till last element of the list)
c:- ?when we are performing operation of removing a node from linked list then we need to carry the address of previous node of linked list along with thw current traversing node so that when we find the node which we are going to remove from linked list we just did this
previous_node->next=current_node->next;//join the remaining linked list aftre removing a node in between.
free(current_node); //release the space of removed node.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.