Begin with the starter code included. The existing code is designed to avoid cycles.

package linkedlist;

public class SinglyLinkedList { protected Node head, tail; protected long size;

public SinglyLinkedList() { head = null; tail = null; size = 0; }

public void addFirst(T element) { Node node = new Node(element); addFirst(node); }

public void addFirst(Node node) { if (tail == null) tail = node; node.setNext(head); head = node; size++; }

public void add(T element) { Node node = new Node(element); if (tail == null) addFirst(node); else add(node); }

public void add(Node nodeToAdd) { nodeToAdd.setNext(null); if (tail == null) { tail = nodeToAdd; head = nodeToAdd; } else tail.setNext(nodeToAdd); tail = nodeToAdd; size++; }

public void removeFirst() { if (head == null) return; Node temp = head;

head = head.getNext(); temp.setNext(null); size--; }

public void removeLast() { Node nodeBefore;

if (size == 0) return; nodeBefore = head;

for (int count = 0; count

public void remove(T element) { if (size == 0) return; Node currNode = head; do { if (currNode.getElement().equals(element)) {

if (currNode == head) { removeFirst(); currNode = head; } else if (currNode == tail) { removeLast(); currNode = tail; } else { Node next = currNode.getNext(); remove(currNode); currNode = next; } } else currNode = currNode.getNext(); } while (currNode != null);

}

public void remove(Node nodeToRemove) { Node nodeBefore, currentNode; if (size == 0) return;

currentNode = head; if (currentNode == nodeToRemove) removeFirst(); currentNode = tail; if (currentNode == nodeToRemove) removeLast();

if (size - 2 > 0) { nodeBefore = head; currentNode = head.getNext(); for (int count = 0; count

nodeBefore = currentNode; currentNode = currentNode.getNext(); } } }

public T get(int index) { Node currNode = head; if (index >= size) return null; for (int counter = 0; counter

public Node getNode(int index) { Node currNode = head; if (index >= size) return null; for (int counter = 0; counter

public long size() { return size; }

public Node getTail() { return tail; }

public boolean contains(T element) { if (head == null) return false; Node currNode = head; while (currNode.getNext() != null) { if (currNode.getElement().equals(element)) return true; currNode = currNode.getNext(); } if (currNode.getElement().equals(element)) return true; return false; } }

• Study the code until you understand how it works, and particularly why you can't create a cycle using the existing add method.
• Add a method public void addToCreateCycle(Node nodeToAdd) that allows the user to add a Node in a way that will create a cycle. If you send a node that is already in the list as a parameter to this method, your list will contain a cycle.
• Write a boolean method called checkForCycle() in the list code that uses Floyd's algorithm to determine whether a cycle exits in the list. You do not need to determine where a cycle starts, only whether one is present.
• Write five JUnit tests, each with *one* assertion
  • create a list with no nodes and assert that there is no cycle (ie., that your cycle detection method returns false)
  • create a list with several nodes but no cycles and assert that there is no cycle
  • create a list with only one node with its next reference set to itself and assert that there is a cycle
  • create a list with a cycle whose length (number of nodes involved in the cycle) is odd and assert that there is a cycle
  • create a list with a cycle whose length is even and assert that there is a cycle

Use exactly the method names specified above.

Turn in the unchanged Node.java file, the edited SinglyLinkedList.java file, your JUnit test case, and a screenshot showing the results of running your JUnit tests. Don't zip or otherwise compress the files, just upload the four files separately.

1 package linkedlist; 2 3 4 public class Node { // instance variables private I element; private Node next; 5 6 7 8 9 // constructor first public Node() { this(null, null); } 10 11 12 13 14 public Node(T element) { this.element = element; } 15 16 17 18 public Node(t element, Node next) { this.element = element; this.next = next; } 19 20 21 22 23 public T getElement() { return element; } 24 25 26 27 public Node getNext() { return next; } 28 29 30 31 public void setElement(t element) { this.element = element; } 32 33 34 35 public setNext(Node next) { this.next = next; } 36 37 38 } 39