Adding of Polynomials -using Linear Linked List

Adding of polynomials is a very common operation in mathematics and other science subjects. Creating a program for adding of polynomials is quite tricky. If you create a program for this common problem of mathematics, selecting the right data type to store polynomials is the most important aspect of it. The data types possible to store the array are string or array.

Using string or array to declare and store polynomials poses same limitations as that using an array or a string for storing and manipulating data. The best option for storing polynomials is a linear linked list to store terms of the polynomials and perform its operations like addition, subtraction or multiplication.

Storing Polynomial in a Linked List

The linear linked list is defined as collection of nodes having a data part (information) and link part (pointer storing address of next node). In case of the node of linked list storing a polynomial it is defined with three parts-

• COEFF to store Coefficient part of a term of a polynomial
• EXP to store Exponent part of a term of a polynomial
• LINK to store address or location of the next term of a polynomial

The POLY pointer is used for storing the address of first term of the polynomial (Just like START pointer in linear linked list). A polynomial can be created by using the insertion operation of a linear linked list.

Adding of Polynomials stored as Linear Linked Lists  

The basic process of adding of polynomials involves using two pointers that keep track of corresponding terms of two polynomials. These corresponding terms are evaluated in this way-

1. If the corresponding terms have same EXP, the coefficients are added and new node is created with the added coefficients and EXP. If the two coefficients cancel each other, then no node is created for this EXP. Both pointers are updated to address on next node.
2. If EXP from first polynomial is larger than the corresponding term from the second polynomial, the term from the first polynomial is added as it is. The pointer of the first polynomial is updated and moved to the next term.
3.  If EXP from second polynomial is larger than the corresponding term from the first polynomial, the term from the second polynomial is added as it is. The pointer of the second polynomial is updated and moved to the next term.
4. If one of the polynomials is exhausted by adding the coefficients or adding directly (following 1, 2 or 3), the remaining terms of the other polynomial are moved as it to the final polynomial.

Algorithm -Addition of Polynomials

Algorithm AddPoly(Poly1, Poly2, Poly3)
1.  While poly1 and pol2 are not NULL, repeat step 2.
2.  if EXP(poly1)=EXP(Poly2) then
 If COEFF(poly1)+COEFF(poly2)<>0
            Create a node with  COEFF(poly1)+COEFF(poly2), EXP(poly1) and add it                     
            to the end of poly3
            Poly1=LINK(poly1)
            Poly2=LINK9poly2)
        Else
     If EXP(poly1)>EXP(Poly2) then
                  Create a node with COEFF(poly1, EXP(poly1) and add it to the end of poly3
                  Poly1=LINK(poly1)
        Else
                  Create a node with COEFF(poly2), EXP(poly2) and add it to the end of poly3
                  Poly2=LINK(poly2)
3. [Copy the remaining terms from the non empty polynomial into the poly3 polynomial]
   If poly1<>NULL then
             While poly1<>NULL
                     Create a node with COEFF(poly1, EXP(poly1) and add it to the end of poly3
                     Poly1=LINK(poly1)
   Else 
             While poly2<>NULL
                    Create a node with COEFF(poly2), EXP(poly2) and add it to the end of poly3
                    Poly2=LINK(poly2)

admin