Description

In this assignment, you will be given an already templatized version of a LinkedList class. The implementation given is mostly the same one as described and presented in chapter 17 of our textbook. you will be adding some additional operations to the template LinkedList class for this assignment.

In particular, you will be adding functionality to use the linked list to search for items, delete items from the list, and display the list, among others. You will need to look at and understand the LinkedList class given, and the node data structure(s) that are being managed to add and remove items from the internal linked list.

Setup

For this assignment you will be given the following files:

File Name         Description

assg08-tests.cpp Unit tests for the member functions you are to write.

LinkedList.hpp     Header file defining LinkedList class and where member function prototypes should be declared.

LinkedList.cpp Implementation file for the LinkedList class member functions.

Set up a multi-file project to compile the .cpp source files and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class. Since LinkedList is a template class you do not actually compile the LinkedList.cpp file separately into an object file. If you look at  the bottom of the LinkedList.hpp header, it includes LinkedList.cpp, the template implementations. So any file that includes the LinkedList.hpp header file actually also includes the template implementations as well.

The general approach you should take for this assignment, and all assignment is:

1. Set up your project with the given starting code. The files should compile and run, but either no tests will be run, or tests will run but be failing.

2. For this project, start by uncommenting the first TEST_CASE in the assg08-tests.cpp file. These are the unit tests to test the functionality of search() member function, the first member function you are to implement.

3. Add the correct function prototype for the search() member function to the LinkedList class in the

LinkedList.hpp header file. The prototype consists of the name of the member function, its input parameters and their types, and the return value of the function.

4. Add an implementation of the search() member function to the LinkedList.cpp implementation file. The function should have the same signature as the prototype you gave in the header file. Documentation for the function has not been given for you this time, so add documentation of your function first. Don’t forget to indicate that this function is a member of the ListType class. And in this assignment, you need to indicate the function is a template function that parameterizes a .

5. Your code should compile and run now. Make sure after adding the function prototype and stub your code compiles and runs. However, your unit tests might be failing initially.

6. Incrementally implement the functionality of your search() member function. You should try to add no more than 2 or 3 lines of code, and then make sure your program still compiles and runs. Start by adding code to get the first failing test to pass. Then once that test passes, move on to the next failing tests until you have all tests passing. If you write something that causes a previously passing test to fail, you should stop and figure out why, and either fix it so that the original test still passes, or remove what you did and try a new approach.

7. Once you have the search() member function implemented and all unit tests passing, you should then move on to the other functions in the order suggested. Some member functions use previous ones in this assignment, so do them in the order given for you in the tasks below.

I have given you a starting template for your LinkedList that implements a lot of the basic functionality of the

LinkedList class. This code is based on the example LinkedList class from our Chapter 17 Malik textbook.

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 implementation 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.

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 indexed 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 indexed 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<T>* as its parameters.

Example Output

Here is the correct output you should get from your program if you correctly implement all the class functions and successfully pass all of the unit tests given for this assignment. If you invoke your function with no command-line arguments, only failing tests are usually shown by default. In the second example, we use the -s command-line option to have the unit test framework show both successful and failing tests, and thus we get reports of all of the successfully passing tests as well on the output.

$ ./test

===============================================================================

All tests passed (168 assertions in 7 test cases)

$ ./test -s

test is a Catch v2.7.2 host application. Run with -? for options

<basic functions> test LinkedList basic member function

assg08-tests.cpp:25

...............................................................................

assg08-tests.cpp:31: PASSED: CHECK( list.isEmpty() )

with expansion: true

... output snipped ...

===============================================================================

All tests passed (168 assertions in 7 test cases)

This assignment has been answered 4 times in private sessions.