The task is to write an efficient method to find the Nth to last item in a singly linked list. The list does not know nor provide a method to return its size.

You will implement a generic linked list that is only singly linked. That is, each node only knows about the next node. Name it SinglyLinkedList. Your linked list will have a head and a tail node which contain no data. It will not keep track of its size. It will implement the Iterable interface, and you will need to write an inner class that implements the Iterator interface. Name this inner class SinglyLinkedListIterator. It is recommended that you also have an inner class Node that defines your node objects.

Your linked list must provide the following methods:

public void add(AnyType element) public void remove(AnyType element) public void clear() public AnyType getNthToLast(int n) public SinglyLinkedListIterator iterator()

The method add() adds the new element to the end of the list. The method remove() removes the first Node from the list that contains element. clear() removes all elements from the list. getNthToLast() returns the Nth to last element in the list. For example, in the list of numbers 5 4 3 2 1, 2 is the 2nd to last element, 3 is the 3rd to last, and so on. iterator() returns an instance of the SinglyLinkedListIterator.

SinglyLinkedListIterator must implement the following 4 methods.

public boolean hasNext() public AnyType next() public void remove() public void add(AnyType element)

hasNext() returns true if there is a next element in the list, and false otherwise. next() moves the iterator to point to the next Node in the list and returns the element held by that node. If next() is called and there is no next element, next() must throw a NoSuchElementException. The iterators remove() removes from the list the node currently pointed to by the Iterator (This is the element last returned by next()). If a call to remove() attempts to remove the tail, remove() must throw an IllegalStateException. Likewise, the iterators method add() adds the new element to the list after the node the iterator currently points to.

I have provided the JUnit test that I will use to test your programs.

--------------------------------------------------------------------------------------

Below is my SinglyLinkedList.java file and I'm trying to do JUnit tests on it using TestLinkedList.java but it is failing 5 tests out of 7. Can you help me fix this? Two files are below. Advanced thanks!

import java.util.Iterator;

import java.util.NoSuchElementException;

public class SinglyLinkedList implements Iterable

{

class SinglyLinkedListIterator implements Iterator

{

Node current, previous;

/* Returns true if there is a next element in the list,

and false otherwise. */

@Override

public boolean hasNext()

{

return current.next != null;

}

/* Moves the iterator to point to the next Node in the list and returns the

element held by that node. If next() is called and there is no next element,

next() must throw a NoSuchElementException. */

@Override

public T next()

{

previous = current;

current = current.next;

if(current == null)

throw new NoSuchElementException();

return current.data;

}

/* The iterators remove() removes from the list the node currently pointed

to by the Iterator. (This is the element last returned by next()). If a call

to remove() attempts to remove the tail, remove() must throw an IllegalStateException. */

@Override

public void remove()

{

previous.next = current.next;

if(current.next == null)

throw new IllegalStateException();

}

/* Adds the new element to the list after the node the iterator currently

points to. */

public void add(T element)

{

current.next = new Node(element, current.next);

}

}//end class SinglyLinkedListIterator

class Node

{

T data;

Node next;

public Node(T data, Node next)

{

this.data = data;

this.next = next;

}

public void setData(T data)

{

this.data = data;

}

public void setNext(Node next)

{

this.next = next;

}

}

Node head = new Node(null, null),

tail = new Node(null, null);

/* Iterator() returns an instance of the SinglyLinkedListIterator. */

@Override

public SinglyLinkedListIterator iterator()

{

SinglyLinkedListIterator iterator = new SinglyLinkedListIterator();

iterator.current = head;

iterator.previous = null;

return iterator;

}

/* The method add() adds the new element to the end of the list. */

public void add(T element)

{

if(tail == null)

head = tail = new Node(element, null);

else

tail = tail.next = new Node(element, null);

}

/* The method remove() removes the first Node from the list that contains element. */

public void remove(T element)

{

if(head == null)

return;

if(head.data.equals(element))

{

head = head.next;

return;

}

Node current = head;

while(current.next != null)

{

if(current.next.data.equals(element))

break;

current = current.next;

}

if(current.next == null)

return;

current.next = current.next.next;

}

/* clear() removes all elements from the list */

public void clear()

{

head = tail = null;

}

/* getNthToLast() returns the Nth to last element in the list. For example,

in the list of numbers 5 4 3 2 1, 2 is the 2nd to last element, 3 is the 3rd to last, and so on. */

public T getNthToLast(int n)

{

T[] arr = (T[])new Object[n];

int index = 0;

Node current = head;

while(current != null)

{

if(index == n)

index = 0;

arr[index++] = current.data;

current = current.next;

}

return arr[(index + 1) % n];

}//end getNthToLast

}//end class SinglyLinkedList

