CS46B Polynomials with java util LinkedList class Revise your polynomial class so that the coefficients are stored in the LinkedList class in java util The LinkedList class is one of the Java Collections Classes As described below you will also want to use java util s Iterator and ListIterator classes Documentation for these classes is in the files LinkedList html Iterator html and ListIterator html You should find these in a directory such as jdk1 3 docs api java util or jdk1 4 docs api java util you may need to search a bit for these or on the web at java sun com docs You may also want to look at jdk1 3 docs guide collections overview html for an overview of the Java collections classes Except for EasyReader do not use any code from Main such as DoubleNode Also do not use arrays or any collection classes other than LinkedList in your program Make use of ListIterator if you need to change values in the list and Iterator if you only need to access values in the list to move through your linked list Do this so that that inputting outputting evaluating and adding polynomials of degree n can be done in O n operations Do not use the LinkedList s get int index or set int index Object element Use of get or set can increase the operation count to O n 2 As an example I will give you the code for multiplying two polynomials Multiplies two polynomials param f one of the polynomials param g the second polynomial return the product of the two polynomials public static Polynomial multiply Polynomial f Polynomial g Note that the instance variables declared earlier of this class include private int degree the degree of the polynomial private LinkedList coef a linked list from java util storing the polynomial coefficients starting with the 0th power and storing 0 for the coefficient of any missing powers This implementation of polynomial multiplication uses iterators in order to illustrate their use and to write a code that is O n 2 when multiplying two nth degree polynomials Note that use of methods that require traversals such as LinkedList s get int index or set int index Object element can make the operation count O n 3 Polynomial h new Polynomial f degree g degree the constructor sets the degree of h and assigns zero to each coefficient of h int i 0 i keeps track of the coefficient of f Iterator fIterator f coef iterator at the 0th coefficient of f while fIterator hasNext loop over the coefficients of f ListIterator hIterator h coef listIterator at 0th coefficient of h for int k 0 k i k move to the ith coef of h hIterator next Note ListIterator hIterator h coef listIterator i would do the same thing here double a Double fIterator next doubleValue the ith coef of f i i increases due to the fIterator next call Iterator gIterator g coef iterator at the 0th coefficient of g int j 0 j keeps track of the coefficient of g while gIterator hasNext loop over the coefficients of g double b Double gIterator next doubleValue coefficient j of g j j increases due to the gIterator next call double c Double hIterator next doubleValue coefficient i j of h c c a b calculate new coefficien of h hIterator set new Double c reassign coefficient i j of h return h Do the same runs as in program 2 so you will need to include equals and clone You should be able to use exactly the same code for main as for program 2 different implementations of a class should not change how the class is used except I want you to add one line at the end of your main program System out println nUsing toString f is n f Your Polynomial class should include a reasonable toString method Note that the LinkedList class comes with its own equals toString and clone methods that will make your equals clone and toString easier to write You should use these built in methods in writing the methods for your Polynomial class Turn in printouts of the four runs and listings of your source code Also turn in a disk with Polynomial java now using java util s LinkedLists and TestPolynomial java as well as EasyReader or FormatWriter if you use them Again place all these in the same directory so delete the package statements from EasyReader and FormatWriter Test your code on Sun s Java jdk 1 3 or 1 4 and TextPad before turning it in