Question

C++

Need to add the following functions to my templatized class linked list. (main is already set to accommodate the functions below)

--void destroy_list () deletes each node in the list, and resets the header to nullptr

--bool search_list (key value) searches the list for a node with the given key. Returns true if found, false if not.

--bool delete_node (key value) deletes the node which contains the given key. If there is more than one node with the same key, delete_node deletes the first occurrence. Returns true if delete successful, false if the node was not found.

#ifndef headDER_H_
#define headER_H_
#include <iostream>
using namespace std;

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

public:
   void push_front(T);
   void push_back(T);
   void display_list();
   int list_length();
   void destroy_list();
   bool search_list(T);
   LL();
};

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

template <class T>
void LL<T>::push_back(T str)
{
LLnode *ptr=new LLnode;
ptr->theData=str;
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>
int LL<T>::list_length()
{
int counter = 0;
LLnode *ptr = head;

while (ptr != nullptr)
{
counter++;
ptr = ptr->fwdPtr;
}
return counter;
}
template <class T>
LL<T>::LL()
{
   head=nullptr;
}

#endif /* headER_H_ */

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

int main() {

   LL <string> ll1;
   cout << "main: length of empty list - " << ll1.list_length() << endl;
   cout << "main: trying to display empty list 1" << endl;
   ll1.display_list();
   cout << "main: trying to display initial size of ll1 - " << ll1.list_length() << endl;
   ll1.push_front("aaaaa");
   ll1.push_back("bbbbb");
   ll1.push_front("before aaaaa");
   ll1.push_back("after bbbbb");
   cout << "main: length of ll1 after 4 pushes - " << ll1.list_length() << endl;
   cout << "main: now trying to display ll1 after 4 push's" << endl;
   ll1.display_list();
   cout << "main: displaying final size of ll1 - " << ll1.list_length() << endl;
   ll1.destroy_list();
   cout << "main: displaying size of list 1 after destroy - " << ll1.list_length() << endl;
   cout << endl;

   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();
   ll2.destroy_list();

   return 0;
}

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Note: Only header.h is attached since it is the only file that is modified.

//updated code for header.h file

#ifndef headDER_H_

#define headER_H_

#include <iostream>

using namespace std;

template <class T>

class LL {

private:

    struct LLnode {

        LLnode* fwdPtr;

        T theData;

    };

    LLnode* head;

public:

    void push_front(T);

    void push_back(T);

    void display_list();

    int list_length();

    LL();

    //prototypes of newly implemented methods

    void destroy_list();

    bool search_list(T);

    bool delete_node (T);

   

};

template <class T>

void LL<T>::push_front(T str)

{

    LLnode* ptr = new LLnode;

    ptr->theData = str;

    ptr->fwdPtr = head;

    head = ptr;

}

template <class T>

void LL<T>::push_back(T str)

{

    LLnode* ptr = new LLnode;

    ptr->theData = str;

    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>

int LL<T>::list_length()

{

    int counter = 0;

    LLnode* ptr = head;

    while (ptr != nullptr) {

        counter++;

        ptr = ptr->fwdPtr;

    }

    return counter;

}

template <class T>

LL<T>::LL()

{

    head = nullptr;

}

//implementations of new methods

template <class T>

void LL<T>::destroy_list()

{

                //looping as long as head is not nullptr

    while(head!=nullptr){

                //taking a reference to next of head node

                LLnode *temp=head->fwdPtr;

                //deleting head node

                delete head;

                //assigning next node to head

                head=temp;

                }

}

template <class T>

bool LL<T>::search_list(T key)

{

                //using a for loop, looping through each node in linked list

    for(LLnode* temp=head;temp!=nullptr;temp=temp->fwdPtr){

                //comparing data field with key

                if(temp->theData==key){

                                //found

                                return true;

                                }

                }

                //not found

                return false;

}

template <class T>

bool LL<T>::delete_node(T key)

{

                //if head node is empty, returning false

    if(head==nullptr){

                return false;

                }

                // checking if head node contains the value to be deleted,

                if(head->theData==key){

                                //storing next of head node

                                LLnode* temp=head->fwdPtr;

                                //deleting head node

                                delete head;

                                //assigning next to head node

                                head=temp;

                                //deletion is successful

                                return true;

                }

                //taking a reference of head

                LLnode* temp=head;

                //looping as long as next of temp is not nullptr

                while(temp->fwdPtr!=nullptr){

                                //checking if next node is the node to be deleted

                                if(temp->fwdPtr->theData==key){

                                               //storing next of next node

                                               LLnode* next=temp->fwdPtr->fwdPtr;

                                               //deleting next node

                                               delete temp->fwdPtr;

                                               //storing previously saved next of next node as the next of temp

                                               temp->fwdPtr=next;

                                               return true; //success

                                }

                                //advancing temp

                                temp=temp->fwdPtr;

                }

                return false; //not found

}

#endif /* headER_H_ */

/*OUTPUT of given test code*/

main: length of empty list - 0

main: trying to display empty list 1

The list is empty

main: trying to display initial size of ll1 - 0

main: length of ll1 after 4 pushes - 4

main: now trying to display ll1 after 4 push's

node 0 data -> before aaaaa

node 1 data -> aaaaa

node 2 data -> bbbbb

node 3 data -> after bbbbb

main: displaying final size of ll1 - 4

main: displaying size of list 1 after destroy - 0

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