import java.util.Iterator; import java.util.NoSuchElementException;

import static org.junit.Assert.*; import org.junit.Test; import org.junit.Before; import org.junit.Rule; import org.junit.rules.ExpectedException;

public class TestLinkedList{ private SinglyLinkedList list;

@Rule // this rule allows one of the tests to verify that an exception is thrown public ExpectedException thrown = ExpectedException.none();

@Before public void setUp(){ list = new SinglyLinkedList<>(); SinglyLinkedList.SinglyLinkedListIterator it = list.iterator(); for(int i = 9; i > 0; i--){ it.add(new Integer(i)); it.next(); } // Question to all: The process of adding numbers to the list could // have been simplified by dispensing with the iterator and simply // calling SinglyLinkedList's add() method. Why use the iterator? // What benefit does it provide over SinglyLinkedList's add? }

/** * Ensure that the linked list holds the expected values after the * initialization in the setup() method. This initialization used the * list iterator to perform the adds. */ @Test public void testIteratorAdd(){ Iterator it = list.iterator(); Integer listElement; for(int i = 9; i > 0; i--){ listElement = it.next(); assertEquals(i, listElement.intValue()); } }

/** * Ensure that the list is built correctly if the list's add method is * used instead of the iterator's add method. */ @Test public void testListAdd(){ list.clear(); for(int i = 9; i > 0; i--){ list.add(new Integer(i)); } Iterator it = list.iterator(); Integer listElement; for(int i = 9; i > 0; i--){ listElement = it.next(); assertEquals(i, listElement.intValue()); } }

/** * Remove all the odd numbers using the list's remove method and ensure * that the remaining elements are as expected (the even numbers 8, 6, * 4, and 2). */ @Test public void testListRemove(){ list.remove(9); list.remove(7); list.remove(5); list.remove(3); list.remove(1);

Iterator it = list.iterator(); int evenNum = 8; while(it.hasNext()){ assertEquals(evenNum,it.next().intValue()); evenNum = evenNum - 2; } }

/** * Remove all the even numbers using the iterators's remove method and ensure * that the remaining elements are as expected (the odd numbers 9, 7, * 5, 3, and 1). */ @Test public void testIteratorRemove(){ // first, remove all the even numbers Iterator it = list.iterator(); while(it.hasNext()){ Integer theVal = it.next().intValue(); if( theVal.intValue() % 2 == 0){ it.remove(); } } // Next, check that the list contains the correct // remaining numbers it = list.iterator(); int oddNum = 9; while(it.hasNext()){ assertEquals(oddNum,it.next().intValue()); oddNum = oddNum - 2; } }

/** * Attempt to remove from an empty list and ensure that the * IllegalStateException is thrown */ @Test public void testEmptyRemove(){ list.clear(); thrown.expect(IllegalStateException.class); Iterator it = list.iterator(); it.remove(); }

/** * Attempt to call next() when already at the end of the list and * ensure that the NoSuchElementException is thrown. */ @Test public void testInvalidNext(){ list.clear(); thrown.expect(NoSuchElementException.class); Iterator it = list.iterator(); it.next(); }

/** * Test the getNthToLast method. * * As an example, given the numbers that is list holds: * 9 8 7 6 5 4 3 2 1 * the 2nd to last element is 2, the 3rd to last * is 3, and so on. * * Ensure that the getNthToLast returns 4 when requested the 4th to * last element. */ @Test public void testGetNthToLast(){ Integer ans = list.getNthToLast(4); assertEquals(new Integer(4),ans); } }