Due Dec. 1st.

For this lab you will be extending your linked list. Use the same node class you created in lab 12 (or lab 13 if you have completed it), which should already 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 assignment add the following functions to the node class:

• A pop function that removes the last element from a linked list and returns it.
• A dequeue function that removes the first element from a linked list and returns it.
• A public, recursive delete function that takes an integer as argument, finds the node with that integer as its ID and deletes it from the list. You can borrow from the search function to help with writing the code to find the correct node. However, to delete the node the node before it should point to the node after it, so you may want your delete function to "look ahead" when trying to find the right node to delete. The node behind the node to be deleted should be changed to point to the node after the node to be deleted - removing from the list.

  Note that a node that has to be removed from the beginning of the list is a special case. You probably want to solve the general case of inserting a node in the middle of the list first.

• A public, recursive delete function that takes a string as argument, finds the node with that string as its name and deletes it from the list. You can borrow from the ID delete function to help with writing the code to find the correct node.

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