Question

You are provided with a partial implementation of a templated singly-linked list in LinkedList.h, with some missing functionality. It contains a templated Node class and a templated LinkedList class. Do not modify the class definitions.

The linked list class contains the following methods:

• LinkedList – Constructor of a linked list with a head pointing to null (implemented).

• ~LinkedList – Destructor of a linked list.

• deleteFromHead – Removes and returns content of the first node of the list. (If the list is empty, does nothing.)

• deleteFromTail – Removes and returns content of last node of the list. (If the list is empty, does nothing.)

• deleteNode – Removes node with provided data from the list.

• InsertToHead – Inserts node with provided data at the head (implemented).

• InsertToTail – Inserts node with provided data at the tail. • getSize – Returns the number of nodes in the linked list.

• print - Prints the linked list (implemented).

Notice that while the declaration and implementation of classes are typically split between .cpp and .h files, some compilers cannot handle templates in separate files, which is why we include both the declaration and implementation in a single .h file. The main.cpp file consists of sample test code for each of the tasks below. Your code, which should be added to the provided LinkedList.h will be compiled and run with variations of this file. Submit your modified LinkedList.h file only

LinkedList.h:

#ifndef LinkedList_h
#define LinkedList_h

#include <iostream>

using namespace std;

template <class T = int>
class Node {
public:
    Node();                                         // default constructor
    Node(const T& data, Node<T>* next = nullptr);   // donstructor
    T data;                                         // node data
    Node<T>* next;                                  // node next pointer
};

template <class T = int>
class LinkedList {
public:
    LinkedList();                                   // constructor
    ~LinkedList();                                  // destructor
    T deleteFromHead();                             // removes and returns content of head
    T deleteFromTail()                              // removes and returns content of tail
    void deleteNode(T data)                         // removes node with specified data
    void InsertToHead(T data);                      // insert node with data at the head
    void InsertToTail(T data);                      // insert node with data at the tail
    int getSize();                                  // returns size of linked list
    void print();                                   // prints linked list
private:
    Node<T>* head;                                  // head of linked list
};


/******* From here down is the content of the LinkedList.cpp file: ***********************/

 /* Implementation of Node */

 // default constructor
 template<class T>
 Node<T>::Node()
 {
 }
 
 // constructor
 template<class T>
 Node<T>::Node(const T& data, Node<T>* next)
 {
     this->data = data;
     this->next = next;
 }
 
 /* Implementation of linked list */

 // constructor
 template <class T>
 LinkedList<T>::LinkedList()
 {
     head = nullptr;
 }

 // destructor
 template <class T>
 LinkedList<T>::~LinkedList()
 {
    /*** to be implemented ***/
 }

 template <class T>
 T LinkedList<T>::deleteFromHead()
 {
    /*** to be implemented ***/
 }


 template <class T>
 T LinkedList<T>::deleteFromTail()
 {
    /*** to be implemented ***/
 }
 

 template <class T>
 void LinkedList<T>::deleteNode(T data)
 {
    /*** to be implemented ***/
 }
 

 template <class T>
 void LinkedList<T>::InsertToHead(T data)
 {
     Node<T> * newNode = new Node<T>(data, nullptr);
     
     if (head == nullptr)
         head = newNode;
     else
     {
         newNode->next = head;
         head = newNode;
     }
 }


 template <class T>
 void LinkedList<T>::InsertToTail(T data)
 {
     /*** to be implemented ***/
 }


 template <class T>
 int LinkedList<T>::getSize()
 {
     /*** to be implemented ***/
 }


 template <class T>
 void LinkedList<T>::print()
 {
     if (head == nullptr)
     {
         cout << "Linked list is empty" << endl;;
         return;
     }
     
     cout << head->data << " ";
     
     if (head->next == nullptr)
     {
         cout << endl;
         return;
     }
 
     Node<T>* currNode = head->next;
     Node<T>* prevNode = head;
 
     
     while (currNode->next != nullptr)
     {
         cout << currNode->data << " ";
         prevNode = currNode;
         currNode = currNode->next;
     }
 
     cout << currNode->data << endl;
     return;
 }
     
     
