Question

In: Computer Science

1.Please write a C++ program that counts the nodes in a linked list with the first...

1.Please write a C++ program that counts the nodes in a linked list with the first node pointed to by first. Also please explain. 2. Write a program to determine the average of a linked list of real numbers with the first node pointed to by first. 3. Determine the computing times of the algorithms in question 1 and 4. Write a program to insert a new node into a linked list with the first node pointed to by first after the nth node in this list for a given integer n. 5. Write a program to delete the nth node in a linked list with the first node pointed to by first, where n is a given integer.

Solutions

Expert Solution

Answer 1

In the structure, we have two members:

  • num -> A double type variable to store a real number
  • next -> A pointer to Node type to store the location of next node in the list

Next we need a list to be able to count it. This function adds a node at the end of the list.

To do this:

  1. We allocate memory to a new_node.
  2. Take the real number from the user, in input_num.
  3. Store the number in the node.
  4. Check if this is the first node to be added to list:
    • If this is first node, then mark this new_node as the first node of the list, *head. (We are using double pointer for head, hence it will be reflected in main() too.)
    • If not, then:
      1. Initialize a temporary node by *head.
      2. Now iterate the list to reach the last node of the list, such that temp points to the last node.
      3. Now add the node to list, by assigning new_node to next pointer of the last node, temp.

Now we define a helper function, printList() to see the current linked list.

Here, we use a single pointer for head. This means any change to head does not reflect in main().

Now this is the required function for question 1, countNode().

To do this, we initialize a count variable to zero. Then we iterate the list, and in each iteration we increment count by one. As soon as the list ends, we get the number of nodes in count. Then we return count to main().

Here is the entire program:

#include <iostream>

using namespace std;

/*
Defining the structure for Node
*/
struct Node
{
        double num;     //      To store the real number
        Node *next;     //      To store pointer to next node
};

/*
Function to add a node to the list
Arguments:
        **head -> Double pointer to the first node of the list
*/
int addNode(Node **head)
{
        Node *new_node = NULL;  //      The new node
        double input_num;               //      Get the real number from user

        //      Defining the new node
        new_node = new Node;
        cout << "Enter a number: ";
        cin >> input_num;
        new_node->num = input_num;
        new_node->next = NULL;

        //      Case when first node is added to list, i.e. the when list is empty
        if(*head == NULL)
        {
                *head = new_node;
        }
        //      Otherwise
        else
        {
                Node *temp = *head;

                //      Iterate to the last node in list
                while(temp->next != NULL)
                        temp = temp->next;

                //      Add the new node to the list
                temp->next = new_node;
        }

        return 0;
}

/*
Function to count the number of nodes in the list
Arguments:
        *head -> pointer to the first node in the list
Return value:
        The count of nodes in the list.
*/
int countNode(Node *head)
{
        int count = 0;

        //      Iterating the entire list
        while(head != NULL)
        {
                //      Increasing the count of nodes by one in each iteration
                ++count;
                head = head->next;
        }

        return count;
}

/*
Function to print the list
Arguments:
        *head -> Pointer to the first node in the list
*/
int printList(Node *head)
{
        cout << "The list is:" << endl;

        while(head != NULL)
        {
                cout << head->num << " -> ";
                head = head->next;
        }
        cout << "NULL" << endl;

        return 0;
}

int main()
{
        Node *first = NULL;
        int choice, count;
        double avg;

        //      Displaying the options available to the user
        cout << "MENU" << endl;
        cout << "1. Add node" << endl;
        cout << "2. Count nodes" << endl;
        cout << "3. Print the list" << endl;
        cout << "4. Exit" << endl;

        do
        {
                //      Take choice from user
                cout << "Enter your choice: ";
                cin >> choice;

                //      Do task according to the choice
                switch(choice)
                {
                        case 1:
                        addNode(&first);
                        break;

                        case 2:
                        count = countNode(first);
                        cout << "Number of nodes in the list: " << count << endl;
                        break;

                        case 3:
                        printList(first);
                        break;

                        case 4:
                        cout << "Bye!!" << endl;
                        break;

                        default:
                        cout << "Sorry!! No such choice. Please try again." << endl;
                }
        }while(choice != 4);

        return 0;
}

