Polynomials Using Linked List and Arrays

Polynomials and Sparse Matrix are two important applications of arrays and linked lists. A polynomial is composed of different terms where each of them holds a coefficient and an exponent. This tutorial chapter includes the representation of polynomials using linked lists and arrays.

What is Polynomial?

A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + …. + jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative integer, which is called the degree of polynomial.

An essential characteristic of the polynomial is that each term in the polynomial expression consists of two parts:

  • one is the coefficient
  • other is the exponent

Example:

10x2 + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value.

Points to keep in Mind while working with Polynomials:

  • The sign of each coefficient and exponent is stored within the coefficient and the exponent itself
  • Additional terms having equal exponent is possible one
  • The storage allocation for each term in the polynomial must be done in ascending and descending order of their exponent

working with polynomials

Representation of Polynomial

Polynomial can be represented in the various ways. These are:

  • By the use of arrays
  • By the use of Linked List

Representation of Polynomials Using Arrays

There may arise some situation where you need to evaluate many polynomial expressions and perform basic arithmetic operations like addition and subtraction with those numbers. For this, you will have to get a way to represent those polynomials. The simple way is to represent a polynomial with degree 'n' and store the coefficient of n+1 terms of the polynomial in the array. So every array element will consist of two values:

  • Coefficient and
  • Exponent

A polynomial can be represented using the C++ code:

#include <iostream>
#include <iomanip.h>
using namespace std;

struct poly {
    int coeff;
    int pow_val;
    poly* next;
};

class add {
    poly *poly1, *poly2, *poly3;

public:
    add() { poly1 = poly2 = poly3 = NULL; }
    void addpoly();
    void display();
};

void add::addpoly()
{
    int i, p;
    poly *newl = NULL, *end = NULL;
    cout << "Enter highest power for x\n"; cin >> p;
    //Read first poly
    cout << "\nFirst Polynomial\n"; for (i = p; i >= 0; i--) {
        newl = new poly;
        newl->pow_val = p;
        cout << "Enter Co-efficient for degree" << i << ":: "; cin >> newl->coeff;
        newl->next = NULL;
        if (poly1 == NULL)
            poly1 = newl;
        else
            end->next = newl;
        end = newl;
    }

    //Read Second poly
    cout << "\n\nSecond Polynomial\n"; end = NULL; for (i = p; i >= 0; i--) {
        newl = new poly;
        newl->pow_val = p;
        cout << "Enter Co-efficient for degree" << i << ":: "; cin >> newl->coeff;
        newl->next = NULL;
        if (poly2 == NULL)
            poly2 = newl;
        else
            end->next = newl;
        end = newl;
    }

    //Addition Logic
    poly *p1 = poly1, *p2 = poly2;
    end = NULL;
    while (p1 != NULL && p2 != NULL) {
        if (p1->pow_val == p2->pow_val) {
            newl = new poly;
            newl->pow_val = p--;
            newl->coeff = p1->coeff + p2->coeff;
            newl->next = NULL;
            if (poly3 == NULL)
                poly3 = newl;
            else
                end->next = newl;
            end = newl;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
}

void add::display()
{
    poly* t = poly3;
    cout << "\n\nAnswer after addition is : ";
    while (t != NULL) {
        cout.setf(ios::showpos);
        cout << t->coeff;
        cout.unsetf(ios::showpos);
        cout << "X" << t->pow_val;
        t = t->next;
    }
}
int main()
{
    add obj;
    obj.addpoly();
    obj.display();
}

Output:
polynomial using cplusplus

Representation of Polynomial Using Linked Lists

A polynomial can be thought of as an ordered list of non zero terms. Each non zero term is a two-tuple which holds two pieces of information:

  • The exponent part
  • The coefficient part

Program for the addition of Polynomials

#include <iostream>
using namespace std;

class polyll {
private:
    struct polynode {
        float coeff;
        int exp;
        polynode* link;
    } * p;

public:
    polyll();
    void poly_append(float c, int e);
    void display_poly();
    void poly_add(polyll& l1, polyll& l2);
    ~polyll();
};
polyll::polyll()
{
    p = NULL;
}
void polyll::poly_append(float c, int e)
{
    polynode* temp = p;
    if (temp == NULL) {
        temp = new polynode;
        p = temp;
    }
    else {
        while (temp->link != NULL)
            temp = temp->link;
        temp->link = new polynode;
        temp = temp->link;
    }
    temp->coeff = c;
    temp->exp = e;
    temp->link = NULL;
}
void polyll::display_poly()
{
    polynode* temp = p;
    int f = 0;

    cout << endl; while (temp != NULL) { if (f != 0) { if (temp->coeff > 0)
                cout << " + ";
            else
                cout << " "; } if (temp->exp != 0)
            cout << temp->coeff << "x^" << temp->exp;
        else
            cout << temp->coeff;
        temp = temp->link;
        f = 1;
    }
}
void polyll::poly_add(polyll& l1, polyll& l2)
{
    polynode* z;
    if (l1.p == NULL && l2.p == NULL)
        return;
    polynode *temp1, *temp2;
    temp1 = l1.p;
    temp2 = l2.p;
    while (temp1 != NULL && temp2 != NULL) {
        if (p == NULL) {
            p = new polynode;
            z = p;
        }
        else {
            z->link = new polynode;
            z = z->link;
        }
        if (temp1->exp < temp2->exp) {
            z->coeff = temp2->coeff;
            z->exp = temp2->exp;
            temp2 = temp2->link;
        }
        else {
            if (temp1->exp > temp2->exp) {
                z->coeff = temp1->coeff;
                z->exp = temp1->exp;
                temp1 = temp1->link;
            }
            else {
                if (temp1->exp == temp2->exp) {
                    z->coeff = temp1->coeff + temp2->coeff;
                    z->exp = temp1->exp;
                    temp1 = temp1->link;
                    temp2 = temp2->link;
                }
            }
        }
    }
    while (temp1 != NULL) {
        if (p == NULL) {
            p = new polynode;
            z = p;
        }
        else {
            z->link = new polynode;
            z = z->link;
        }
        z->coeff = temp1->coeff;
        z->exp = temp1->exp;
        temp1 = temp1->link;
    }
    while (temp2 != NULL) {
        if (p == NULL) {
            p = new polynode;
            z = p;
        }
        else {
            z->link = new polynode;
            z = z->link;
        }
        z->coeff = temp2->coeff;
        z->exp = temp2->exp;
        temp2 = temp2->link;
    }
    z->link = NULL;
}
polyll::~polyll()
{
    polynode* q;
    while (p != NULL) {
        q = p->link;
        delete p;
        p = q;
    }
}
int main()
{
    polyll p1;
    p1.poly_append(1.4, 5);
    p1.poly_append(1.5, 4);
    p1.poly_append(1.7, 2);
    p1.poly_append(1.8, 1);
    p1.poly_append(1.9, 0);
    cout << "\nFirst polynomial:";
    p1.display_poly();
    polyll p2;
    p2.poly_append(1.5, 6);
    p2.poly_append(2.5, 5);
    p2.poly_append(-3.5, 4);
    p2.poly_append(4.5, 3);
    p2.poly_append(6.5, 1);
    cout << "\nSecond polynomial:";
    p2.display_poly();
    polyll p3;
    p3.poly_add(p1, p2);
    cout << "\nResultant polynomial: ";
    p3.display_poly();
    getch();
}

Output:
addition of polynomials


Courses
Subscribe Updates via Email

Join 49,000+ W3schools lovers and get all the latest tutorials, programs, algorithms in your inbox.