Please solve the SLinkedList.deepClone. This is the provided code, solve the part that says add code here :

package assignments2018.a2template; import java.lang.Iterable; import java.util.Iterator;

/** * A basic implementation of some methods in a singly linked list class. * @author Michael Langer * @modified by Sayantan Datta * * (Most of this code was adapted from textbooks * e.g. by Frank Carrano, Mark Allen Weiss, * Michael Goodrich and Roberto Tomassia) * * I put some Javadoc in this code, e.g. @param, @return * But I do not expect you to do so in this course * (and I generally don't do it when I am writing my own Java code) * */

// The "extends" (rather than "implements") in the generic type definition is a Java detail that you don't need to think about.

public class SLinkedList> implements Iterable { // Fields private SNode head; private SNode tail; private int size;

// Constructor SLinkedList() { head = null; tail = null; size = 0; } /** * Inserts the element to the specified position in this list * where index is from 0 to size. If the position is size, then * add element to the end of the list. * @param i the position where the element should go * @param element the element to be added */ public void add(int i, E element) { if ((i size)) throw new IndexOutOfBoundsException(); if (i == 0) addFirst(element); else if (i == size) // Bot necessary to do this test. Only do it because addLast(element); // it is more efficient than what is below. else { SNode previousNode = getNode(i-1); // undefined if i==0 SNode newNode = new SNode(element); newNode.next = previousNode.next; previousNode.next = newNode; size++; } } /* * add a new element to front of list * @param element the new element */ public void addFirst(E element) { SNode newNode = new SNode(element); size++; if (head == null) { head = newNode; tail = head; } else { newNode.next = head; // Why not newNode.setNext(head) ? You could but you don't need to. head = newNode; // i.e. Don't need to use get and set methods inside the class. } }

/* * add a new element to the end of the list * @param element the new element */ public void addLast(E element) { SNode newNode = new SNode(element); size++; if (head == null) { head = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } } /* * remove all elements from the list */ public void clear() { head = null; tail = null; size = 0; }

/* * get the element at position i in the list (0,..., size -1 ) * @param i the index of the element * @return the element to get */ public E get(int i) { return getNode(i).element; } public boolean isEmpty() { return (size == 0); }

/* * Removes the element at index i in 0 to size-1, and return it. * @return the element at index i. */ public E remove(int i) { if ((i = size)) throw new IndexOutOfBoundsException(); else { // first deal with special case that size == 1, i == 0 if ((size == 1) && (i == 0)) // only one node in list { size--; SNode cur = head; head = null; tail = null; return cur.element; } // Now we can assume that size > 1. // We first deal with case that i == 0 SNode cur = head; size--; if (i == 0){ head = head.next; return cur.element; } else // we can assume that i > 0; { cur = getNode(i-1); SNode nodeToRemove = cur.next; cur.next = nodeToRemove.next; if (nodeToRemove.next == null) // removing the tail tail = cur; else nodeToRemove.next = null; // be safe return nodeToRemove.element; } } }

/** * Remove element at front of the list. * @return first element in list */ public E removeFirst(){ return remove(0); }

/** * Remove element at back of list. * @return last element */ public E removeLast(){ return remove(size-1); }

/** * Sets the ith element in the list. * @param i the index of element to be set * @param e the new element that replaces the old element */ public void set(int i, E e) { if ((i = size)) throw new IndexOutOfBoundsException(); else getNode(i).element = e; } /** * Show all elements in list. Alternatively I could have overriden the toString() method and then * just print the object, since printing an object automatially calls the toString() method. */ public void show() { SNode cur = head; while (cur != null) { System.out.print(" " + cur.element.toString()); cur = cur.next; } System.out.println(" (size is " + size + " )"); } public int size() { return size; } /* * TODO: Makes a deep copy of the this linked list. * Hint: Use E.deepCopy(). */ public SLinkedList deepClone() { SLinkedList newList= new SLinkedList(); /**** ADD CODE HERE ****/ return null; } @Override public String toString() { String ret = ""; if (head == null) return ""; // Hint: Use T.toString(). SNode current = head; while (current != null) { ret = ret + current.element.toString(); current = current.next; } return ret; } @Override public SLLIterator iterator() { SLLIterator iter = new SLLIterator(this); return iter; }

private class SLLIterator implements Iterator { // use a different generic type, since we're defining a new class here SNode cur; // constructor SLLIterator(SLinkedList list) { cur = list.head; } @Override public boolean hasNext() { return (cur != null); }

@Override public E next() { SNode tmp = cur; cur = cur.next; return tmp.element; } }

// The next two methods are private. The client has no access to the nodes of the linked list, // but rather the client can only access the elements that are stored in the list. /* * @param index of node to get * @return ith SNode of the linked list * */ private SNode getNode(int i) { if ((i = size)) throw new IndexOutOfBoundsException(); else { if (i == 0) // only one node in list return head; else { int index = 0; SNode cur = head; while (index { // I have to use a different generic type since I am defining a class here.

private T element; private SNode next;

SNode(T element){ this.element = element; next = null; } } }

Introduction In mathematics, a polynomial is an expression constructed from variables and constants, using the operations of addition, subtraction, multiplication, and constant non-negative integer exponents. For example, 5x - 4x + 7 is a polynomial. In general, a polynomial can be writtern where the coefficients ci are real numbers and cm 0, As explained below, in this assignment, the coefficients c and the variables x will be integers, represented with the Java Biglnteger class. Polynomials are heavily used in computer science and in mathematics and also in many other sciences. They are the basis of many models in physics and chemistry and other natural sciences, as well as in the social sciences such as economics. For example, they are commonly used to approximate functions. An example is a Taylor series expansion of a smooth function. Another example is that any continuous function on a closed interval of the real line can be approximated as closely as one wishes using a polynomial Instructions and Starter Code We will use a singly linked list data structure to represent polynomials and perform basic operations on them, such as addition and multiplication. Essentially, you will write a Polynomial class that builds upon the functionality of a linked list class. The starter code defines four classes which are as follows: Polynomial This class defines a polynomial in one variable with positive integer exponents. Most of your work goes into this function. You should use the methods provided with the linked list class to implement the methods of this class. You will notice that the template we provided use Java Biglnteger for storing the polynomial coefficient and variable. We intentionally chose Biglnteger over floating point (e.g. double) to avoid numerical issues associated with polynomial evaluation. SLinkedList This class implements a generic singly linked list. You do not have to implement the functionality of linked list as it is already provided with the starter code However, you must implement the cloning functionality (Task 1 see below) for performing a deep copy of the list. Term- This is a simple class that represents a single term of a polynomial. Example: 5x2. This class is also provided with the starter code. You do not have to modify this class, but you are required to understand what it does and how DeepCopy This is a small user defined interface for enforcing deep copy functionality You are not required to understand Java interfaces for completing this assignment as the underlying complexity is handled by the starter code. We will discuss Java interfaces in the lectures a few weeks from now Introduction In mathematics, a polynomial is an expression constructed from variables and constants, using the operations of addition, subtraction, multiplication, and constant non-negative integer exponents. For example, 5x - 4x + 7 is a polynomial. In general, a polynomial can be writtern where the coefficients ci are real numbers and cm 0, As explained below, in this assignment, the coefficients c and the variables x will be integers, represented with the Java Biglnteger class. Polynomials are heavily used in computer science and in mathematics and also in many other sciences. They are the basis of many models in physics and chemistry and other natural sciences, as well as in the social sciences such as economics. For example, they are commonly used to approximate functions. An example is a Taylor series expansion of a smooth function. Another example is that any continuous function on a closed interval of the real line can be approximated as closely as one wishes using a polynomial Instructions and Starter Code We will use a singly linked list data structure to represent polynomials and perform basic operations on them, such as addition and multiplication. Essentially, you will write a Polynomial class that builds upon the functionality of a linked list class. The starter code defines four classes which are as follows: Polynomial This class defines a polynomial in one variable with positive integer exponents. Most of your work goes into this function. You should use the methods provided with the linked list class to implement the methods of this class. You will notice that the template we provided use Java Biglnteger for storing the polynomial coefficient and variable. We intentionally chose Biglnteger over floating point (e.g. double) to avoid numerical issues associated with polynomial evaluation. SLinkedList This class implements a generic singly linked list. You do not have to implement the functionality of linked list as it is already provided with the starter code However, you must implement the cloning functionality (Task 1 see below) for performing a deep copy of the list. Term- This is a simple class that represents a single term of a polynomial. Example: 5x2. This class is also provided with the starter code. You do not have to modify this class, but you are required to understand what it does and how DeepCopy This is a small user defined interface for enforcing deep copy functionality You are not required to understand Java interfaces for completing this assignment as the underlying complexity is handled by the starter code. We will discuss Java interfaces in the lectures a few weeks from now