Circular Doubly Linked List

Open Eclipse, create a new Java project, and add a new class called CircularDoublyLinkedList.

This class will be based heavily on the doubly linked list written below. You can use the same node inner class, without modification, as well as the private helper methods. However, this list will NOT have a head or a tail.

Code:

public class DLList { private Node header; private Node trailer; private int size; public DLList() { header = new Node<>(null, null, null); trailer = new Node<>(null, null, header); header.next = trailer; size = 0; } /** * This method inserts value v in a new node bteween first and second * @param v value to insert * @param first first node * @param second second node */ private void insertBetween(E v, Node first, Node second) { Node newNode = new Node<>(v, second, first); second.prev = newNode; first.next = newNode; size++; } /** * Removes the node beteween first and second. Throws illegalStateException * if the list is empty * @param first first node * @param second second node * @return the value deleted */ private E removeBetween(Node first, Node second) throws IllegalStateException { if(header.next == trailer) //if(size == 0) { throw new IllegalStateException("Cannot delete from empty list"); } E valueToReturn = first.next.value; first.next = second; second.prev = first; size--; return valueToReturn; } public void insertAtHead(E v) { insertBetween(v, header, header.next); } public void insertAtTail(E v) { insertBetween(v, trailer.prev, trailer); } public E removeHead() throws IllegalStateException { return removeBetween(header, header.next); } public E removeTail() throws IllegalStateException { return removeBetween(trailer.prev, trailer); } public String toString() { if(size == 0) { return "list is empty!"; } String r = ""; Node temp = header.next; while(temp != trailer) { r += temp.toString() + " "; temp = temp.next; } return r; } public void printBackward() { if(size == 0) { System.out.println("list is empty!"); } Node temp = trailer.prev; while(temp != header) { System.out.print(temp + " "); temp = temp.prev; } System.out.println();

} private static class Node { private T value; private Node next; private Node prev; public Node(T v, Node n, Node p) { value = v; next = n; prev = p; } public String toString() { return value.toString(); } }

}

In a circularly linked list, the first and last element are linked together, so that the list becomes a loop. Because of this, we only need a reference to a single node, called the cursor. Thus, CircularDoublyLinkedList will only have two member variables:

cursor -- a reference to one of the nodes in the list, or null if the list is empty

size -- an integer storing the number of nodes in the list

Implement the following methods:

A constructor that creates an empty list

addAfterCursor(T value) -- adds a new node for the given value after the cursor. Be sure you handle the empty list case correctly. The cursor should not change unless the list is empty.

deleteCursor() -- remove the node pointed to by the cursor and return its value. If the list is empty, you should throw an appropriate exception. The cursor should be updated to point to the node after cursor, or to null if the list is empty after deletion.

advanceCursor(int n) -- move the cursor n elements forward. Since the list is circular, this operation will always work. Do nothing if the list is empty.

getValue() -- return the value stored at the cursor. If the list is empty, throw an appropriate exception.

Add a Driver class with a main method, and test your list by performing a "lottery" simulation:

Add the numbers 1-10 to a CircularDoublyLinkedList

While the list is not empty:

Advance the cursor a random amount

Print the element at the cursor

Delete the cursor.