+1 (315) 557-6473 

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


Implement node linked lists and circular lists in Java programming language
Implement node linked lists and circular lists in Java programming language 1
Implement node linked lists and circular lists in Java programming language 2
Implement node linked lists and circular lists in Java programming language 3

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

 }

}