Download the Assn1_code.zip file from the class website. In there, you will find 3 files:

Node.java

CDLL.java

CDLLTester.java

You are given code for Node and CDLLTester which you are not allowed to change. CDLL is a skeleton file of functions that you are tasked with completing.

CDLL stands for Circular Doubly Linked List. It is a modified Linked List data structure where the last node in the list always points to the first node making the list circular. For example, if you insert 4, then 3, then 5. The list would be:

5 -> 3 -> 4 and then 4's "next" pointer points to 5

The list is also Doubly Linked. This means that each node contains a reference to the next node and the previous node. In the same example, the CDLL actually looks like

5 <--> 3 <--> 4. 4's "next" pointer points to 5, 4's "previous" pointer points to 3 and 3's previous points to 5. Note also that 5's previous pointer points to 4 keeping the list Circular.

Note that all nodes in the list will have a next and previous pointer point to an existing node. If there is only one Node in the list, the next and previous both point to the same Node.

The CDLL only maintains a current Node and a current size. Current represents the Node where the last action takes place. For example, after the inserts above are done, the current Node will be pointing to 5 (it was the last Node inserted into the list). If we do a search for a Node containing a value of 4, then after it is found, the current Node is now pointing to Node 4.

You are to complete the insert, update, delete, search and print functions of the CDLL. The CDLLTester is designed to test your functions based on these requirements with test data. It cannot change. This assignment will be demo'd to me in class. The output of your program must match the expected output shown in the code. If you think something is in error with the code or function signatures, let me know.

If you are using a different programming language (Swift, C++, python, etc.), be sure to first convert the Node and CDLLTester classes as appropriate so the same expected output is achieved.

node. java

public class Node { public int data; public Node next, previous; }

CDLLTesfer.java

/** * CDLLTester tests certain operations of the Circular LinkedList. * Do not modify anything inside this class. */ public class CDLLTester { public static void main(String[] args) { CDLL list = new CDLL();

/* Testing insert and delete method. */ list.insert(5); if (list.delete(5) == true) System.out.println(Node 5 was deleted); else System.out.println(Node 5 was not deleted); if (list.delete(5) == true) System.out.println(Node 5 was deleted); else System.out.println(Node 5 was not deleted); list.print();

/* Testing insert and print methods. */ list.insert(9); list.insert(0); list.insert(3); list.insert(4); list.print();

CDLL.java

public class CDLL { private Node current = null; private int size = 0;

/* Insert creates a new node and puts in front of the current Node * The new node inserted becomes the lists current Node */ public void insert(int data) { }

/* Search starts from the current location and looks * for the given data value. If the Node is found, it * returns the Node. Otherwise, it returns null */ public Node search(int data) { }

/* Update searches for the given oldData value. * If the Node is found, it changes the node value to * newValue and returns true. Otherwise, it returns false * If the node is found, that node also becomes * the current Node */ public boolean update(int oldValue, int newValue) { }