Programming assignment
Bee_wake
assg-09.pdf
Assg 09: Linked Lists
COSC 2336 Spring 2019
March 8, 2019
Dates:
Due: Sunday March 24, by Midnight
Objectives
� More practice with dynamic memory and pointers.
� Also more practice with using templates, as we would like our LinkedList to be templatized to work with lists of any type.
� Look at a more realistic example of an ADT.
� Learn how to construct linked lists, and perform operations like iterate over, insert and delete items in the list.
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 de- scribed and presented in chapter 17 of our textbook. We will be adding some additional operations to the template LinkedList class for this assignment.
For this assignment you need to perform the following tasks.
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 pa- rameter 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.
1
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 �rst part of this function is similar to the search() function, in that you �rst have to perform a search to �nd 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 �nd the �rst instance of the item and delete it, if the item appears multiple times in the list, the ones after the �rst one will still be there after the �rst 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 de�ned for you in the starting template header �le.
3. Write a member function named findItemAtIndex() for the LinkedList class. This function will be given a single integer parameter called in- dex. It will search through the linked list and return a reference to the info of index'th node in the list. This function works using 0 based indexing (like arrays), thus if we ask for index 0, the �rst 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 al- ready been de�ned 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 de�ne indexing operations on your LinkedList which just uses your working findItemAtIndex() member function.
4. Write a member function named deleteItemAtIndex(). This func- tion will perform similar to the previous one, but instead of return- ing the info in the index'thed node, it will simply delete the node. Thus your logic will be similar to 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 mem- ory). If the asked for index does not exist, as usual you should thow 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.
2
Your method will create a string of the items in the linked list, but in reverse order. You should use the recursiveReversePrint() dis- cussed in our textbook as an example. E.g. this method should be implemented using a recursive function de�nition to accomplish re- versing 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 �le, 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.
You will be given 3 starting template �les like before, an assg-09-tests.cpp �le of tests of your code, and a LinkedList.hpp and LinkedList.cpp header and implementation �le. As before, you should practice incremental devel- opment, and uncomment the tests in the assg-09-tests.cpp �le one at a time, and implement the functions in the order speci�ed. If you implement your code correctly and uncomment all of the tests, you should get the following correct output:
-------------- Tests of functions given for assignment --------------
test list isEmpty? true
list length should be 0: 0
list front item: Second Item
list back item: First Item
list back item is now: Back Item Again
list length is now: 4
list is no longer empty? false
<myList>:
List count: 4
info: [Second Item, First Item, Back Item, Back Item Again]
Iterating list item at index[0] = Second Item
Iterating list item at index[1] = First Item
Iterating list item at index[2] = Back Item
Iterating list item at index[3] = Back Item Again
3
Using range based got info it index[0] = Second Item
Using range based got info it index[1] = First Item
Using range based got info it index[2] = Back Item
Using range based got info it index[3] = Back Item Again
List count: 4
info: [Second Item, First Item, Back Item, Back Item Again]
anotherList length: 4
Test all items are equal after copy constructor:
Item index: 0
Item from another list : Second Item
Item from original list: Second Item
Item index: 1
Item from another list : First Item
Item from original list: First Item
Item index: 2
Item from another list : Back Item
Item from original list: Back Item
Item index: 3
Item from another list : Back Item Again
Item from original list: Back Item Again
After emptying anotherList: List count: 0
info: []
myList should still be fine: List count: 4
info: [Second Item, First Item, Back Item, Back Item Again]
After copying back again anotherList: List count: 4
info: [Second Item, First Item, Back Item, Back Item Again]
Test all items are equal after copyList() function:
Item index: 0
Item from my list : Second Item
Item from copied list: Second Item
Item index: 1
Item from my list : First Item
Item from copied list: First Item
Item index: 2
4
Item from my list : Back Item
Item from copied list: Back Item
Item index: 3
Item from my list : Back Item Again
Item from copied list: Back Item Again
-------------- Test search() function ------------------------------
search() test if front item found: true
search() test if back item found: true
search() test if middle item found: true
search() test unsuccessful search: false
search() test on empty list: false
-------------- Test deleteNode() function ------------------------------
deleteNode() delete middle node:
List count: 3
info: [Second Item, Back Item, Back Item Again]
deleteNode() delete first node:
List count: 2
info: [Back Item, Back Item Again]
deleteNode() delete last node:
List count: 1
info: [Back Item]
deleteNode() try and delete nonexistent item
List count: 1
info: [Back Item]
caught item not found exception:
Error: LinkedList item not foundLinkedList<T>::deleteNode() failed to find item: Bogus Item
deleteNode() delete only node, list is now empty:
List count: 0
info: []
5
-------------- Test findItemAtIndex() function ----------------------
findItemAtIndex(): created new list of integers of length: 5
List count: 5
info: [1, 5, 7, 2, 8]
findItemAtIndex() item at index 2: 7
findItemAtIndex() item at last valid index: 8
findItemAtIndex() item at index 0: 1
findItemAtIndex() tried invalid index 5
caught item not found exception:
Error: LinkedList item not foundLinkedList<T>findItemAtIndex(): invalid index request index: 5 count: 5
findItemAtIndex() tried invalid index -1
caught item not found exception:
Error: LinkedList item not foundLinkedList<T>findItemAtIndex(): invalid index request index: -1 count: 5
findItemAtIndex() returned item at index 1: 5
findItemAtIndex() after changing item to 9: List count: 5
info: [1, 9, 7, 2, 8]
findItemAtIndex() after changing lst item to `0: List count: 5
info: [1, 9, 7, 2, 10]
operator[] test overloading, get item 2: 7
operator[] test overloading, get item 0: 1
-------------- Test deleteItemAtIndex() function ----------------------
deleteItemAtIndex() delete middle node:
List count: 4
info: [1, 9, 2, 10]
deleteItemAtIndex() delete first node index 0:
List count: 3
info: [9, 2, 10]
deleteItemAtIndex() delete last node index 2:
List count: 2
6
info: [9, 2]
deleteItemAtIndex() try and dleete invalid index
List count: 2
info: [9, 2]
caught item not found exception:
Error: LinkedList item not foundLinkedList<T>findItemAtIndex(): invalid index request index: 2 count: 2
deleteItemAtIndex() try and dleete invalid negative index
List count: 2
info: [9, 2]
caught item not found exception:
Error: LinkedList item not foundLinkedList<T>findItemAtIndex(): invalid index request index: -2 count: 2
deleteItemAtIndex() deleted last 2 items, expect empty list:
List count: 0
info: []
-------------- Test toReverseString() function (Extra Credit) -------
toReverseString() test empty list:
List count: 0
info: []
the string in normal order:
List count: 4
info: [1, 2, 3, 4]
toReverseString() test:
List count: 4
info: [4, 3, 2, 1]
Assignment Submission
A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed .cpp source �les to the submission
7
folder to complete this assignment. You really do not need to give me the assg-09.cpp �le again, as I will have my own �le with additional tests of your functions. However, please leave the names of the other two �les as LinkedList.hpp and LinkedList.cpp when you submit them.
Requirements and Grading Rubrics
Program Execution, Output and Functional Requirements
1. Your program must compile, run and produce some sort of output to be graded. 0 if not satis�ed.
2. (15 pts.) search() works and correctly returns boolean result.
3. (20 pts.) deleteNode() is implemented correctly. Works for all cases of a linked list, like removing �rst and last nodes. Detects invalid indexes and throws the asked for exception.
4. (30 pts.) findItemAtIndex() is implemented correctly. Correctly throws exception for invalid indexes. Is correctly returning a refer- ence, so can actually be used for assignment.
5. (35 pts.) deleteItemAtIndex() is working. Correctly handles delete- ing the �rst and last items of list, and deleteing case when list goes from 1 item to an empty list. Throws exception for invalid indexes as asked for.
6. (5 bonus pts.) Up to an additional 5 points of extra credit for correctly adding the mentioned overloaded operator[] and the toReverseString() recursive functions.
Program Style
Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.
1. Most importantly, make sure you �gure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from �les, and only 2 spaces used for indentation.
8
2. A function header must be present for member functions you de�ne. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.
3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.
4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is speci�c to a single operating system, such as the system("pause") which is Microsoft Windows speci�c.
9
