Question

C++ Recursion, Change the delete_node function in the header file to a recursive delete_node function, main is already set.

Hint: It might be helpful to modify the function so that it uses a separate recursive function to perform whatever processing is needed.

//////////////////////////////////////////////////////////////header.h//////////////////////////////////////////////////////////////////////////////////////////////

#ifndef HEADER_H_
#define HEADER_H_

#include <iostream>
using namespace std;

template <class T>
class LL
{
private:
   struct LLnode
   {
       LLnode* fwdPtr;
       T theData;
   };
   LLnode* head;

public:
   LL();   
   void push_front(T);
   void push_back(T);
   void display_list();
   bool search_list(T);
   bool delete_node(T);

};

template <class T>
LL<T> :: LL()
{
   head = nullptr;
}

template <class T>
void LL<T> :: push_front(T numb)
{
LLnode* ptr = new LLnode;
ptr -> theData = numb;
ptr -> fwdPtr = head;
head = ptr;
}

template <class T>
void LL<T> :: push_back(T numb)
{
LLnode* ptr = new LLnode;
ptr -> theData = numb;
ptr -> fwdPtr = nullptr;
if(head == nullptr)
{
head = ptr;
}
else
{
LLnode* temp = head;
while(temp -> fwdPtr != nullptr)
{
temp = temp-> fwdPtr;
}
temp -> fwdPtr = ptr;
}
}

template <class T>
void LL<T> :: display_list()
{
int counter = 0;
LLnode* ptr = head;

if (head == nullptr)
cout << "The list is empty" << endl;

while (ptr != nullptr)
{
cout << "node " << counter << " data -> " << ptr->theData << endl;
counter++;
ptr = ptr -> fwdPtr;
}
}

template <class T>
bool LL<T> :: search_list(T numb)
{
   for(LLnode* temp = head;temp != nullptr;temp = temp -> fwdPtr)
   {
       if(temp -> theData == numb)
       {
           return true;
       }
   }
   return false;
}

template<class T>
bool LL<T> :: delete_node(T numb) //////////////////////////////////////delete_node
{
   if(head == nullptr)
   {
       return false;
   }
   if(head -> theData == numb)
   {
       LLnode* temp = head -> fwdPtr;
       delete head;
       head = temp;
       return true;
   }
   LLnode* temp = head;
   while(temp -> fwdPtr != nullptr)
   {
       if(temp -> fwdPtr -> theData == numb)
       {
           LLnode* nextNode = temp -> fwdPtr -> fwdPtr;
           delete temp -> fwdPtr;
           temp -> fwdPtr = nextNode;
           return true;
       }
       temp = temp -> fwdPtr;
   }
   return false;
}

#endif

/////////////////////////////////////////////////////////////////////////////////////////////////////////////main.cpp///////////////////////////////////////////////////////////////////

#include <iostream>
using namespace std;
#include "header.h"

int main()

{

   LL <string> ll2;

   ll2.push_front("33333");
   ll2.push_front("22222");
   ll2.push_front("11111");
   ll2.push_back("44444");
   ll2.push_back("55555");
   ll2.push_back("66666");
   cout << "main: now trying to display ll2 after 6 push's" << endl;
   ll2.display_list();
   cout << "main: now searching for node 44444" << endl;
   if (ll2.search_list("44444"))
   {
       cout <<"main: found node 44444" << endl;
   }
   else
   {
       cout << "main: did not find node 44444" << endl;
   }
   cout << "main: now searching for node 44445" << endl;
   if (ll2.search_list("44445"))
   {
       cout <<"main: found node 44445" << endl;
   }
   else
   {
       cout << "main: did not find node 44445" << endl;
   }
   cout << "main: now trying to delete node 44444" << endl;
   if (ll2.delete_node("44444"))
   {
       cout <<"main: node 44444 deleted" << endl;
   }
   else
   {
       cout << "main: did not find 44444 for delete" << endl;
   }
   if (ll2.search_list("44444"))
   {
       cout <<"main: searched for 44444 after delete, found" << endl;
   }
   else
   {
       cout << "main: searched for 44444 after delete, not found" << endl;
   }
   cout << "main: displaying whole list after delete 44444" << endl;
   ll2.display_list();
   cout << "main: now trying to delete node 11111" << endl;
   if (ll2.delete_node("11111"))
   {
       cout <<"main: node 11111 deleted" << endl;
   }
   else
   {
       cout << "main: did not find node 11111 for delete" << endl;
   }
   cout << "main displaying whole list after delete 11111" << endl;
   ll2.display_list();

   return 0;
}

