Question

Write the deleteNode() member function, which is also given in our textbook implementation. This function takes a const T& as its parameter, which is the value of an item to search for and delete. Thus the first part of this function is similar to the search() function, in that you first have to perform a search to second the item. But once found, the node containing the item should be removed from the list (and you should free the memory of the node). This function is only guaranteed to find the first instance of the item and delete it, if the item appears multiple times in the list, the ones after the first one will still be there after the first item is removed by this function. This function should return a LinkedListItemNotFoundException if the item asked for is not found. The LinkedListItemNotFoundException class has already been defined for you in the starting template header file.

Here is the cpp for main and LinkedList - https://paste.ofcode.org/37gZg5p7fiR243AD4sD5ttU

Answer 1

deletenode() function to be implemented:

template <class T>
void LinkedList<T>:: deleteNodet(const T& Item)
{
    /*Itr pointer will be used to iterate the whole linked list
     to find the element which is to be deleted.*/
   
   Node<T>* Itr = first;
  
      //If the first element is storing the value to be deleted.
    //Make first point to the second element in the Linked List
    // and free the memory.
    if (Itr != NULL && Itr->info == Item)
    {
        first = Itr->link;  
        free(Itr);             
        return;
    }
  
    /*This pointer will point to the element which will be present just before the
     element which is to be deleted.*/
   Node<T>* previous;

    //Iterate the whole linked list to find the element which is to be deleted.
    //Update previous pointer accordingly.
   while (Itr != NULL && Itr->info != Item)
    {
        previous = Itr;
        Itr = Itr->link;
    }
  
   // If element is not found in the whole linked list.
   if (Itr == NULL)
        throw(LinkedListItemNotFoundException());
      
    //If value to be deleted is found at Last Element
    //Make last point to previous and free the memory.
     if(Itr==last && Itr->info ==Item)
     {
         last=previous;
         free(Itr);
         return;
     }
      
    //If element is found at any other node. Un-link that node for the linked list.
   previous->link =Itr->link;

   //Free the memory of the node.
   free(Itr);
   
}

Explanation:

In order to delete an element from a Linked List follow the following steps:-

1. Declare a pointer which will be used to iterate the Linked List.
2. Check if the first node stores the element which is to be deleted.If yes, then make the first point to the second element in the Linked List and free the memory occupied by first node.
3. If No, then declare another Pointer which will keep track of the element previous to the one which is to be deleted.
4. Iterate the whole Linked List to find the element: Item.
5. If the element is not found anywhere in the linked list then throw the LinkedListItemNotFoundException.
6. If the element is stored in the last node then make the last point to the previous node and free up the memory.
7. If the element is stored by any other node then just separate the node from the linked list.

Separating the node from the linked list will be more clear by the following diagram:-