Sample output:

Answer 2

To calculate the average of real numbers in the list, we iterate through the list. In each iteration, we add the real number (in the node) to the variable sum. Also, we increment the count variable by one. At the end, we return sum/count.

Here is now the final code for question 2:

#include <iostream>

using namespace std;

/*
Defining the structure for Node
*/
struct Node
{
        double num;     //      To store the real number
        Node *next;     //      To store pointer to next node
};

/*
Function to add a node to the list
Arguments:
        **head -> Double pointer to the first node of the list
*/
int addNode(Node **head)
{
        Node *new_node = NULL;  //      The new node
        double input_num;               //      Get the real number from user

        //      Defining the new node
        new_node = new Node;
        cout << "Enter a number: ";
        cin >> input_num;
        new_node->num = input_num;
        new_node->next = NULL;

        //      Case when first node is added to list, i.e. the when list is empty
        if(*head == NULL)
        {
                *head = new_node;
        }
        //      Otherwise
        else
        {
                Node *temp = *head;

                //      Iterate to the last node in list
                while(temp->next != NULL)
                        temp = temp->next;

                //      Add the new node to the list
                temp->next = new_node;
        }

        return 0;
}

/*
Function to calculate the average of the nodes
Arguments:
        *head -> pointer to the first node in the list
Return value:
        The average of the nodes in the list.
*/
double avgNodes(Node *head)
{
        int count = 0;  //      Variable to store the count of nodes
        double sum = 0; //      Variable to store the sum of nodes

        while(head != NULL)
        {
                ++count;
                sum += head->num;
                head = head->next;
        }

        //      Calculating the average
        double avg = (double)sum / count;

        return avg;
}

/*
Function to print the list
Arguments:
        *head -> Pointer to the first node in the list
*/
int printList(Node *head)
{
        cout << "The list is:" << endl;

        while(head != NULL)
        {
                cout << head->num << " -> ";
                head = head->next;
        }
        cout << "NULL" << endl;

        return 0;
}

/*
Driver function
*/
int main()
{
        Node *first = NULL;
        int choice, count;
        double avg;

        //      Displaying the options available to the user
        cout << "MENU" << endl;
        cout << "1. Add node" << endl;
        cout << "2. Average of list" << endl;
        cout << "3. Print the list" << endl;
        cout << "4. Exit" << endl;

        do
        {
                //      Take choice from user
                cout << "Enter your choice: ";
                cin >> choice;

                //      Do task according to the choice
                switch(choice)
                {
                        case 1:
                        addNode(&first);
                        break;

                        case 2:
                        avg = avgNodes(first);
                        cout << "Average of list: " << avg << endl;
                        break;

                        case 3:
                        printList(first);
                        break;

                        case 4:
                        cout << "Bye!!" << endl;
                        break;

                        default:
                        cout << "Sorry!! No such choice. Please try again." << endl;
                }
        }while(choice != 4);

        return 0;
}

The output for the program is:

Answer 3

Now let's analyze the time complexity of countNode() and avgNodes().

For countNode():

We travel the whole list once to increase the count in eaach iteration. That means we iterate n times over a list of n nodes.

Hence, time complexity of countNode() is O(N).

For avgNodes():

We travel the whole list once to add each element to the variable sum, and increase count in each iteration. That means we iterate n times over a list of n nodes.

Hence, time complexity of avgNodes() is O(N).

Answer 4

In this, we want to enter node at a specified location.

For this, we first take a real number from the user and create a new_node using that. Then we ask the user for the position in which we want to insert this new_node.

If the postion entered by user can be access (either it already exist, or it is just one above the count of nodes (case when we insert at end of list)):

  • If yes, then check if we are inserting at the very start of list or not:
    • If we insert at start, then assign *head to next pointer of new_node, and assign new_node as the new *head.
    • Otherwise, we initialize a counter by 1 and a temporary pointer to Node, temp and initialize it by *head. Then,
      1. Iterate the list to reach the position just before the point where we want to insert our new_node.
      2. Then we assign temp->next to new_node->next, and new_node to temp->next.
  • If no, then we display an error message to user, and exit the function.

