Instructions
Requirements and Specifications
Source Code
NODE
// University of Manitoba - COMP 2140 - Fall 2020
//
// This code implements the class Node, including
// the following public methods:
// Node - constructor
// getValue - return the int value stored in the node
// getNext - return the node's next pointer
// setValue - update the int value stored in the node
// setNext - update the node's next pointer
public class Node {
// INSTANCE VARIABLES
protected int value; // value stored in this node
protected Node next; // pointer to the next node in the linked list
// CONSTRUCTORS
public Node (int newValue, Node newNext) {
value = newValue;
next = newNext;
}
public Node (int newValue) { this(newValue, null); }
// ACCESSOR METHODS
public int getValue () { return value; }
public Node getNext () { return next; }
// ACTION METHODS
public void setValue (int newValue) { value = newValue; }
public void setNext (Node newNext) { next = newNext; }
}
LINKED LIST
// University of Manitoba - COMP 2140 - Fall 2020
//
// This code implements the class LinkedList, including
// the following public methods:
// LinkedList - constructor
// insert - insert a new node storing the int newValue at the head of the list
// delete - delete the node at the head of the list
// getHead - return a reference to the node at the front of the list
// print - print the ints stored in the linked list starting at head, printing
// at most maxLength items (in case the list is circular)
public class LinkedList {
// INSTANCE VARIABLES
protected Node head;
// CONSTRUCTOR
public LinkedList () { head = null; }
// ACCESSOR METHODS
// getHead
// Return the node at the head of the list.
public Node getHead () { return head; }
// print
// Print the ints stored in the linked list starting at head, printing
// at most maxLength items (in case the list is circular).
public void print (int maxLength) {
Node printNode = head;
int counter = 0;
while (printNode != null && counter < maxLength) {
System.out.print(printNode.getValue() + " ");
printNode = printNode.getNext();
counter++;
}
System.out.println("");
}
// ACTION METHODS
// insert
// Insert a new node storing newValue at the head of the linked list.
public void insert (int newValue) {
head = new Node(newValue, head);
}
// delete
// Delete the node at the head of the linked list.
public void delete () {
if (head != null) head = head.getNext();
}
}
CIRCULAR LINKED LIST
//
//
// This code implements the class CircularList, including
// the following public methods:
// CircularList - constructor
// isCircularRecursive - returns true if the linked list is circular
// isCircularIterative - returns true if the linked list is circular
// getNumRecursiveCalls - return the number of recursive calls performed
// getNumNodesVisited - return the number of linked list nodes visited
// getNumIterations - return the number of iterations performed
// printList - print the data stored in the linked list
// printStats - print the statistics collected while running
// resetNumRecursiveCalls - set numRecursiveCalls to 0
// resetNumNodesVisited - set numNodesVisited to 0
// resetNumIterations - set numIterations to 0
// resetStats - reset all statistics to 0
// setList - refer to a new linked list
// generateRandomList - generate a new linked list of length n with random
// list is circular (1), not circular (2), or circular
// with probability 0.5 (0).
// main - run tests
// FOR THE LAB YOU CAN EDIT THE METHODS main AND testSuite
public class CircularList {
// INSTANCE VARIABLES
private LinkedList list; // we want to determine whether this
// linked list is circular
private int numRecursiveCalls, numNodesVisited, numIterations;
// store the # recursive call, # nodes visited, # iterations performed
// by the iterative and recursive algorithms for checking whether
// the linked list is ciruclar.
// CONSTRUCTORS
public CircularList (LinkedList inputList) {
numRecursiveCalls = 0; // set all counts to 0
numNodesVisited = 0;
numIterations = 0;
}
public CircularList () { this(new LinkedList()); }
// if no linked list is specified, instantiate a new empty linked list
// ACCESSOR METHODS
// isCircularRecursive
// Return true if list is circular, false otherwise, using a
// recursive algorithm. The algorithm uses two list pointers,
// called slow and fast, that traverse the list at different speeds.
// Two outcomes are possible: either the fast pointer encounters
// the end of the list (a null next pointer) or the fast pointer loops
// around and catches up to the slow pointer.
public boolean isCircularRecursive() {
boolean result = false;
Node head = list.getHead();
if (head == null)
result = false;
else {
numNodesVisited++;
result = isCircularHelper(head, head.getNext());
}
return result;
}
private boolean isCircularHelper(Node slowNode, Node fastNode) {
boolean result = false;
numRecursiveCalls++;
if (slowNode == null || fastNode == null) // list terminates
result = false;
else if (fastNode.getNext() == null) { // list terminates
result = false;
numNodesVisited++;
}
else if (slowNode == fastNode) // fast has caught slow
result = true;
else if (slowNode == fastNode.getNext()) { // fast has caught slow
result = true;
numNodesVisited++;
}
else { // move slow ahead one node, and fast ahead two nodes
result = isCircularHelper(slowNode.getNext(), fastNode.getNext().getNext());
numNodesVisited += 3;
}
return result;
}
// isCircularRecursive
// Return true if list is circular, false otherwise, using an
// iterative algorithm. The algorithm uses two list pointers,
// called slow and fast, that traverse the list at different speeds.
// Two outcomes are possible: either the fast pointer encounters
// the end of the list (a null next pointer) or the fast pointer loops
// around and catches up to the slow pointer.
public boolean isCircularIterative () {
Node slow, fast;
boolean result = false;
slow = list.getHead();
if (slow == null) // list terminates
result = false;
else {
fast = slow.getNext();
numNodesVisited++;
while (fast != null && fast.getNext() != null && slow != fast && slow != fast.getNext()) {
slow = slow.getNext();
fast = fast.getNext().getNext();
numNodesVisited += 3;
numIterations++;
}
if (fast == null)
result = false; // list terminates
else if (fast.getNext() == null) {
result = false; // list terminates
numNodesVisited++;
}
else if (slow == fast)
result = true; // fast caught slow
else {
result = true; // fast caught slow
numNodesVisited++;
}
}
return result;
}
// accessor methods for numRecursiveCalls, numNodesVisites, numIterations
public int getNumRecursiveCalls () { return numRecursiveCalls; }
public int getNumNodesVisited () { return numNodesVisited; }
public int getNumIterations () { return numIterations; }
// printList
// Print the data stored in list in order.
public void printList (int maxLength) { list.print(maxLength); }
// printStats
// Print stats collected during execution of the recursive and iterative
// algorithms for checking whether list is circular.
public void printStats () {
System.out.println("number of recursive calls: " + getNumRecursiveCalls() );
System.out.println("number of linked list nodes visited: " + getNumNodesVisited() );
System.out.println("number of iterations: " + getNumIterations() );
}
// ACTION METHODS
// Set numberRecursiveCalls, numNodesVisited, numIterations to 0.
public void resetNumRecursiveCalls () { numRecursiveCalls = 0; }
public void resetNumNodesVisited () { numNodesVisited = 0; }
public void resetNumIterations () { numIterations = 0; }
public void resetStats () {
resetNumRecursiveCalls();
resetNumNodesVisited();
resetNumIterations();
}
// setList
// Update list to refer to a new linked list.
public void setList (LinkedList newList) {
list = newList;
}
// generateRandomList
// Set list to a new linked list of length length, whose data
// are ints generated at random between 0 and maxValue-1. The loop
// is circular with probability 0.5 if circularFlag is 1, 1 if
// circularFlag is 1, and 0 if circularFlag is 2.
public void generateRandomList(int length, int circularFlag) {
boolean isCircular = false;
int loopNodeIndex = (int) (Math.random() * length);
int maxValue = 1000;
Node lastNode = null;
Node loopNode = null;
if (circularFlag == 0) // choose random boolean
isCircular = (Math.random() < 0.5);
else if (circularFlag == 1) // list is circular
isCircular = true;
else // list is not circular
isCircular = false;
list = new LinkedList();
for (int i = 0 ; i < length ; i++) {
int newValue = (int) (Math.random() * maxValue);
list.insert(newValue); // store random int
if (i == 0) // store reference to last node in list
lastNode = list.getHead();
if (i == loopNodeIndex) // store reference to node to
// which the last node will
// refer if list is circular
loopNode = list.getHead();
}
if (isCircular && lastNode != null) lastNode.setNext(loopNode);
}
// main
// Feel free to modify this code.
public static void main (String [] args) {
int listLength = 20; // length of linked list
int maxPrintLength = 5 * listLength; // max items to print if
// list is circular
CircularList test = new CircularList();
test.generateRandomList(listLength, 0); // generate new list
// at random
test.resetStats();
System.out.println("Iterative circular list check: " + test.isCircularIterative());
System.out.println("Recursive circular list check: " + test.isCircularRecursive());
test.printStats();
test.printList(maxPrintLength);
testSuite(listLength, maxPrintLength);
}
private static void testSuite (int listLength, int maxPrintLength) {
// EDIT THIS METHOD
}
}