#endif /* LinkedList_h */

Answer 1

Hello there,
Let's fill those gaps..

 // default constructor
 template<class T>
 Node<T>::Node()
 {
 }
 
 // constructor
 template<class T>
 Node<T>::Node(const T& data, Node<T>* next)
 {
     this->data = data;
     this->next = next;
 }
 
 /* Implementation of linked list */

 // constructor
 template <class T>
 LinkedList<T>::LinkedList()
 {
     head = nullptr;
 }

 // destructor
 template <class T>
 LinkedList<T>::~LinkedList()
 {
    /*** to be implemented ***/

if(head!=nullptr)
{     
     Node<T> *current = head;
     Node<T> *next;
     while(current ! = nullptr)
     {
      next = current->next;
      delete current;
      current = next;
     }
}

}

 template <class T>
 T LinkedList<T>::deleteFromHead()
 {
    /*** to be implemented ***/
   Node<T> *ptr; 
   if(head == nullptr)
     cout<<"List is Empty..";
   else
     {
      ptr=head;
      head = head->next;
      delete ptr;
     }     
 
 }
 template <class T>
 T LinkedList<T>::deleteFromTail()
 {
    /*** to be implemented ***/
   if(head==nullptr)
      cout<<"List is Empty..";
   else
   {

     Node<T> *fast;
     Node<T> *slow;
     
    fast = head;
    if(fast->next == nullptr)   //If a Linked List contain only a single node.. 
     {
        head = nullptr;
         delete head;
     }        
     else
      {
      while(fast->next != nullptr)
       {
             slow = fast;
             fast = fast->next;
       }
       slow->next = nullptr;
       delete fast;
      }

  }
   
 }
 
 template <class T>
 void LinkedList<T>::deleteNode(T data)
 {
    /*** to be implemented ***/
     int n;
     cin>>n;  //node to be deleted..    
     if(head==nullptr)
       cout<<"List is Empty..";
     else if(head->data==n)      //if node is to be deleted is first node from the front...
     {
        Node<T> *temp=head;
        head=head->next;
        delete temp;
     } 
     else 
     {
      Node<T> *fast;
      Node<T> *slow;
      fast = head;
          
      while(fast->next != nullptr)
      {
        slow = fast;
        if(fast->data==n)
          {
             break;
          }
        fast = fast->next;
      }

 Node<T> *t;
 t =  slow->next;  
 slow->next = fast->next;
 delete t;
 }
 
}
 

 template <class T>
 void LinkedList<T>::InsertToHead(T data)
 {
     Node<T> * newNode = new Node<T>(data, nullptr);
     
     if (head == nullptr)
         head = newNode;
     else
     {
         newNode->next = head;
         head = newNode;
     }
 }


 template <class T>
 void LinkedList<T>::InsertToTail(T data)
 {
     /*** to be implemented ***/
     Node<T> * newNode = new Node<T>(data, nullptr);
     if(head==nullptr)
       head = newNode;
     else
   {
     Node<T> *ptr=head;
     while(ptr->next!=nullptr)
     {
      ptr=ptr->next;
     }
   ptr->next = newNode;
}

}


 template <class T>
 int LinkedList<T>::getSize()
 {
     /*** to be implemented ***/
  if(head == nullptr)
    return 0;
  Node<T> ptr=head;
  int len=0;
  while(ptr!=nullptr)
   {
         ptr = ptr->next;
         len++;
  }     
  return len;
 }


 template <class T>
 void LinkedList<T>::print()
 {
     if (head == nullptr)
     {
         cout << "Linked list is empty" << endl;;
         return;
     }
     
     cout << head->data << " ";
     
     if (head->next == nullptr)
     {
         cout << endl;
         return;
     }
 
     Node<T>* currNode = head->next;
     Node<T>* prevNode = head;
 
     
     while (currNode->next != nullptr)
     {
         cout << currNode->data << " ";
         prevNode = currNode;
         currNode = currNode->next;
     }
 
     cout << currNode->data << endl;
     return;
 }
     
     
#endif /* LinkedList_h */

Thanks for reaching out to us..

Keep asking and keep learning.. :))))