Program To Implement Node, Linked Lists and Circular Linked Lists Using Java Programming Language Assignment Solutions

Instructions

Objective

Write a program to implement node, linked lists and circular linked lists using Java programming language.

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