Polynomial representation using Linked List

The linked list can be used to represent a polynomial of any degree. Simply the information field is changed according to the number of variables used in the polynomial. If a single variable is used in the polynomial the information field of the node contains two parts: one for coefficient of variable and the other for degree of variable. Let us consider an example to represent a polynomial using linked list as follows:

Polynomial:      3x3-4x2+2x-9

Linked List:

In the above linked list, the external pointer ‘ROOT’ point to the first node of the linked list. The first node of the linked list contains the information about the variable with the highest degree. The first node points to the next node with next lowest degree of the variable.

Representation of a polynomial using the linked list is beneficial when the operations on the polynomial like addition and subtractions are performed. The resulting polynomial can also be traversed very easily to display the polynomial.

The above two linked lists represent the polynomials,3x3-4x2+2x-9 and 5x3-2x2+6x+3 respectively. If both the polynomials are added then the resulting linked will be:

The linked list pointer ROOT gives the representation for polynomial, 8x3-6x2+8x-6.

C program to read and display a polynomial using Linked List:

#inculde<stdio.h>
#inculde<stdlib.h>
#inculde<conio.h>
struct node
{
int coeft;
int degree;
struct node *link;
};
typedef struct node poly;
main()
{
poly *root,*temp,*new;
int hdegree, coeft;
root=NULL;
clrscr();
printf(“Enter the highest degree of polynomial:”)
scanf(“%d”,&hdegree);
while(hdegree>=0)
{
printf(“Enter coefficient of variable with degree %d”,hdegree);
scanf(“%d”,&coeft);
if(coeft!=0)
{
new=(poly*)malloc(sizeof(poly));
if(new= =NULL)
{
printf(“Memory allocation error…”); exit(0);
}
new->coeft=coeft;
new->degree=hdegree;
new->link=NULL;
if(root= =NULL)
{
root=new;
temp=root;
}
else
{
temp->link=new;
temp=new;
}
}
hdegree--;
}
clrscr();
printf(“\n The Polynomial is:\n\n”);
temp=root;
while(temp!=NULL)
{
if(temp->coeft>0)
 printf(“+%dx%d”,temp->coeft,temp->degree);
else
  printf(“%dx%d”,temp->coeft,temp->degree);
temp=temp->link;
}
 getch();
}