JAVA

CircularDoublyLinkedList.java

public class CircularDoublyLinkedList {

//---------nested Node class---------

private static class Node {

//reference to the element stored at this node

private E element;

//reference to the previous node in the list

private Node prev;

//reference to the subsequent node in the list

private Node next;

public Node(E e, Node p, Node n) {

element = e;

prev = p;

next = n;

}

public E getElement() {

return element;

}

public Node getPrev() {

return prev;

}

public Node getNext() {

return next;

}

public void setPrev(Node p) {

prev = p;

}

public void setNext(Node n) {

next = n;

}

}

//----------end of nested Node class---------

//instance variables of the CircularDoublyLinkedList

//last node

private Node tail = null;

/umber of nodes in the list

private int size = 0;

//boolean whether list is moving forward or in reverse

private boolean forward;

//constructs a new empty list

public CircularDoublyLinkedList() {

//create head

tail = new Node(null,null,null);

//set up head's next node to point at itself

tail.setNext(tail);

//set up head's previous node to point at itself

tail.setPrev(tail);

}

//access methods

//Returns the number of elements in the linked list

public int size() {

return size;

}

//Test whether the linked list is empty

public boolean isEmpty() {

return size == 0;

}

//returns (but does not remove) the first element of the list

public E first() {

if (isEmpty())

return null;

if (forward) {

return tail.getNext().getElement();

}

else

return tail.getPrev().getElement();

}

//returns (but does not remove) the last element

public E last() {

if (isEmpty())

return null;

if (forward) {

return tail.getPrev().getElement();

}

else

return tail.getNext().getElement();

}

//public update methods

//rotate the first element to the back of the list

public void rotate() {

//declare new variables

Node first = tail.getNext();

Node last = tail.getPrev();

Node firstNext = first.getNext();

Node lastPrev = last.getPrev();

//if empty, do nothing

if (isEmpty() || size == 1) {

return;

}

//if have 2 elements, reassign elements

else if (size == 2) {

tail.setPrev(first);

tail.setNext(last);

first.setPrev(last);

first.setNext(tail);

last.setPrev(tail);

last.setNext(first);

}

//if have more than 2 elements, reassign elements

else {

//if moving clockwise

if (forward) {

tail.setPrev(lastPrev);

tail.setNext(last);

first.setPrev(last);

last.setPrev(tail);

last.setNext(first);

lastPrev.setNext(tail);

}

//if moving counterclockwise

else {

tail.setPrev(first);

tail.setNext(firstNext);

first.setPrev(last);

first.setNext(tail);

last.setNext(first);

firstNext.setPrev(tail);

}

}

}

//rotate in the reverse order

public void reverse() {

forward = !forward;

}

//Adds element e to the front of the list

public void addFirst(E e) {

if (forward)

addBetween(e,tail,tail.getNext());

else

addBetween(e,tail.getPrev(),tail);

}

//Adds element e to the end of the list

public void addLast(E e) {

if (forward)

addBetween(e,tail.getPrev(),tail);

else

addBetween(e,tail,tail.getNext());

}

//Removes and returns the first element of the list

public E removeFirst() {

if (isEmpty())

return null;

if (forward)

return remove(tail.getNext());

else

return remove(tail.getPrev());

}

//Removes and returns the last element of the list

public E removeLast() {

if (isEmpty())

return null;

if (forward)

return remove(tail.getPrev());

else

return remove(tail.getNext());

}

//private update methods

//Adds elements e to the linked list in between the given nodes

private void addBetween(E e, Node predecessor, Node successor) {

//create and link a new node

Node newest = new Node(e, predecessor, successor);

predecessor.setNext(newest);

successor.setPrev(newest);

size++;

}

//Removes the given node from the list and returns its element

private E remove(Node node) {

Node predecessor = node.getPrev();

Node successor = node.getNext();

predecessor.setNext(successor);

successor.setPrev(predecessor);

size--;

return node.getElement();

}

}

