Create a Circular Doubly Linked List data structure. The Node structure is defined as follows (we will use integers for data elements):

public class Node

{

public int data;

public Node next;

public Node previous;

}

The Circular Linked List class definition is as follows:

public class CircularLinkedList

{

public int currentSize;

public Node current;

}

This design modifies the standard linked list. In the standard that we discussed in class, there is a head node that represents the first node in the list and each node contains a reference to the next node in the list until the chain of nodes reach null. In this Circular Doubly Linked List (CDLL), each node has a reference to a next and previous node. When new Node elements are added to the CDLL, the structure looks like a standard linked list with the last nodes next pointer pointing to the first. In this way, no next pointers of every Node in the CDLL are ever pointing to null.

Since this is also a doubly linked list, the previous pointers of each Node are pointing to the Node behind it in the CDLL. Also, since this is a CDLL, the first Nodes previous pointer should also be pointing to the last Node and no previous pointers of every Node are ever pointing to null.

For example, if a CDLL has elements 5, 3 and 4 and current is pointing to 3, the CDLL should look like:

Key observations with this structure:

1.The current node in the CDLL is always pointing to an existing node. If current is null, the CDLL should be empty

2.All Nodes next and previous pointers are pointing to an existing node

3.Traversing all elements means starting at the current node and going in either direction until you come back to the current node

Part 1) Complete the following functions for the CDLL:

public CircularDoublyLinkedList()

public void insertBeforeCurrent(int n)

public void insertAfterCurrent(int n)

public Node search(int n)

public boolean update(int o, int n)

public boolean delete(int n)

public void printSize()

public void printCurrent()

public void printForward()

public void printReverse()

The requirements for each function are as follows:

CircularDoublyLinkedList():

-This function is the default constructor for the CDLL and creates an empty list of size 0

insertBeforeCurrent(int n):

-This creates a new node and inserts it behind the current node. If the list is empty, the new nodes next and previous pointers point to itself. If the list has at least 1 element, the new node is placed behind current while keeping the CDLL structure intact. When complete, the new node inserted is the new current node

insertAfterCurrent(int n):

-This creates a new node and inserts it after the current node. If the list is empty, the new nodes next and previous pointers point to itself. If the list has at least 1 element, the new node is placed after current while keeping the CDLL structure intact. When complete, the new node inserted is the new current node

search(int n):

-This searches the CDLL for a Node where its data property matches the given n. If a match is found, the Node is returned and the current Node in the CDLL is now this Node. If a match is not found, the function returns null and the current Node should be the same as when the function started

update(int o, int n):

-This searches the CDLL for a Node where its data property matches the given o. If a match is found, the Nodes data element is updated to the given n and the function returns true. The current Node in the CDLL is now this Node. If a match is not found, the function returns false and the current Node should be the same as when the function started

delete(int n):

-This searches the CDLL for a Node where its data property matches the given n. If a match is found, the Nodes is removed from the CDLL while keeping the structure intact and the current Node is the Node that is after the Node that was removed. The function returns true. If a match is not found, the function returns false and the current Node should be the same as when the function started

print functions:

-Size: displays the number of elements in the CDLL

-Current: displays the data value of the current element in the CDLL. If the list is empty, it prints Empty List

-Forward: displays all Node data values starting from current and traversing each element in next order. The current Node should be the same when the function completes. If the list is empty, it prints Empty List

-Reverse: displays all Node data values starting from current and traversing each element in previous order. The current Node should be the same when the function completes. If the list is empty, it prints Empty List

Part 2) Write a main test program that allows the user to interactively test all these functions. The user must be able to insert, change, delete and search elements at any time and display the CDLL using any of the four print functions required. The demo of the program will be such that I will be testing to make sure everything works to my satisfaction.

When developing and testing this project, remember every function (except the constructor) should be dealing with 3 scenarios:

1.Empty lists

2.Lists with only 1 Node

3.Lists with more than 1 Node

CDLL Example current0x4245ABCO 3 0x44001FAC 0x28ABDD92 4 0x28ABDD92 0x4245ABCO 0x4245ABCO 0x44001FAC CDLL Example current0x4245ABCO 3 0x44001FAC 0x28ABDD92 4 0x28ABDD92 0x4245ABCO 0x4245ABCO 0x44001FAC