Question

1. Design and implement a CircularLinkedList, which is essentially a linked list in which the next...

1. Design and implement a CircularLinkedList, which is essentially a linked list in which the next reference of the tail node is set to refer back to the head of the list (rather than null) . Start from the SinglyLinkedList provided in the Lecture (not the built-in Java LinkedList class).

2. Starting from  SinglyLinkedList you will need to modify or complete methods: first(), last(), addFirst(), addLast(), removeFirst(), toString(), and also create a new rotate() method which will move the tail to tail.getNext. Note that no head Node is needed in the circular linked list because you can refer to it as tail.next().

toString method: You will have to modify the (while loop condition of) the toString() method from SinglyLinkedList to avoid an infinite loop: Modify the while loop so the String contains the elements of the list from two rounds in CircularLinkedList showing the circular nature of this new data structure you will design.

CircularLinkedList.java:

import java.util.Scanner;

public class CircularLinkedList <E> {

    //Instance variables
    private Node<E> tail;
    private int size;
    /*
        init instance variables
     */
    public CircularLinkedList()
    {
    }

    /*
        return the size of the linked list
     */
    public int size()
    {
    }

    /*
        checks if the linked list is empty
     */
    public boolean isEmpty()
    {
    }
    /*
        if linked list is empty return null
        if not empty return the first element
     */
    public E first()
    {
    }

    /*
        if linked list is empty return null
        if not empty return last element
     */
    public E last()
    {
    }

    /*
        move tail to the next node
     */
    public void rotate()
    {
    }

    /*
        add element to the first of the linked list
        increase the size
     */
    public void addFirst(E e)
    {
    }

    /*
        add element to the end of the linked list
        increase size
     */
    public void addLast(E e)
    {
    }

    /*
        take out the first element
        decrease the size
        return first element or null


     */
    public E removeFirst()
    {
    }

    public String toString()
    {
        String s;
        Node<E> n;
        if ( tail == null )
            return "null";
        s = "[";
        n = tail.getNext();
        if (n==null)
        {
            return s+ "empty list]";
        }
        int iter =0;
        while (n!=null&&iter<2*size)
        {
            iter++;
            s = s+ n.getElement();
            if (n.getNext()!=null) s = s + ", ";
            n = n.getNext();
        }
        return s+"]";
    }
    public static void main(String args[])
    {
        String[] cars = { "prius", "rav4", "subaru", "crv", "pilot"};
        CircularLinkedList<String> carslist = new CircularLinkedList<String>();
        for (String i: cars)
        {
            carslist.addLast(i);
        }
        System.out.println("linkedlist:"+ carslist);
    }
}

Node.java:

public class Node<E> {
    // Instance variables:
    private E element;
    private Node<E> next;
    /** Creates a node with null references to its element and next node. */
    public Node() {
        this(null, null);
    }
    /** Creates a node with the given element and next node. */
    public Node(E e, Node<E> n) {
        element = e;
        next = n;
    }
    // Accessor methods:
    public E getElement() {
        return element;
    }
    public Node<E> getNext() {
        return next;
    }
    // Modifier methods:
    public void setElement(E newElem) {
        element = newElem;
    }
    public void setNext(Node<E> newNext) {
        next = newNext;
    }
}

Homework Answers

Answer #1

Here is the solution code with specifice java file :

**************************************** CircularLinkedList.java ***********************************************

public class CircularLinkedList <E> {

//Instance variables
private Node<E> tail;
private int size;
/*
init instance variables
*/
public CircularLinkedList()
{
   tail = null;
   size = 0;
}

/*
return the size of the linked list
*/
public int size()
{
   return size;
}

/*
checks if the linked list is empty
*/
public boolean isEmpty()
{
   return size==0;
}
/*
if linked list is empty return null
if not empty return the first element
*/
public E first()
{
   if(this.size==0) {
       return null;
   }
   return tail.getNext().getElement();
}

/*
if linked list is empty return null
if not empty return last element
*/
public E last()
{
   if(this.size==0) {
       return null;
   }
   return tail.getElement();
}

/*
move tail to the next node
*/
public void rotate()
{
   if(tail!=null)
       tail = tail.getNext();
}

/*
add element to the first of the linked list
increase the size
*/
public void addFirst(E e)
{
   Node<E> newNode = new Node<>(e,null);
   if(tail==null) {
   tail = newNode;
   newNode.setNext(tail);
   }else {
       newNode.setNext(tail.getNext());
       tail.setNext(newNode);  
   }
   size++;
}

/*
add element to the end of the linked list
increase size
*/
public void addLast(E e)
{
   Node<E> newNode = new Node<>(e,null);
   if(tail==null) {
   tail = newNode;
   newNode.setNext(tail);
   }else {
       newNode.setNext(tail.getNext());
       tail.setNext(newNode);  
       tail = newNode;
   }
   size++;
}

/*
take out the first element
decrease the size
return first element or null


*/
public E removeFirst()
{
   if(this.size==0) {
       return null;
   }else if(size==1) {
   Node<E> temp = tail;
   tail = null;
   size = 0;
   return temp.getElement();
   }else {
Node<E> temp = tail.getNext();
tail.setNext(temp.getNext());
size--;
return temp.getElement();
   }
}

public String toString()
{
String s;
Node<E> n;
if ( tail == null )
return "null";
s = "[";
n = tail.getNext();
if (n==null)
{
return s+ "empty list]";
}
int iter =0;
while (n!=null&&iter<2*size)
{
iter++;
s = s+ n.getElement();
if (n.getNext()!=null) s = s + ", ";
n = n.getNext();
}
return s+"]";
}
public static void main(String args[])
{
String[] cars = { "prius", "rav4", "subaru", "crv", "pilot"};
CircularLinkedList<String> carslist = new CircularLinkedList<String>();
for (String i: cars)
{
carslist.addLast(i);
}
System.out.println("linkedlist:"+ carslist);
}
}

