Question

The code file is attached. Portion of the code is given (1, 2, 3, 4). You have to write the code for the remaining items (5, 6, 7).

#include <iostream>
using namespace std;
struct node 
{
   int data;
   node* next;
};

node* head=NULL;

void appendNode(int value)
{
        node *newNode, *curr;
        newNode = new node();
        newNode->data=value;
        newNode->next=NULL;
        if (!head)  
                head=newNode;
        else 
        {
                curr=head;
                while (curr->next)
                        curr = curr->next;
                curr->next = newNode;
        }
}

void insertNode(int value)
{
        node *newNode, *curr, *previous;
        newNode = new node();
        newNode->data = value;
        if (head==NULL) 
        {
                head = newNode;
                newNode->next = NULL;
        }       
        else 
        {
                curr = head;
                while (curr != NULL && curr->data < value) 
                {
                        previous = curr;
                        curr = curr->next;
                }
                if (previous == NULL)
                {       
                        head = newNode;
                        newNode->next = curr;
                }
                else 
                {       
                        previous->next = newNode;
                        newNode->next = curr;
                }
        }       
}

void deleteNode(int value)
{
        node *curr, *previous;
        if(!head)
           return;
        if (head->data == value)
        {
                curr = head->next;
                delete head;
                head = curr;
        }
        else
        {
                curr = head;
                while( curr != NULL && curr->data != value)
                {
                        previous=curr;
                        curr=curr->next;
                }               
                previous->next = curr->next;
                delete curr;
        }
        cout << "Value is deleted\n";

}

void displayList(void)
{ 
        node *curr;
        curr = head;
        while (curr != NULL)
        {
                cout << curr->data << " " ;
                curr = curr->next;
        }
        cout << "\n";
}

int     findMaxNode()
{
        int m;
        //complete the code here
        return m;
}

int     searchItem(int value)
{
        int f;
        //complete the code here
        return f;
}

int     countNodes()
{
        int c;
        //complete the code here
        return c;
}

int main()
{
        int choice;
        int x;
        do
        {
                system("cls");
                cout << "1. Append a node" << "\n";
                cout << "2. Insert a node" << "\n";
                cout << "3. Delete a node" << "\n";
                cout << "4. Display the linked list" << "\n";
                cout << "5. Find the maximum node" << "\n";
                cout << "6. Search for a node" << "\n";
                cout << "7. Count the number of the nodes " << "\n";
                cout << "8. Exit" << "\n";
                cout << "Enter your choice(1-8):";
                cin >> choice;
                switch(choice)
                {
                        case 1:
                        cout << "Enter a value:";
                        cin >> x;
                        appendNode(x);
                        cout << "Value is appeneded\n";
                        break;

                        case 2:
                        cout << "Enter a value to insert:";
                        cin >> x;
                        insertNode(x);
                        cout << "Value is inserted\n";
                        break;

                        case 3:
                        cout << "Enter a value to delete:";
                        cin >> x;
                        deleteNode(x); 
                        break;

                        case 4:
                        displayList();
                        break;
                        
                        case 5:
                        int max;
                        max = findMaxNode();
                        cout << "Maximum is :" << max << endl;
                        break;

                        case 6:
                        cout << "Enter value to search for\n";
                        cin >> x;
                        int flag;
                        flag= searchItem(x);
                        if(flag==1)
                                cout << "Found\n";
                        else
                                cout << "Not found\n";
                        break;
                
                        case 7:
                        int count;
                        count= countNodes();
                        cout<<"Number of nodes in the list is:" << count << endl;
                        break;
                }
                        
                system("pause");
                
        } while(choice!=8);
}

Answer 1

5)

To find the max of a node first assume the first element of the list as the maximum element. Next, traverse the entire list and see if the value of that node is greater than the current maximum. Update m with new maximum. If list is empty return -1 indicating list is empty hence no maximum

int findMaxNode()
{
int m;
node *cur;
cur=head;
if(cur==NULL)
{
return -1;
}
else
m=cur->data;
while (cur != NULL)
{
if(m<cur->data)
m=cur->data;
cur = cur->next;
}
return m;
}

6)

Simple traverse the entire list and see if data in node matches with search value.

int searchItem(int value)
{
int f=0;
node *cur;
cur=head;
while (cur != NULL)
{
if(cur->data==value)
{
f=1;
break;
}
cur = cur->next;
}
return f;
}

7)

To count the no of nodes simple maintain a counter while traveling across the nodes. Increment the value of the counter upon visiting each node.

int countNodes()
{
int c=0;
node *cur;
cur=head;
while (cur != NULL)
{
c++;
cur = cur->next;
}
return c;
}