4. Given the algorithm for inserting new nodes into an ordered double linked lis

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, next Assume the function returns true if it successfully inserts the node ListNode emp 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 tail else Insert elsewhere in the list Set newNode's pointers Set next pointer for node before newNode Set prev pointer for node after newNode return true; return false;

Explanation / Answer

bool MyDoublyLinkedList::Insert(ListNode *newNode)
{
    // Assume ListNode is a structure and contains the variable int key;
    // and ListNode *prev, *next;
    // Assume the function returns true if it successfully inserts the node.
    ListNode *temp = head;   //Initializes the temp pointer to the start of the list.
    if(head == NULL)   //Check for inserting first node into an empty list.
    {  
       head = newNode;   //Make this node as the first node.
       return true;   //Confirming the node has been inserted.
    }
    else   //If there is atleast one node.
    {
       //Search for insert location
       while((temp->next != NULL) && (temp->key < newNode->key))   //Till you either reach the end of list, or the position to insert.
           temp = temp->next;   //Keep moving forward.
      
       //Check for inserting at head of the list.
       if(temp == head)   //If the element should be inserted at first position.  
       {
          newNode->next = head;   //Make the newNode->next point to then first node.
          head->prev = newNode;   //Make the then first node->prev point to newNode.
          head = newNode;           //Make head point to newNode
          return true;           //Confirming the node has been inserted.
       }
       else if((temp->next == NULL) && (newNode->key > temp->key)) //If the node should be inserted in the last position.
       {
          //Inserting at the tail.
          newNode->prev = temp;   //Make the newNode->prev point to then last node.
          temp->next = newNode;//Make the then last node -> next point to newNode.
       }
       else   //Insert elsewhere in the list.
       {
          //Set newNode's pointers.
          newNode->prev = temp;
          newNode->next = temp->next;
          //Set next pointer for node before the newNode.
          temp->next = newNode;
          //Set prev pointer for node after newNode.
          newNode->next->prev = newNode;
       }
       return true;
    }
    return false;
}

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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