Polynomial in Singly-Linked List: Representation and Operations Explained

We understand very well that a singly-linked list in C++ is a data structure that consists of nodes to host the data field and the next field. While the data field stores the input values, the next field contains the address to the next node.

Of the various applications that the singly-linked list is famous for, one of its key applications comes down to performing arithmetic operations. So, in this tutorial, we are going to explore how polynomial in singly linked list can be represented, implemented and operated upon.

Representation of Polynomial in Singly-Linked List

Before we get to the representation part, we must understand what comprises a polynomial in the mathematical background. Simply said, a polynomial is a mathematical expression that contains two or more algebraic expressions. Most often, polynomials represent functions and can be operated upon.

Now, in the computer science world, a polynomial in C++ is characterized by its two important fields: the data field and the next field. Here, the data field has two values, an exponent and a coefficient. The next field contains the address of the next node; thus, it establishes a link between the polynomials in singly linked list.

Now, let us take a look at the polynomial below for a better understanding of its representation in the singly-linked list.

P(x) = 3x2+ 5x+ 7

Exponents Coefficients
2 3
1 5
Null 7

This polynomial, when stored in the singly-linked list must follow the following syntax.

Polynomial in Singly Linked List

 

In this representation of P(x), polynomial in C++, we have got three fields: the exponent field that stores the exponent data, in our case, “2,1, null”, the coefficient field that stores the coefficient data, in our example, “3,5,7”, and the link field, that stores the address to the successive field.

Now that we’ve understood how to represent polynomials in singly linked list, let us move on to the operations that can be performed on polynomials in C++.

Operations On Polynomials In C++

Operation 1: Addition of Polynomials in Singly-Linked List

Let us now consider two polynomials, P(x) and Q(x).

P(x)=6x2+7x+4

Q(x)=8x+6

Mathematically, upon adding the two expressions, we would get the resultant polynomial, R(x)=6x2+15x+10.

But, when we represent these polynomials in singly linked list, it would look as below:

Polynomial Addition in Singly Linked List

 

 

Note that in the resultant polynomial in singly linked list, coefficients were added only when their corresponding exponents were same. While writing the code for the addition of polynomials in singly linked list, be sure to follow the algorithm.

  • Make a loop between all the values in the linked list.
  • Supposing a node’s exponent contains a unique value, copy the value of this node to the resultant node.
  • Else if two nodes have the same exponent values, add their coefficients and copy the result to the resultant node.
  • Print the results.

Operation 2: Multiplication of Polynomials in Singly-Linked List

To understand the multiplication of polynomials in C++, let us consider the following example.

P(x)=2x2+4x+5

Q(x)=3x+2

Upon multiplying, we must get R(x)=6x3+16x2+23x+10. While representing this polynomial in the singly linked list, it must observe the following syntax:

Polynomial Multiplication in Singly Linked List

 

Here’s a simple algorithm that you can keep in mind while writing the code:

  • Multiply the second polynomial, that is, Q(x), with all the terms of the first polynomial, P(x)
  • Store the obtained multiplied value in the resultant linked list
  • Add all the coefficients whose exponents have the same values in the resultant linked list
  • Print the results

C++ Program For Polynomial representation, implementation and operations(Add, Multiply, Eval) using SLL.

#include <iostream>
#include <math.h>
using namespace std;
struct poly{
    int coeff;
    int pow;
    poly *next;
};

class add2poly
{
   poly *poly1, *poly2, *poly3;
   public:
   add2poly(){poly1=poly2=poly3=NULL;}
   void mulpoly();
   void addpoly();
   void displaymulpoly();
   void displayaddpoly();
};

//Function For The Multiplication Of Two Polynomials
void add2poly :: mulpoly(){
      int i,p;
      poly *newl=NULL,*end=NULL;
      cout<<"Enter highest power for the polynomial x\n";
      cin>>p;
    
	//Read first polynomial
      cout<<"\nFirst Polynomial is\n";
      for(i=p;i>=0;i--)
      {
      newl=new poly;
      newl->pow=i;
      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=i;
      cout<<"Enter Co-efficient for degree"<<i<<"::  ";
      cin>>newl->coeff;
      newl->next=NULL;
      if(poly2==NULL)
         poly2=newl;
      else
         end->next=newl;
      end=newl;
      }

      //Multiplication Logic
      poly *p1=poly1,*p2=poly2;
      int flag;
      end=NULL;
      while(p1 !=NULL){
    p2=poly2;
    while(p2!=NULL){
        //if(p1->pow == p2->pow){
            newl=new poly;
            newl->pow=p1->pow + p2->pow;
            newl->coeff=p1->coeff * p2->coeff;
            newl->next=NULL;
            if(poly3==NULL)
               poly3=newl;
            else{
               flag=1;

               //search if element already exist in poly3//flag will be zero if item already exist//1 otherwise
                 poly *tmp=poly3;
                 while(tmp!=NULL){
                   if(tmp->pow==newl->pow){
                    tmp->coeff += newl->coeff;
                    flag=0;
                   }
                   tmp=tmp->next;
                }

                //if item not present simply append it.if(flag==1)
                  end->next=newl;
            }
            end=newl;
            p2=p2->next;
        }
        p1=p1->next;
      }
}

// Function To Display The Multiplication Result
void add2poly :: displaymulpoly(){
   poly *t=poly3;
   cout<<"\n\nAnswer after addition is : ";
   while(t!=NULL){
      cout<<t->coeff;
      cout<<"X^"<<t->pow<<"+";
      t=t->next;
   }
}

//Function To Add Two polynomials
void add2poly :: 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=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=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 == p2->pow){
            newl=new poly;
            newl->pow=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 add2poly :: displayaddpoly(){
   poly *t=poly3;
   cout<<"\n\nAnswer after addition is : ";
   while(t!=NULL){
      cout<<t->coeff;
      cout<<"x^"<<t->pow<<"+";
      t=t->next;
   }
}



int main()
{
	int ch;
    add2poly obj;
    do{
    cout<<"\nChoose The Operation You Want To Perform\n";
    cout<<"1:Polynomial Addition\n2: Polynomial Multiplication\n";
    cin>>ch;
    switch(ch)
    {
    	case 1:
    		obj.addpoly();
    		obj.displayaddpoly();
    		break;
    	case 2:
		    obj.mulpoly();
			obj.displaymulpoly();
	}
}while(ch!=3);
return 0;
}

 

Leave a Comment