C++ Consider the following code: // Linked Lists: INSERT a new node in a sorted
ID: 3908376 • Letter: C
Question
C++
Consider the following code: // Linked Lists: INSERT a new node in a sorted list
struct Data { int number; char ch; };
struct ListNode { Data data; struct ListNode *next; };
Assume that a linked list has been created and head points to a sentinel node. A sentinel node is an empty data node in the beginning of the list. It sometimes holds a sentinel value. The use of sentinel nodes is a popular trick to simplify the insert and delete operations.
You may also assume that the list is not empty and it is sorted in ascending order by the numeric value in the node. The data in the sentinel node is -9999.
Write a function named insertNode that is passed the pointer to the sentinel node and new data to be inserted into the sorted list at the right location (to keep the list sorted!). Duplicates must be rejected: the function returns false in this case, true otherwise. A calling statement for this function is given below:
bool inserted = insertNode(head, dataIn);
Explanation / Answer
void insertNode(struct Node** head_ref, struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.