2. Given the algorithm for inserting new nodes into an ordered linked list (or a

Question

2. Given the algorithm for inserting new nodes into an ordered linked list (or a portion of the algorithm) in real code, be able to fill in the blanks bool MyLinkedList::Insert (ListNode *newNode) // Assume ListNode is a structure and contains the variable int key; // Assume the function returns true if it successfully inserts the nodee ListNode *back - NULL, *temp - head; if(headNULL) Check for inserting first node into an empty list return true; // Search for insert location while( ( ; // Advance to next node // Check for inserting at head of the list if( = head; // Insert at head of list head newNode; return true; else // Insert elsewhere in the list return true return false; // Should never get here

Explanation / Answer

Blank 1:

head = newNode /* head == NULL means that the list is empty. So just make the head pointer point to this new node and return. This newNode will become the only node in the list. */

Blank 2 & 3:

(temp->next!=NULL) && (temp->next->Key< newNode->Key)

/* Here we are trying to find the position where we want to insert the incoming node. For that, we need to find a node whose value is lesser than the incoming newNode and whose next node's value is greater than the newNode */

Blank 4:

temp = temp->next; // Move to next node

Blank 5:

back = temp; // storing the back node in back pointer

Blank 6:

head->Key >= newNode->Key /* Checking if first node itself is greater than the newNode, then newNode needs to be inserted in the beginning at head position */

Blank 7:

newNode->next = head // inserting the node at head

Blank 8 & 9:

newNode->next = back->next;

back->next = newNode;

// inserting the node in front of back pointer

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.