Answer 1

Modified code given below. Please do rate the answer if it helped. Thank you.

header.h
------

#ifndef HEADER_H_
#define HEADER_H_

#include <iostream>
using namespace std;

template <class T>
class LL
{
private:
struct LLnode
{
LLnode* fwdPtr;
T theData;
};
LLnode* head;
LLnode* delete_node_helper(LLnode* n, T numb, bool &found);
public:
LL();   
void push_front(T);
void push_back(T);
void display_list();
bool search_list(T);
bool delete_node(T);

};

template <class T>
LL<T> :: LL()
{
head = nullptr;
}

template <class T>
void LL<T> :: push_front(T numb)
{
LLnode* ptr = new LLnode;
ptr -> theData = numb;
ptr -> fwdPtr = head;
head = ptr;
}

template <class T>
void LL<T> :: push_back(T numb)
{
LLnode* ptr = new LLnode;
ptr -> theData = numb;
ptr -> fwdPtr = nullptr;
if(head == nullptr)
{
head = ptr;
}
else
{
LLnode* temp = head;
while(temp -> fwdPtr != nullptr)
{
temp = temp-> fwdPtr;
}
temp -> fwdPtr = ptr;
}
}

template <class T>
void LL<T> :: display_list()
{
int counter = 0;
LLnode* ptr = head;

if (head == nullptr)
cout << "The list is empty" << endl;

while (ptr != nullptr)
{
cout << "node " << counter << " data -> " << ptr->theData << endl;
counter++;
ptr = ptr -> fwdPtr;
}
}

template <class T>
bool LL<T> :: search_list(T numb)
{
for(LLnode* temp = head;temp != nullptr;temp = temp -> fwdPtr)
{
if(temp -> theData == numb)
{
return true;
}
}
return false;
}

template<class T>
typename LL<T>::LLnode* LL<T>:: delete_node_helper(LLnode* n, T numb, bool &found)
{
   if(n == nullptr)
       return n;
  
   if(n->theData == numb)
   {
       found = true;
       LLnode* next = n->fwdPtr;
       delete n;
       return next;
   }
   else
   {
       n->fwdPtr = delete_node_helper(n->fwdPtr, numb, found);
       return n;
   }

}

template<class T>
bool LL<T> :: delete_node(T numb) //////////////////////////////////////delete_node
{
bool found = false;
head = delete_node_helper(head, numb, found);
return found;
}

#endif

output
---
main: now trying to display ll2 after 6 push's
node 0 data -> 11111
node 1 data -> 22222
node 2 data -> 33333
node 3 data -> 44444
node 4 data -> 55555
node 5 data -> 66666
main: now searching for node 44444
main: found node 44444
main: now searching for node 44445
main: did not find node 44445
main: now trying to delete node 44444
main: node 44444 deleted
main: searched for 44444 after delete, not found
main: displaying whole list after delete 44444
node 0 data -> 11111
node 1 data -> 22222
node 2 data -> 33333
node 3 data -> 55555
node 4 data -> 66666
main: now trying to delete node 11111
main: node 11111 deleted
main displaying whole list after delete 11111
node 0 data -> 22222
node 1 data -> 33333
node 2 data -> 55555
node 3 data -> 66666