4. Given the algorithm for inserting new nodes into an ordered double linked lis
ID: 3595052 • Letter: 4
Question
4. Given the algorithm for inserting new nodes into an ordered double linked list (or a portion of the algorithm) in real code, be able to fill in the blanks. Note: There is no back pointer used in this function. bool MyDoubleLinkedList::Insert(ListNode newNode) // Assume ListNode is a structure and contains the variable int key / and ListNode *prev, *nexti /7 Assume the function returns true if it successfully inserts the node ListNode *temp = head; if(head == NULL) // Check for inserting first node into an empty list return true; else // Search for insert location while( // Check for inserting at head of the list if( return true; else if(( temp->next == NULL ) && (newNode->key > temp->key)) // Inserting at the tailExplanation / Answer
bool MyDoubleLinkedList::Insert(ListNode *newNode)
{
ListNode *temp = head;
// if the linked list is empty
// newNode becomes the new head of the linked list
if(head == NULL)
{
head = newNode;
return true;
}
else
{
// search for insert location
while( (temp->next != NULL ) && (temp->key < newNode->data) )
{
temp = temp->next;
}
// check for inserting at the head of the list
if( temp == head )
{
newNode->next = temp;
temp->prev = newNode;
head = newNode;
}
// insert at the tail
else if((temp->next == NULL) && (newNode->key > temp->key))
{
temp->next = newNode;
newNode->prev = temp;
}
else
{
newNode->next = temp->next;
newNode->prev = temp;
temp->next = newNode;
newNode->next->prev = newNode;
}
return true;
}
return false;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.