Modify a provided generic linked list class and analyze the performance of your new functionality.

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 information 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(T 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 your 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.

Code provided:

/**
	A generic SinglyLinkedList class for you to modify and analyze
	*/
	public class SinglyLinkedList implements Iterable{
	// since this is an inner class (not a static nested class), we can access
	// T
	private class Node
	{
	T value;
	Node next;
	Node(T value, Node next)
	{
	this.value=value;
	this.next=next;
	}
	Node() { }
	}
	private int count; // number of items in the list
	private Node head; // pointer to dummy node at head of list
	public SinglyLinkedList()
	{
	head = new Node(); // dummy node
	}
	/**
	* Add a value to the end of the list
	* @param value the value to be added
	* This performs linearly with respect to the length of the list.
	* TOOD: Modify the list, and this method, to make this a constant
	* operation
	*/
	void add(T value)
	{
	Node curs=head;
	while (curs.next != null)
	{
	curs=curs.next;
	}
	curs.next = new Node(value,null);
	count++;
	}
	/**
	* Add a value to the list at position index
	* @param index the desired location
	* @param value the value to be added
	*
	* Note: this throws an exception if index is invalid
	*
	* Food for thought: How does the performance of this method depend on index?
	*/
	void add(int index, T value)
	{
	Node c=findNode(index);
	c.next=new Node(value, c.next);
	count++;
	}
	/**
	@index the index of the desired list value
	@return the value in the list at the index'th position
	Throws exception if index is invalid
	*/
	T get(int index)
	{
	Node c=findNode(index);
	return c.next.value;
	}
	/**
	* @return the number of items in this list
	*/
	int size()
	{
	return count;
	}
	/**
	* Returns a Node whose .next member is (or would be, in the case of
	* index==count) the index'th Node in the list
	*
	* Throws an exception if the index is not valid
	*
	* @param index the index of the desired Node
	* @return the Node whose next is the index'th
	*/
	private Node findNode(int index)
	{
	// Notice how the use of a 'dummy' node at the head makes this logic
	// simpler
	Node curs=head;
	int p=0;
	if (index < 0)
	{
	throw new RuntimeException("invalid index: " + index);
	}
	while (p
	{
	curs=curs.next;
	p++;
	}
	if (curs == null)
	{
	throw new RuntimeException("invalid index: " + index);
	}
	return curs;
	}
	/**
	Implements java.lang.Iterable
	*/
	public java.util.Iterator iterator()
	{
	return new ForwardIterator();
	}
	private class ForwardIterator implements java.util.Iterator
	{
	// This is legal since it's a proper inner class (not a static nested
	// class)
	Node curs=head;
	public boolean hasNext()
	{
	return curs.next != null;
	}
	// Note: this method has undefined behavior if hasNext() return false
	public T next()
	{
	curs=curs.next;
	return curs.value;
	}
	// TODO: add a remove() method -- see the java.util.Iterator documentation
	}
	// TODO: Write a ReverseIterator inner class, along with a public method
	// for returning it. Normally you would only have such a thing on a
	// doubly linked list, but we're writing one to analyze its performance.
	}

public class Tester {
	public static void main(String[] args)
	{
	// See the SinglyLinkedList class in action ...
	SinglyLinkedList sl1 = new SinglyLinkedList<>();
	sl1.add("a");
	sl1.add("b");
	sl1.add("c");
	sl1.add(1, "in the middle!");
	sl1.add(0, "at the beginning");
	System.out.println("List contents:");
	for (String s : sl1)
	{
	System.out.println(s);
	}
	// // Equivalent code using an explicit iterator
	//
	// java.util.Iterator it = sl1.iterator();
	// while (it.hasNext())
	// {
	// System.out.println(it.next());
	// }
	// // Somewhat equivalent code using the get() method
	//
	// for (int i=0; i
	// {
	// System.out.println(sl1.get(i));
	// }
	// Analyze the performance of the .add() method
	System.out.println();
	System.out.println("now some timing tests...");
	System.out.println();
	for (long N=10000; N<100000; N*=2)
	{
	long start = System.nanoTime();
	addN(N);
	long end = System.nanoTime();
	System.out.println("calling add() " + N + " times took " + (end-start)/1e6 + " ms");
	}
	}
	public static SinglyLinkedList addN(long N)
	{
	SinglyLinkedList slist = new SinglyLinkedList<>();
	for (long i=0; i
	{
	slist.add(i);
	}
	return slist;
	}
	}