The complete code for this is:

#include <iostream>

using namespace std;

/*
Defining the structure for Node
*/
struct Node
{
        double num;     //      To store the real number
        Node *next;     //      To store pointer to next node
};

/*
Function to add a node to the list
Arguments:
        **head -> Double pointer to the first node of the list
*/
int addNode(Node **head)
{
        Node *new_node = NULL;  //      The new node
        double input_num;               //      Get the real number from user

        //      Defining the new node
        new_node = new Node;
        cout << "Enter a number: ";
        cin >> input_num;
        new_node->num = input_num;
        new_node->next = NULL;

        //      Case when first node is added to list, i.e. the when list is empty
        if(*head == NULL)
        {
                *head = new_node;
        }
        //      Otherwise
        else
        {
                Node *temp = *head;

                //      Iterate to the last node in list
                while(temp->next != NULL)
                        temp = temp->next;

                //      Add the new node to the list
                temp->next = new_node;
        }

        return 0;
}

/*
Function to count the number of nodes in the list
Arguments:
        *head -> pointer to the first node in the list
Return value:
        The count of nodes in the list.
*/
int countNode(Node *head)
{
        int count = 0;

        //      Iterating the entire list
        while(head != NULL)
        {
                //      Increasing the count of nodes by one in each iteration
                ++count;
                head = head->next;
        }

        return count;
}

/*
Function to add a node at position given by user
*/
int addNodeAtPosition(Node **head)
{
        Node *new_node = NULL;  //      The new node
        double input_num;               //      Get the real number from the user
        int position;                   //      Get the position from the user

        //      Defining the new node
        new_node = new Node;
        cout << "Enter a number: ";
        cin >> input_num;
        new_node->num = input_num;
        new_node->next = NULL;

        //      Taking the position of insertion from the user
        cout << "Enter the position of the node: ";
        cin >> position;

        //      Checking if insertion at given position feasible or not.
        if(position > countNode(*head) + 1)
        {
                cout << "Sorry!! Node cannot be entered at this position. List is too short." << endl;
                return 0;
        }
        //      Inserting the node
        else
        {
                //      If we insert at the start of the list
                if(position == 1)
                {
                        new_node->next = *head;
                        *head = new_node;
                }
                //      Otherwise
                else
                {
                        int counter = 1;        //      Keep track of the current position
                        Node *temp = *head;

                        //      Iterate the list to reach node at (position-1)
                        while(temp != NULL && counter < position-1)
                        {
                                ++counter;
                                temp = temp->next;
                        }

                        //      Insert the node at position
                        new_node->next = temp->next;
                        temp->next = new_node;
                }
        }
        return 0;
}

/*
Function to print the list
Arguments:
        *head -> Pointer to the first node in the list
*/
int printList(Node *head)
{
        cout << "The list is:" << endl;

        while(head != NULL)
        {
                cout << head->num << " -> ";
                head = head->next;
        }
        cout << "NULL" << endl;

        return 0;
}

/*
Driver function
*/
int main()
{
        Node *first = NULL;
        int choice, count;
        double avg;

        //      Displaying the options available to the user
        cout << "MENU" << endl;
        cout << "1. Add node" << endl;
        cout << "2. Add node at nth position" << endl;
        cout << "3. Print the list" << endl;
        cout << "4. Exit" << endl;

        do
        {
                //      Take choice from user
                cout << "Enter your choice: ";
                cin >> choice;

                //      Do task according to the choice
                switch(choice)
                {
                        case 1:
                        addNode(&first);
                        break;

                        case 2:
                        addNodeAtPosition(&first);
                        break;

                        case 3:
                        printList(first);
                        break;

                        case 4:
                        cout << "Bye!!" << endl;
                        break;

                        default:
                        cout << "Sorry!! No such choice. Please try again." << endl;
                }
        }while(choice != 4);

        return 0;
}

The output of the program is:

Answer 5

