package linkedlists; public class CircularlyLinkedList { private static class Node { private E element; private Node next; // a reference to the subsequent node in the list

public Node(E e, Node n) { element = e; next = n; } public E getElement() { return element; }

public Node getNext() { return next; }

public void setNext(Node n) { next = n; } } //----------- end of nested Node class -----------

// instance variables of the CircularlyLinkedList private Node tail = null; // we store tail (but not head)

/** Number of nodes in the list */ private int size = 0; // number of nodes in the list

/** Constructs an initially empty list. */ public CircularlyLinkedList() { } // constructs an initially empty list public int size() { return size; } public boolean isEmpty() { return size == 0; } public E first() { // returns (but does not remove) the first element if (isEmpty()) return null; return tail.getNext().getElement(); // the head is *after* the tail } public E last() { // returns (but does not remove) the last element if (isEmpty()) return null; return tail.getElement(); } public void rotate() { // rotate the first element to the back of the list if (tail != null) // if empty, do nothing tail = tail.getNext(); // the old head becomes the new tail } public void addFirst(E e) { // adds element e to the front of the list if (size == 0) { tail = new Node<>(e, null); tail.setNext(tail); // link to itself circularly } else { Node newest = new Node<>(e, tail.getNext()); tail.setNext(newest); } size++; } public void addLast(E e) { // adds element e to the end of the list addFirst(e); // insert new element at front of list tail = tail.getNext(); // now new element becomes the tail } public E removeFirst() { // removes and returns the first element if (isEmpty()) return null; // nothing to remove Node head = tail.getNext(); if (head == tail) tail = null; // must be the only node left else tail.setNext(head.getNext()); // removes "head" from the list size--; return head.getElement(); } public String toString() { if (tail == null) return "()"; StringBuilder sb = new StringBuilder("("); Node walk = tail; do { walk = walk.getNext(); sb.append(walk.getElement()); if (walk != tail) sb.append(", "); } while (walk != tail); sb.append(")"); return sb.toString(); } //main method public static void main(String[] args) { //(LAX, MSP, ATL, BOS) CircularlyLinkedList circularList = new CircularlyLinkedList(); circularList.addFirst("LAX"); circularList.addLast("MSP"); circularList.addLast("ATL"); circularList.addLast("BOS"); // System.out.println(circularList); circularList.removeFirst(); System.out.println(circularList); circularList.rotate(); System.out.println(circularList);

// } }

In this exercise you will add a clone() method to CircularlyLinkedList class from above example. Write a main method to test the new method. Make sure to properly link the new chain of nodes.