COSC 2336: Data Structures and Algorithms

Tasks
You should set up your project/code as described in the previous section. In this section we give some more details on implementing the member functions for this assignment. You should perform the following tasks for this assignment:
1. Write the member function to search() the linked list for a particular piece of information. The search function takes a const T& as its parameter and it returns a boolean result. This member function should also be declared
as a const member function, as it does not change the list if it is called. An example implementaiton for this function is actually given in our textbook, though you may need to change it slightly to work with our assignment code.
2. Also add/write the deleteNode() member function, which is also given in our textbook implementation. This function takes a const T& as its parameter, which is the value of an item to search for and delete. Thus the first part of this function is similar to the search() function, in that you first have to perform a search to find
the item. But once found, the node containing the item should be removed from the list (and you should free the memory of the node). This function is only guaranteed to find the first instance of the item and delete it, if the item appears multiple times in the list, the ones after the first one will still be there after the first item is removed by this function. This function should return a LinkedListItemNotFoundException if the item asked for is not found. The LinkedListItemNotFoundException class has already been defined for you in the starting template header file.

COSC 2336: Data Structures and Algorithms

3. Write a member function named findItemAtIndex() for the LinkedList class. This function will be given a single integer parameter called index. It will search through the linked list and return a reference to the info of index’th node in the list. It is important that you return a T& (a reference to a type T) from this function.
This function works using 0 based indexing (like arrays), thus if we ask for index 0, the first or head node info should be returned. If we ask for index 1, the info in the node after the head node is returned. If the list only has 5 nodes (indexes 0 to 4) and we ask for index 5 or greater, you should throw a LinkedListItemNotFound exception. (This exception class has already been defined in the LinkedList header given to you, you simply need to throw it). For a little extra credit, you can add the overloaded operator[] to define indexing operations on your LinkedList which just uses your working findItemAtIndex() member function.
4. Write a member function named deleteItemAtIndex(). This function will perform similar to the previous one, but instead of returning the info in the index’thed node, it will simply delete the node. Thus your logic will be similar to task 3, you will need to search till you get to the index’thed node in the list. But at that point you should remove the node (and don’t forget to delete it, to free up its memory). If the asked for index does not exist, as usual you should throw a LinkedListItemNotFound exception.
5. Extra credit: you can write this recursive member function for a little bit of additional extra credit. Write a member function named toReverseString(). There is already a string function, that creates a string representation of the items in the list and returns the string. Your method will create a string of the items in the linked list, but in reverse order. You should use the recursiveReversePrint() discussed in our textbook as an example. E.g. this method should be implemented using a recursive function definition to accomplish reversing the list. But for credit, your function needs to use recursion, and it needs to build and return a string recursively (not print the results on the cout stream). There are tests for this extra credit in the testing file, but you can simply leave them commented out if you don’t work on this function. Hint: You will need to write two functions named toReverseString(). One of them will take no parameters, and is what is usually called by a user of the LinkedList class. But the second version should be the recursive function, and it will take a Node* as its parameters.