Due at the end of lab.

For this lab you will be extending your linked list. Use the same node class you created in lab 12, which should contain the following:

• A private string variable called name.
• A private integer variable called ID.
• A private node pointer called next
• A public set function that takes a string, an integer, and a node pointer and sets the name, ID, and next variables.
• A public, recursive print function that prints every element in the linked list.
• A public, recursive search function that takes an integer as an argument and searches a linked list for the matching ID. It should return a string - the name that matches the ID. Or return an empty string "" if the ID is not found.

For this lab we are going to add the following functions to the node class:

• A public, recursive queue function that takes a string and an integer as arguments and adds a new node to the tail (end) of the list. This function will need to recursively traverse the list ("walk" down the list) until it finds the NULL pointer at the end of the list. Then this function will need to create a new node using the string as the name and the integer as the ID and add it at the end.

• A public recursive insert function that takes a string and an integer as arguments and adds a new node to the list in it's sorted position based on the integer (the node's ID). Like the queue function, the insert function will need to find the right place in the list to insert the new data, then create a node object with the given ID (integer) and name (string).

  Note that a node that has to be inserted at the beginning of the list or at the end of the list are both special cases. You probably want to solve the general case of inserting a node in the middle of the list first.

The main code should use the node class to do the following:

• Use the insert function to create a list sorted by ID (you can pick the IDs and names to add) and use the print function to show that it exists.
• Use the queue function to create an unsorted list (you can pick the IDs and names to add) and use the print function to show that it exists.
• Note for both of the above tasks you should print the list when its only partially created and when it's fully created to show that the nodes are being added in the correct positions.

Turn in: Your code and sample output showing that both types of insert work.