Hello I have JAVA DATA STRUCTURE lab assignment could you help me and add each clone methods steps Part 1. You will first add a new method to DoublyLinkedList.java from Lab1 (from LinkedLists Add the clone() method to the DoublyLinkedList class and test it by adding appropriate statements into Main class. 1. clone() : write a clone method , you will make a copy of the linked list, the copy will have its own independent nodes, but the element references that are stored in the copy nodes will be the same references as in the original list. See the textbook for this kind of clone(). This is NOT a deep copy. 2. Now, you will rewrite the clone method such that it makes a deep copy of the linked list (both nodes and the elements of the copy will be independent from the original lists.) First try the following two steps: (i) use the following code when making a new Node that is a copy of the node referenced by variable walk : Node newNode = new Node((E)(walk.getElement()).clone(), null,null); (ii) and, restrict type E in your class heading as follows since you want E to be Cloneable : public class DoublyLinkedList implements Cloneable If you try to compile this code you will get an error message saying that the clone() is protected in class Object. This is because at this time all Java knows that the generic type E is a descendent of class Object, and the clone() method in Object class is protected. Here is one way you can overcome this problem: (i) First, define a new interface called PubliclyCloneable which contains a public clone() method and extends Cloneable. Here is its definition: public interface PubliclyCloneable extends Cloneable { public Object clone()throws CloneNotSupportedException; } Any class that implements this interface needs to define a public clone() method. (ii) Now, restrict type E in your class heading as: public class DoublyLinkedList implements PubliclyCloneable (iii) Now, you can write a deep clone() method in DoublyLinkedList by making nodes as suggested before: Node newNode = new Node((E)(walk.getElement()).clone(), null); 3. To test your deep clone() method, first define a simple Person class with two instance variables name, and age. Let this class implement PubliclyCloneable and provide a public clone() method by simply calling super.clone(). Then, make a linked list of Person objects. Clone the linked list. And test to see if the Person objects in the original list and the copy are really independent. Fo example, you can change a Person objects data in one list and see if it is changed or not in the copy. DoublyLinkedList class:

public class DoublyLinkedList {

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

/**

* Node of a doubly linked list, which stores a reference to its

* element and to both the previous and next node in the list.

*/

private static class Node {

private E element; // reference to the element stored at this node

private Node prev; // reference to the previous node in the list

private Node next; // reference to the subsequent node in the list

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

element = e;

prev = p;

next = n;

}

public E getElement() {

return element;

}

/**

* Returns the node that precedes this one (or null if no such node).

* @return the preceding node

*/

public Node getPrev() { return prev; }

public Node getNext() { return next; }

public void setPrev(Node p) { prev = p; }

public void setNext(Node n) { next = n; }

}

private Node header; // header sentinel

/** Sentinel node at the end of the list */

private Node trailer; // trailer sentinel

/** Number of elements in the list (not including sentinels) */

private int size = 0; // number of elements in the list

/** Constructs a new empty list. */

public DoublyLinkedList() {

header = new Node<>(null, null, null); // create header

trailer = new Node<>(null, header, null); // trailer is preceded by header

header.setNext(trailer); // header is followed by trailer

}

int size() { return size; }

public boolean isEmpty() { return size == 0; }

public E first() {

if (isEmpty()) return null;

return header.getNext().getElement(); // first element is beyond header

}

public E last() {

if (isEmpty()) return null;

return trailer.getPrev().getElement(); // last element is before trailer

}

public void addFirst(E e) {

addBetween(e, header, header.getNext()); // place just after the header

}

public void addLast(E e) {

addBetween(e, trailer.getPrev(), trailer); // place just before the trailer

}

public E removeFirst() {

if (isEmpty()) return null; // nothing to remove

return remove(header.getNext()); // first element is beyond header

}

/**

* Removes and returns the last element of the list.

* @return the removed element (or null if empty)

*/

public E removeLast() {

if (isEmpty()) return null; // nothing to remove

return remove(trailer.getPrev()); // last element is before trailer

}

// private update methods

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.

* @param node the node to be removed (must not be a sentinel)

*/

public E remove(Node node) {

Node predecessor = node.getPrev();

Node successor = node.getNext();

if(node==header){

header=predecessor;

}else if(node==trailer){

trailer=successor;

}else{

predecessor.setNext(successor);

successor.setPrev(predecessor);}

size--;

return node.getElement();

}

/**

* Produces a string representation of the contents of the list.

* This exists for debugging purposes only.

*/

public String toString() {

StringBuilder sb = new StringBuilder("(");

Node walk = header.getNext();

while (walk != trailer) {

sb.append(walk.getElement());

walk = walk.getNext();

if (walk != trailer)

sb.append(", ");

}

sb.append(")");

return sb.toString();

}

public void addBefore(Node node, E newData){//prev next

if(node==header){

Node newest = new Node<>(newData,null,node);

node.setPrev(newest);

newest.setNext(node);

header=newest;

size++;

}

else if(node.getPrev()==header){

Node newest = new Node<>(newData, header, node);

node.setPrev(newest);

header.setNext(newest);

size++;

}else{

Node onceki = node.getPrev();

Node newest = new Node<>(newData, onceki, node);

node.setPrev(newest);

onceki.setNext(newest);

size++;

}

}

public void removeBefore(Node node){

if(node.getPrev()==header){

System.out.println("NODE IS THE FIRST NODE");

}else{

Node sil = node.getPrev();

Node onceki = sil.getPrev();

node.setPrev(onceki);

onceki.setNext(node);

sil.setPrev(null);

sil.setNext(null);

size--;

}

}

public Node getNode(int i){

if(i>=size())

return null;

Node newest = header;

for(int j = 0;j<=i;j++)

newest = newest.getNext();

return newest;

}

public E get(int i){

Node temp = header;

for(int a =0;a<=i;a++)

temp = temp.getNext();

return temp.getElement();

}

public void add(int i, E newData){

if(size==0){

Node newest = new Node<>(newData, null, null);

header.setNext(newest);

newest.setNext(trailer);

trailer.setPrev(newest);

newest.setPrev(header);

size++;

}else if(i==size){

Node newest = new Node<>(newData, null, null);

Node last = getNode(size-1);

last.setNext(newest);

newest.setNext(trailer);

trailer.setPrev(newest);

newest.setPrev(last);

size++;

}else if(i>=0 && i

Node newest = new Node<>(newData, null, null);

Node temp = header;

for(int a = 0;a<=i;a++)

temp=temp.getNext();

addBefore(temp,newData);

}

}

public E remove(int i){

if(i

Node newest = getNode(i+1);

Node deger = getNode(i);

removeBefore(newest);

return deger.getElement();

}else if(i== size-1){

Node newest = getNode(size-1);

Node deger = getNode(size-2);

deger.setNext(trailer);

trailer.setPrev(newest);

size--;

return newest.getElement();

}else

return null;

}

public int indexOf(E target){

Node temp = header.getNext();

for(int i = 0;i

if(temp.getElement().equals(target))

return i;

else

temp = temp.getNext();

}

return -1;

}

public void removeEveryOther(){

if(size != 0){

for(int i = 0;i

removeBefore(getNode(i+1));

}

}//----------- end of DoublyLinkedList class ---------- Main class:

public class Main{

public static void main(String[] args) {

DoublyLinkedList dll = new DoublyLinkedList<>();

dll.addFirst("A");

dll.addLast("B");

dll.addLast("C");

dll.addLast("D");

dll.addLast("E");

dll.addLast("F");

dll.addLast("G");

dll.addLast("H");

System.out.println(dll);

System.out.println("is index > size return (null) ="+dll.getNode(10));//null

DoublyLinkedList dll2 = new DoublyLinkedList<>();

System.out.println("if dll2 is empty return (null) ="+dll2.getNode(0));// if dll2 is empty return null

dll.addBefore(dll.getNode(2), "Z");

System.out.println("After addBefore:(A B Z C D E F G H) "+dll);//A B Z C D E F G H

dll.removeBefore(dll.getNode(2));//remove B

System.out.println("After removeBefore:(A Z C D E F G H) "+dll);//A Z C D E F G H

dll.removeBefore(dll.getNode(1));//remove A

System.out.println("After removeBefore:(Z C D E F G H) "+dll);//Z C D E F G H

dll.removeBefore(dll.getNode(dll.size()-1));//remove G

System.out.println("After removeBefore:(Z C D E F H) "+dll);//Z C D E F H

System.out.println("index (0) ="+dll.indexOf("Z"));//0

System.out.println("index (2) ="+dll.indexOf("D"));//2

System.out.println("index (5) ="+dll.indexOf("H"));//5

System.out.println("index (-1) ="+dll.indexOf("G"));//-1

System.out.println("Remove Z ="+dll.remove(0));//Z

; System.out.println("Remove H ="+dll.remove(dll.size()-1));//H

dll.add(0,"U");

System.out.println("After add U 0.th index:(U C D E F) "+dll);

dll.add(dll.size()-1,"T");

System.out.println("After add T last index: (U C D E T F) "+dll);

System.out.println("First element (U)= "+dll.get(0));//U

System.out.println("Last element (F)= "+dll.get(dll.size()-1));//F

dll.removeEveryOther();

System.out.println("After removeEveryOther: "+dll);

}

}