Question

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

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 :)