# 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. 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++

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: 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: 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;
};

{
poly *poly1, *poly2, *poly3;
public:
void mulpoly();
void displaymulpoly();
};

//Function For The Multiplication Of Two Polynomials
int i,p;
poly *newl=NULL,*end=NULL;
cout<<"Enter highest power for the polynomial x\n";
cin>>p;

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;
}

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
poly *t=poly3;
while(t!=NULL){
cout<<t->coeff;
cout<<"X^"<<t->pow<<"+";
t=t->next;
}
}

int i,p;
poly *newl=NULL,*end=NULL;
cout<<"Enter highest power for x\n";
cin>>p;
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;
}

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;
}

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;
}
}

poly *t=poly3;
while(t!=NULL){
cout<<t->coeff;
cout<<"x^"<<t->pow<<"+";
t=t->next;
}
}

int main()
{
int ch;
do{
cout<<"\nChoose The Operation You Want To Perform\n";
cin>>ch;
switch(ch)
{
case 1: