Language is Java and the source code is given by this github link.
https://github.com/ctanis/cpsc3200_fa18/tree/master/hw1_provided
For this assignment you will modify a provided generic linked list class and analyze the performance of your new functionality After the due date you will check other students work for correctness and completeness. Provided code I've written a SinglyLinkedList
class for you to start with, along with a simple Tester class. You can find this code in the course git repository https://github.com/ctanis/cpsc3200_fa18 in the hw1_provided/ subdirectory You should verify that you can compile this code and run the main method in Tester. Read through the source code and familiarize yourself with the contents. Your tasks You should do the following: 1. Modify the class as appropriate so that add (T value) performs in constant time. Do not make the list into a doubly linked list. 2. Add a remove ) method that removes the last value in the list. 3. Add a remove(int index) method that removes the value at position index, and throws an exception if index is invalid. 4. Add a remove() method to the ForwardIterator. Look at the java.util.Iterator javadocs for infor- mation about how this method should function. 5. Create a new ReverseIterator and a method that returns one that visits list elements in reverse order Because this is a singly linked list, this iterator will perform poorly. That is desirable for our purposes. 6. Write a Tester1 class that demonstrates that your modifications function correctly. Simply test add (1T value). remove) and remove (int index). Make sure that size ) returns the correct value after adds and removes. Make sure the forward iterator still works, including your new remove method. Make sure vour new reverse iterator works correctly 7. Write a Tester2 class that shows that your new add(T value) method operates in constant time, rather than linear as in the provided code. Show that your reverse iterator operates in quadratic time. For this assignment you will modify a provided generic linked list class and analyze the performance of your new functionality After the due date you will check other students work for correctness and completeness. Provided code I've written a SinglyLinkedList class for you to start with, along with a simple Tester class. You can find this code in the course git repository https://github.com/ctanis/cpsc3200_fa18 in the hw1_provided/ subdirectory You should verify that you can compile this code and run the main method in Tester. Read through the source code and familiarize yourself with the contents. Your tasks You should do the following: 1. Modify the class as appropriate so that add (T value) performs in constant time. Do not make the list into a doubly linked list. 2. Add a remove ) method that removes the last value in the list. 3. Add a remove(int index) method that removes the value at position index, and throws an exception if index is invalid. 4. Add a remove() method to the ForwardIterator. Look at the java.util.Iterator javadocs for infor- mation about how this method should function. 5. Create a new ReverseIterator and a method that returns one that visits list elements in reverse order Because this is a singly linked list, this iterator will perform poorly. That is desirable for our purposes. 6. Write a Tester1 class that demonstrates that your modifications function correctly. Simply test add (1T value). remove) and remove (int index). Make sure that size ) returns the correct value after adds and removes. Make sure the forward iterator still works, including your new remove method. Make sure vour new reverse iterator works correctly 7. Write a Tester2 class that shows that your new add(T value) method operates in constant time, rather than linear as in the provided code. Show that your reverse iterator operates in quadratic time
