USING JAVA

Begin with the linked list package The existing code is designed to avoid cycles.

• Add a method public void addToCreateCycle(Node nodeToAdd) that allows the user to add a Node in a way that will create a cycle.
• Write a boolean method in the list code that determines whether a cycle exits in the list. You do not need to determine where a cycle starts, only whether one is present.
• Write JUnit tests that create a) a list with no nodes; b) a list with nodes but no cycles; c) a list with only one node with its next reference set to itself; d) a list with a cycle whose length (number of nodes involved in the cycle) is odd; e) a list with a cycle whose length is even.

package linkedlist; //adapted from http://.com/a-simple-singly-linked-list-implementation-in-java/ public class Node { // instance variables private T element; private Node next;

// constructor first public Node() { this(null, null); } public Node(T element) { this.element = element; }

public Node(T element, Node next) { this.element = element; this.next = next; }

public T getElement() { return element; }

public Node getNext() { return next; }

public void setElement(T element) { this.element = element; }

public void setNext(Node next) { this.next = next; }

}

**************************************************************************************************

package linkedlist;

import javax.swing.JOptionPane;

// heavily adapted from http://www.crunchify.com/a-simple-singly-linked-list-implementation-in-java/ 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 < size - 2; count++) nodeBefore = nodeBefore.getNext(); nodeBefore.setNext(null); tail = nodeBefore; size--; }

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 < size - 2; count++) { if (currentNode == nodeToRemove) { nodeBefore.setNext(currentNode.getNext()); size--; break; }

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

public T get(int index) { Node currNode = head; if (index >= size) return null; for (int counter = 0; counter < index; counter++) currNode = currNode.getNext(); return currNode.getElement(); }

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

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; } }

*************************************************************************************************************************

package linkedlist;

import static org.junit.Assert.assertEquals;

import static org.junit.Assert.assertFalse;

import static org.junit.Assert.assertNotNull;

import static org.junit.Assert.assertNull;

import static org.junit.Assert.assertTrue;

import org.junit.Test;

public class SinglyLinkedListTester {

@Test public void testRemoveFromListWithoutElement() { SinglyLinkedList l = new SinglyLinkedList(); String testString = "Godzilla"; String testString2 = "Mothra"; l.add(testString); l.remove(testString2); assertFalse(l.contains(testString2)); }

@Test public void testRemoveWithFirstElement() { SinglyLinkedList l = new SinglyLinkedList(); String testString = "Godzilla"; String testString2 = "Mothra"; l.add(testString); l.add(testString2); l.remove(testString); assertFalse(l.contains(testString)); }

}