Design an interfacePolynomialthat defines the following operations.

This is your polynomialabstract data type. Specifically this interface should have the following method signatures:

• A methodaddTermthat takes a coefficient and a power (both integer numbers) and adds the resulting term to the polynomial. (This will enable you to build a polynomial term-by-term.) It should throw anIllegalArgumentExceptionif a negative power is passed to it.
• A methodremoveTermthat takes a power and removes any and all terms in the polynomial with that power.
• A methodgetDegreethat returns the degree of this polynomial.
• A methodgetCoefficientthat takes a power and returns the coefficient for the term with that power.
• A methodevaluatethat takes a double-precision decimal number and returns a double-precision result.
• A methodaddthat takes anotherPolynomialobject and returns the polynomial obtained by adding the two polynomials. Any implementation should ensure that this method does not mutate either polynomial. The implementation may assume that the givenPolynomialis of the same concrete class as this object; if it is a different class, the method may throw anIllegalArgumentException.

Now implement this interface in a classPolynomialImpl. Beyond implementing thePolynomialinterface, this implementation should have the following features/obey these constraints:

• This class should store the polynomial using a linked list with nodes. This representation must be implemented by you (i.e. you are not allowed to use existing list or other collection classes in Java).
• This class should store only terms with non-zero coefficients.
• This class should store the polynomial terms in decreasing order of their powers.
• This class should have a constructor with no parameters that creates a polynomial with no terms, i.e. the polynomial 0 (how to represent this?).
• This class should have another constructor that takes a polynomial as a string, parses it and creates the polynomial accordingly. The string contains the polynomial, with each term separated by a space. The following examples should work with your constructor:
  • "4x^3 +3x^1 -5"
  • "-3x^4 -2x^5 -5 +11x^1"

Hint:Break the string into substrings and process. You may find theScannerandStringclasses helpful. Furthermore one can convert"23"into the integer23by usingInteger.parseInt("23").

• While you are free to write helper methods, you are not allowed to write other public methods as part of PolynomialImpl other than those in the interface and the above two constructors.
• This class should include a toString method that returns a string that contains the polynomial. An polynomial of nothing should return "0" (keep in mind this does not necessarily mean that the empty node should return "0"!). The following examples should help you infer the required format:
  • 5x² + 4x - 2 creates the string "5x^2 +4x^1 -2"
  • -50x³ + x² + 3 creates the string "-50x^3 +1x^2 +3"
  • 4x + 2x⁵ - 3x² -10 creates the string "2x^5 -3x^2 +4x^1 -10"