Question

C++ We are to implement 8 small additional functions and 2 helper functions to a singly linked list.

1. removeSecondNode340 deletes the second node in the Linked Bag.

2. addEnd340 inserts the new node at the end of the Linked Bag.

3. getCurrentSize340Iterative counts the number of nodes in the Linked Bag iteratively.

4. getCurrentSize340Recursive counts the number of nodes in the Linked Bag recursively. Use 1 helper function: getCurrentSize340RecursiveHelper.  

5. IMMEDIATE RECURSION: getCurrentSize340RecursiveNoHelper counts the number of nodes in the Linked Bag recursively. This recursive function does not use any helper functions.

6. getFrequencyOf340Recursive recursively counts the number of times an entry appears in the Linked Bag. Use 1 helper function: getFrequencyOf340RecursiveHelper.

7. IMMEDIATE RECURSION: getFrequencyOf340RecursiveNoHelper recursively counts the number of times an entry appears in the Linked Bag. This recursive function does not use any helper functions.  

8. removeRandom340 removes a random entry from the Linked Bag.

Answer 1

#include<bits/stdc++.h>

int rand();

using namespace std;

struct node{

int data;

struct node *next;

};

void removeSecondNode340(struct node *root)

{

if(root==NULL||root->next==NULL)

{cout<<"List contain less than two element\n";

return;

}

struct node *temp;

temp=root->next->next;

root->next->next=NULL;

root->next=temp;

}

void addEnd340(struct node **root)

{

int item;

cout<<"Enter item to add:";

cin>>item;

struct node *temp=(struct node *)malloc(sizeof(struct node));

temp->data=item;

temp->next=NULL;

if(*root==NULL)

{

*root=temp;

return;

}

struct node *curr=*root;

while(curr->next!=NULL)

curr=curr->next;

curr->next=temp;

}

int getCurrentSize340Iterative(struct node *root)

{

int c=0;

struct node *temp=root;

while(temp!=NULL)

{

c++;

temp=temp->next;

}

return c;

}

void print(struct node *root)

{

struct node *temp=root;

while(temp!=NULL)

{

cout<<temp->data<<" ";

temp=temp->next;

}

cout<<endl;

}

int getCurrentSize340RecursiveNoHelper(struct node *root)

{

if(root==NULL)

return 0;

return (1+getCurrentSize340RecursiveNoHelper(root->next));

}

int getFrequencyOf340RecursiveHelper(int c,int entry,int key)

{

if(key==entry)

c++;

return c;

}

int getFrequencyOf340Recursive(struct node *root,int entry)

{

static int c=0;

if(root==NULL)

return c;

c=getFrequencyOf340RecursiveHelper(c,entry,root->data);

return getFrequencyOf340Recursive(root->next,entry);

}

int getFrequencyOf340RecursiveNoHelper(struct node *root,int entry)

{

if(root==NULL)

return 0;

if(root->data==entry)

{

return (1+getFrequencyOf340RecursiveNoHelper(root->next,entry));

}

else

{

return getFrequencyOf340RecursiveNoHelper(root->next,entry);

}

}

int removeRandom340(struct node **root)

{

int count=getCurrentSize340Iterative(*root);

if(count==0)

return -1;

int index=rand()%count+1;

struct node *temp=*root,*temp2;

if(index==1)

{

*root=temp->next;

temp->next=NULL;

return temp->data;

}

int counter=1;

temp2=temp;

while(counter<index)

{

temp2=temp;

temp=temp->next;

counter++;

}

temp2->next=temp->next;

temp->next=NULL;

return temp->data;

}

int getCurrentSize340RecursiveHelper(int c)

{

c++;

return c;

}

int getCurrentSize340Recursive(struct node *root)

{

static int c=0;

if(root==NULL)

return c;

c=getCurrentSize340RecursiveHelper(c);

return getCurrentSize340Recursive(root->next);

}

int main()

{

struct node *root=NULL;

int choice;

int c;

int entry;

do

{

cout<<"Enter choice";

cin>>choice;

switch(choice)

{

case 1:removeSecondNode340(root);

break;

case 2:addEnd340(&root);

break;

case 3:c=getCurrentSize340Iterative(root);

cout<<"Count = "<<c<<endl;

break;

case 4:c=getCurrentSize340Recursive(root);

cout<<"Size of the list "<<c<<endl;

break;

case 5:c=getCurrentSize340RecursiveNoHelper(root);

cout<<"Size of the list "<<c<<endl;

break;

case 6:

cout<<"Enter entry to see frequency:";

cin>>entry;

c=getFrequencyOf340Recursive(root,entry);

cout<<"Frequency of "<<entry <<" in list is "<<c<<endl;

break;

case 7:

cout<<"Enter entry to see frequency:";

cin>>entry;

c=getFrequencyOf340RecursiveNoHelper(root,entry);

cout<<"Frequency of "<<entry <<" in list is "<<c<<endl;

break;

case 8:c=removeRandom340(&root);

if(c==-1)

cout<<"there are no element in the list\n";

else

cout<<c <<" is removed from the list\n";

break;

case 10:print(root);

break;

default:choice=0;

}

}while(!choice==0);

return 0;

}