1. Program the generic CircularDoubl yLinkedList class. See appendix for CDLL representation. - Use the circularly and doubly linked list classes from our notes as a basis. - Start with the DLL and think of how it can work circularly. - Sentinels are not required, only reference to the last node. - Node will have references to the next and previous nodes. - addBetween and remove private utilities will be used, all adding and removing will work like doubly. - Your CircularlyDoublyLinkedList class will support the following public methods: size () Returns the number of elements in the list. isEmpty () Returns true if the list is empty, and false otherwise. first () Returns (but does not remove) the first element in the list. last () Returns (but does not remove) the last element in the list. addFirst (e) Adds a new element to the front of the list. addLast (e) Adds a new element to the end of the list. removeFirst () Removes and returns the first element of the list. removeLast () Removes and returns the last element of the list. rotate () Advances to the next element in the list. contains (e) Returns true if e is in the list, and false otherwise 2. Create the following classes: a) Student stores the student number and name of a student. Include an equals method to check if an object is the same as an instance of the student. (Two students are considered the same if they have the same student number and name). Include any methods required to retrieve student details. b) WaitlistedStudent is a type of Student that has a Status and some number of days left to register. - Add a constructor that works the same way that a Student is created but initializes the registration status to Waitlisted and the number of days left to register to 0 . - Add a constructor that allows the number of days left to register to be specified - Include any methods required to retrieve or update the status or number of days left to register. - Status is an enum type: Waitlisted, PermittedToRegister c) CourseWaitlist class that simulates the random operation on a course waitlist with some waitlisted students. Note: most of the work will be done here. Assign1PartA_Driver should have only a minimal amount of code: e.g., declare/create a CourseWaitlist instance, create initial waitlisted students, and initiate the course waitlist simulation. - Fields - a CircularDoublyLinkedList of waitlisted students - any other field required to manage the game - Upon instantiation, set up the initial list of waitlisted students (use 4 initial waitlisted students for your demo/sample data) and grant the first student permission to register (when a student is granted permission, they have two days to register). Begin the simulation. - The simulation randomly chooses one of the operations and continues until the list is empty or 20 operations have been performed. - After each operation, the list of students on the waitlist is displayed together with the waitlist status and the number of days left to register (if they have permission to register). - When the simulation stops, the termination condition of the simulation is displayed and the final waitlist is also displayed. 3. Create a driver class called Assign1PartA_Driver that invokes a simulation of the course waitlist using a list of four waitlisted students of your choice. Sample Output 3 System chose option 1: No addition to waitlist (status/days left may change) 4444444 : Muskan, Status: PermittedToRegister Days left: 2 5555555 : Mankomal, Status: Waitlisted 2222222 : Anna, Status: Waitlisted 3333333 : Ishit, Status: Waitlisted System chose option 3: Muskan registers 5555555 : Mankomal, Status: PermittedToRegister Days left: 2 2222222 : Anna, Status: Waitlisted 3333333 : Ishit, Status: Waitlisted System chose option 1: No addition to waitlist (status/days left may change) 5555555 : Mankomal, Status: PermittedToRegister Days left: 1 2222222 : Anna, Status: Waitlisted 3333333 : Ishit, Status: Waitlisted System chose option 1: No addition to waitlist (status/days left may change) 2222222 : Anna, Status: PermittedToRegister Days left: 2 3333333 : Ishit, Status: Waitlisted 5555555 : Mankomal, Status: Waitlisted System chose option 2: A new student joins the waitlist Enter student name and number: 6666666 Jasleen 2222222 : Anna, Status: PermittedToRegister Days left: 1 3333333 : Ishit, Status: Waitlisted 5555555 : Mankomal, Status: Waitlisted 6666666 : Jasleen, Status: Waitlisted System chose option 4: Checks if a student is waitlisted Enter student name and number: 6666666 Jasleen Student found in waitlist 3333333 : Ishit, Status: PermittedToRegister Days left: 2 5555555 : Mankomal, Status: Waitlisted 6666666 : Jasleen, Status: Waitlisted 2222222 : Anna, Status: Waitlisted System chose option 3: Ishit registers 5555555 : Mankomal, Status: PermittedToRegister Days left: 2 6666666 : Jasleen, Status: Waitlisted 2222222 : Anna, Status: Waitlisted System chose option 3: Mankomal registers 6666666 : Jasleen, Status: PermittedToRegister Days left: 2 2222222 : Anna, Status: Waitlisted System chose option 4: Checks if a student is waitlisted Enter student name and number: 6666666 Jasleen Student found in waitlist 6666666 : Jasleen, Status: PermittedToRegister Days left: 1 2222222 : Anna, Status: Waitlisted System chose option 4: Checks if a student is waitlisted Enter student name and number: 7777777 John Student not found in waitlist 2222222 : Anna, Status: PermittedToRegister Days left: 2 6666666 : Jasleen, Status: Waitlisted System chose option 4: Checks if a student is waitlisted Enter student name and number: 2222222 Anna Student found in waitlist 2222222 : Anna, Status: PermittedToRegister Days left: 1 6666666 : Jasleen, Status: Waitlisted System chose option 1: No addition to waitlist (status/days left may change) 6666666 : Jasleen, Status: PermittedToRegister Days left: 2 2222222 : Anna, Status: Waitlisted System chose option 1: No addition to waitlist (status/days left may change) 6666666 : Jasleen, Status: PermittedToRegister Days left: 1 2222222 : Anna, Status: Waitlisted System chose option 2: A new student joins the waitlist Enter student name and number: 7777777 John 2222222 : Anna, Status: PermittedToRegister Days left: 2 7777777 : John, Status: Waitlisted 6666666 : Jasleen, Status: Waitlisted System chose option 2: A new student joins the waitlist Enter student name and number: 8888888 Joey 2222222 : Anna, Status: PermittedToRegister Days left: 1 7777777 : John, Status: Waitlisted 6666666 : Jasleen, Status: Waitlisted 8888888 : Joey, Status: Waitlisted Reached 20 days/operations! Final waitlist: 2222222 : Anna, Status: PermittedToRegister Days left: 1 7777777 : John, Status: Waitlisted 6666666 : Jasleen, Status: Waitlisted 8888888 : Joey, Status: Waitlisted