************************************** Node.java file ******************************************************

public class Node<E> {
// Instance variables:
private E element;
private Node<E> next;
/** Creates a node with null references to its element and next node. */
public Node() {
this(null, null);
}
/** Creates a node with the given element and next node. */
public Node(E e, Node<E> n) {
element = e;
next = n;
}
// Accessor methods:
public E getElement() {
return element;
}
public Node<E> getNext() {
return next;
}
// Modifier methods:
public void setElement(E newElem) {
element = newElem;
}
public void setNext(Node<E> newNext) {
next = newNext;
}
}

*************************************** Console Output Sceenshot ***********************************************

If you will face any issue in the code, let me know through comments.

Thanks :)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
public class LinkedList {       private Node list;       public LinkedList()       {           list =...
public class LinkedList {       private Node list;       public LinkedList()       {           list = null;       }       public Node getList()       {           return list;       }       . . .//other methods       // insert method printHighEarners here       // insert method lowestPaidEmployeeRec       private class Node       {           public Employee data;           public Node next;           public Node(Employee emp)           {               data = emp;               next = null;           }           public String toString()...
The following program creates a linked list which contains 5 links. Add a method called doubleValue()...
The following program creates a linked list which contains 5 links. Add a method called doubleValue() to the LinkedList class. The doubleValue() method must double the value of the number data field in each link. Add the required code to the main() method to call the doubleValue() method and display the revised list. public class Link { private int number; private Link next;      public Link(int x) { number = x; }    public void displayLink() { System.out.println("The number is:...
The following program creates a linked list which contains 5 links. Add a method called doubleValue()...
The following program creates a linked list which contains 5 links. Add a method called doubleValue() to the LinkedList class. The doubleValue() method must double the value of the number data field in each link. Add the required code to the main() method to call the doubleValue() method and display the revised list. public class Link { private int number; private Link next;      public Link(int x) { number = x; }    public void displayLink() { System.out.println("The number is:...
IN JAVA Language- Singly Linked List Implementation Implement a Linked List in your language. Use your...
IN JAVA Language- Singly Linked List Implementation Implement a Linked List in your language. Use your Can class. You need to create a driver that makes several Can objects and places them in alphabetical order in a list. Identify the necessary methods in a List Linked implementation. Look at previous Data Structures (stack or queue) and be sure to include all necessary methods. NOT USE your language's Library List . You will receive zero points. Write a LinkedList class. Include...
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete....
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete. Return true or false to indicate success or failure. Delete the memory the node was using The algorithm for deleting a Node to a Linked List (general case): ● Begin at the head. ● Compare the id to the current node. ● If search id > current id, stop. ● Detach the current Node ○ current->previous->next = current->next ○ current->next->previous = current->previous ● Deallocate...
Given this definition of a generic Linked List node: public class LLNode {     private T...
Given this definition of a generic Linked List node: public class LLNode {     private T data;     private LLNode next;     public LLNode(T data, LLNode next) {           this.data = data;           this.next = next;     }     public void setNext(LLNode newNext){ next = newNext; }     public LLNode getNext(){ return next; }     public T getData() {return data;} } Write the findMinimumNode method body. This method returns the linked list node that contains the minimum value in the...
The class CourseList implements a simple database of students registered in a course. Complete the method...
The class CourseList implements a simple database of students registered in a course. Complete the method countAttendees in the code below such that it returns the number of students in the instance of CourseList who have not attended any classes. Your response may be written in Java or pseudocode. Your code cannot modify the linked list. The class Node is similar to the linked list node object discussed in lecture. You can use helper methods, but this is not necessary....
Java Language Add a method (convertToRing ()) that converts the list to a circular. This is,...
Java Language Add a method (convertToRing ()) that converts the list to a circular. This is, which makes the last node instead of pointing to null point to the first. Code: class Node { int value; Node nextNode; Node(int v, Node n) { value = v; nextNode = n; } Node (int v) { this(v,null); } } class LinkedList { Node head; //head = null; LinkedList() { } int length() { Node tempPtr; int result = 0; tempPtr = head;...
Java Language Add a method (convertToRing ()) that converts the list to a circular. This is,...
Java Language Add a method (convertToRing ()) that converts the list to a circular. This is, which makes the last node instead of pointing to null point to the first. Code: class Node { int value; Node nextNode; Node(int v, Node n) { value = v; nextNode = n; } Node (int v) { this(v,null); } } class LinkedList { Node head; //head = null; LinkedList() { } int length() { Node tempPtr; int result = 0; tempPtr = head;...
based on the code below, answer the questions Question 1: The LinkedList class uses another class...
based on the code below, answer the questions Question 1: The LinkedList class uses another class called Node (which is defined inside LinkedList.java). What are the fields in the Node class? Question 2: The Node class uses generics. Why? Question 3: The linkFirst method contains the following lines of code: if (f == null) last = newNode; else f.prev = newNode; What is the value of the linked list’s size attribute at this point in the code if f ==...