In this, we want to delete node from position specified by the user. To do this, we first take the position from the user. We declare a variable del_node to store reference to the node. C++ do not have garbage collector, hence we manually need to free the memory. Then we check, if deletion is poosible from that position or not.

  • If yes, then:
    • We check if user want to delete from the start of the list.
      • If yes, then we assign the node to del_node. Then, move *head one position right by assigning (*head)->next to *head.
      • Otherwise, we initialize the counter by 1, and a temporary Node type pointer by *head.
        1. Now we iterate to the position before the node which we want to delete.
        2. Assign temp to del_node.
        3. Assign temp->next->next to temp->next.
    • Then we free the memory space allocated the the node we just deleted, by using free(del_node).
  • Otherwise, we exit the function.

Here is the complete code for this question:

#include <iostream>

using namespace std;

/*
Defining the structure for Node
*/
struct Node
{
        double num;     //      To store the real number
        Node *next;     //      To store pointer to next node
};

/*
Function to add a node to the list
Arguments:
        **head -> Double pointer to the first node of the list
*/
int addNode(Node **head)
{
        Node *new_node = NULL;  //      The new node
        double input_num;               //      Get the real number from user

        //      Defining the new node
        new_node = new Node;
        cout << "Enter a number: ";
        cin >> input_num;
        new_node->num = input_num;
        new_node->next = NULL;

        //      Case when first node is added to list, i.e. the when list is empty
        if(*head == NULL)
        {
                *head = new_node;
        }
        //      Otherwise
        else
        {
                Node *temp = *head;

                //      Iterate to the last node in list
                while(temp->next != NULL)
                        temp = temp->next;

                //      Add the new node to the list
                temp->next = new_node;
        }

        return 0;
}

/*
Function to count the number of nodes in the list
Arguments:
        *head -> pointer to the first node in the list
Return value:
        The count of nodes in the list.
*/
int countNode(Node *head)
{
        int count = 0;

        //      Iterating the entire list
        while(head != NULL)
        {
                //      Increasing the count of nodes by one in each iteration
                ++count;
                head = head->next;
        }

        return count;
}

/*
Function to delete a node from specified position in the list
Arguments:
        **head -> Double pointer for he first node of the list
*/
int deleteNode(Node **head)
{
        int position;   //      Get position for deleting from the user

        cout << "Enter the position of node to be deleted: ";
        cin >> position;

        //      Taking the position of insertion from the user
        if(position > countNode(*head))
        {
                cout << "Sorry!! Node cannot be entered at this position. List is too short." << endl;
                return 0;
        }
        //      Checking if insertion at given position feasible or not.
        else
        {
                Node *del_node = NULL;  //      Node to be deleted

                //      If we are deleting the first node of the list
                if(position == 1)
                {
                        del_node = *head;
                        *head = (*head)->next;
                }
                //      Otherwise
                else
                {
                        int counter = 1;        //      Keep track of the current position
                        Node *temp = *head;

                        //      Iterate the list to reach node at (position-1)
                        while(temp != NULL && counter < position-1)
                        {
                                ++counter;
                                temp = temp->next;
                        }

                        //      Delete node from the position
                        del_node = temp->next;
                        temp->next = temp->next->next;
                }

                //      Freeing the memory allocated to the deleted node
                free(del_node);
        }

        return 0;
}

/*
Function to print the list
Arguments:
        *head -> Pointer to the first node in the list
*/
int printList(Node *head)
{
        cout << "The list is:" << endl;

        while(head != NULL)
        {
                cout << head->num << " -> ";
                head = head->next;
        }
        cout << "NULL" << endl;

        return 0;
}

/*
Driver function
*/
int main()
{
        Node *first = NULL;
        int choice, count;
        double avg;

        //      Displaying the options available to the user
        cout << "MENU" << endl;
        cout << "1. Add node" << endl;
        cout << "2. Delete a node" << endl;
        cout << "3. Print the list" << endl;
        cout << "4. Exit" << endl;

        do
        {
                //      Take choice from user
                cout << "Enter your choice: ";
                cin >> choice;

                //      Do task according to the choice
                switch(choice)
                {
                        case 1:
                        addNode(&first);
                        break;

                        case 2:
                        deleteNode(&first);
                        break;

                        case 3:
                        printList(first);
                        break;

                        case 4:
                        cout << "Bye!!" << endl;
                        break;

                        default:
                        cout << "Sorry!! No such choice. Please try again." << endl;
                }
        }while(choice != 4);

        return 0;
}

