We are now going to use our list classes to build another type of abstract data type called a polynomial. As you already know, a polynomial over a set F is a function of the following form:
| p(t) | = | a0 + a1t + a2t2 + ... + antn |
and the last power in the polynomial, n, is called its degree. The coefficients {a0,..., an} are taken from the set F. The collection of all such functions is called the polynomials over the set F.
We will implement polynomials as a class by modifying the existing class for lists. Roughly speaking, a polynomial will be implemented as a singly linked list with each cell containing an element from our chosen set and an unsigned integer to represent the power. So a cell with an element value of say 1.3 and an unsigned integer power of 4 would denote the term 1.4t4 in some polynomial over the set of real numbers represented as either floats or doubles. We can easily choose to restrict our attention to elements from the rationals (we would need to build a fraction class), Zp, where p is prime (the integers mod p), and so forth.
We can choose to put the largest degree of the polynomial at the head or at the tail of the list. We will choose to put it at the head.