You are provided with a partial implementation of a templated singly-linked list in LinkedList.h, with some...

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 */

Expert Solution

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.. :))))

venereology answered 1 year ago

Give a complete implementation of the queue ADT using a singly linked list that includes a...

Give a complete implementation of the queue ADT using a singly linked list that includes a header sentinel (in Python).

You are given a singly linked list. Write a function to find if the linked list...

You are given a singly linked list. Write a function to find if the linked list contains a cycle or not. A linked list may contain a cycle anywhere. A cycle means that some nodes are connected in the linked list. It doesn't necessarily mean that all nodes in the linked list have to be connected in a cycle starting and ending at the head. You may want to examine Floyd's Cycle Detection algorithm. /*This function returns true if given...

Q1) In the implementation of Singly linked list we had an integer variable called size that...

Q1) In the implementation of Singly linked list we had an integer variable called size that keeps track of how many elements in the list. Also, we have a reference “tail” that points to the last node in the list. You are asked to re-implement the concept of singly linked list without using variable size, and without using reference “tail”. a) What are the methods of the main operation of singly linked list that need to be changed? Rewrite them...

Data Structures in Java In the following Singly Linked List implementation, add the following methods, and...

Data Structures in Java In the following Singly Linked List implementation, add the following methods, and write test cases in another java file to make sure these methods work. - Write a private method addAfter(int k, Item item) that takes two arguments, an int argument k and a data item, and inserts the item into the list after the K-th list item. - Write a method removeAfter(Node node) that takes a linked-list Node as an argument and removes the node...

In C++: Provide a linked implementation of a deque and name it LinkedDeque (use singly linked...

In C++: Provide a linked implementation of a deque and name it LinkedDeque (use singly linked list). It can be a template/generic class or you can set it up with a certain data type. Use a test driver to try out your LinkedDeque by adding and removing values from both ends.

I've provided a Node class that implements a node of a simple singly-linked list (with .value...

I've provided a Node class that implements a node of a simple singly-linked list (with .value and .next fields), and an empty LinkedList class. Your task is to implement LinkedList.sort(l), where given the node l as the head of a singly-linked list, LinkedList.sort(l) sorts the nodes in the list into ascending order according to the values in the .value field of each node. Your implementation should do an in-place update of the list. It is ok to use a simple...

I was supposed to conver a singly linked list to a doubly linked list and everytime...

I was supposed to conver a singly linked list to a doubly linked list and everytime I run my program the output prints a bunch of random numbers constantly until I close the console. Here is the code. #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> struct node { int data; struct node *next; struct node *prev; }; //this always points to first link struct node *head = NULL; //this always points to last link struct node *tail = NULL;...

In C++, Implement the queue ADT with a singly linked list

Complete the provided partial C++ Linked List program. Main.cpp is given and Link list header file...

Complete the provided partial C++ Linked List program. Main.cpp is given and Link list header file is also given. The given testfile listmain.cpp is given for demonstration of unsorted list functionality. The functions header file is also given. Complete the functions of the header file linked_list.h below. ========================================================= // listmain.cpp #include "Linked_List.h" int main(int argc, char **argv) { float f; Linked_List *theList; cout << "Simple List Demonstration\n"; cout << "(List implemented as an Array - Do...

Using C++, Create a singly Linked List of patients list so that you can sort and...

Using C++, Create a singly Linked List of patients list so that you can sort and search the list by last 4 digits of the patient's Social Security number. Implement Node insertion, deletion, update and display functionality in the Linked List. Each patient's record or node should have the following data: Patient Name: Age: Last 4 digits of Social Security Number: The program should first display a menu that gives the user the option to: 1) Add a Patient's record...

Question