The output for the program is:

Hope my answer meet your needs.

venereology answered 1 year ago
Next > < Previous

Related Solutions

Write a subroutine named swap in C thatswaps two nodes in a linked list. The first...
Write a subroutine named swap in C thatswaps two nodes in a linked list. The first node should not be able to change places. The nodes are given by: Struct nodeEl { int el; struct nodeEl * next; }; typdef struct nodeEl node; The list header (of type node *) is the first parameter of the subroutine. The second and third parameters consist of integers and are the places in the list where the nodes are to change places. The...
1) a. Write down a C++ program which will create a list (simple linear linked list)...
1) a. Write down a C++ program which will create a list (simple linear linked list) of nodes. Each node consists of two fields. The first field is a pointer to a structure that contains a student id (integer) and a gradepoint average (float). The second field is a link. The data are to be read from a text file. Your program should read a file of 10 students (with student id and grade point average) and test the function...
Please use C++ and linked list to solve this problem Linked list 1 -> 3 ->...
Please use C++ and linked list to solve this problem Linked list 1 -> 3 -> 4 -> 5-> 6 ->7 replaceNode( 5 , 6) // Replace 5 with 6     result 1 -> 3 -> 4 -> 6 -> 6 ->7 Base code #include <iostream> using namespace std; class Node { public:     int data;     Node *next;     Node(int da = 0, Node *p = NULL) {         this->data = da;         this->next = p;     } };...
Please use C++ and linked list to solve this problem Linked list 1 -> 2 ->...
Please use C++ and linked list to solve this problem Linked list 1 -> 2 -> 3 -> 4 -> 5-> 6 ->7 replaceNode( 5 , 6) // Replace 5 with 6     result 1 -> 2 -> 3 -> 4 -> 6 -> 6 ->7 Base code #include <iostream> using namespace std; class Node { public:     int data;     Node *next;     Node(int da = 0, Node *p = NULL) {         this->data = da;         this->next =...
C++ code please: Write a program that first gets a list of integers from input. The...
C++ code please: Write a program that first gets a list of integers from input. The input begins with an integer indicating the number of integers that follow. Then, get the last value from the input, which indicates how much to multiply the array by. Finally, print out the entire array with each element multiplied by the last input. Assume that the list will always contain less than 20 integers. Ex: If the input is 4 4 8 -4 12...
Could you write a c- program that reads a text file into a linked list of...
Could you write a c- program that reads a text file into a linked list of characters and then manipulate the linked list by making the following replacements 1. In paragraph 1 Replace all “c” with “s” if followed by the characters “e”, “i” or “y”; otherwise 2. In pragraph 2 Replace "We" with v"i" This is the text to be manipulated: Paragraph1 She told us to take the trash out. Why did she do that? I wish she would...
Could you write a c- program that reads a text file into a linked list of...
Could you write a c- program that reads a text file into a linked list of characters and then manipulate the linked list by making the following replacements 1. Replace all “c” with “s” if followed by the characters “e”, “i” or “y”; otherwise 2. Replace "sh" with ph This is the text to be manipulated: Paragraph1 She told us to take the trash out. Why did she do that? I wish she would not do that Paragraph 2 We...
Write a C program that creates and prints out a linked list of strings. • Define...
Write a C program that creates and prints out a linked list of strings. • Define your link structure so that every node can store a string of up to 255 characters. • Implement the function insert_dictionary_order that receives a word (of type char*) and inserts is into the right position. • Implement the print_list function that prints the list. • In the main function, prompt the user to enter strings (strings are separated by white-spaces, such as space character,...
Suppose a linked list of 20 nodes. The middle node has a data –250. Write the...
Suppose a linked list of 20 nodes. The middle node has a data –250. Write the pseudocode to replace the middle node of the linked list with a new node and new data. Assume that the list's head pointer is called head_ptr and the data for the new node is called entry
Given a linked list of integers, remove any nodes from the linked list that have values...
Given a linked list of integers, remove any nodes from the linked list that have values that have previously occurred in the linked list. Your function should return a reference to the head of the updated linked list. (In Python)
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT