C++ program to add two polynomial using linked list

Hello everyone!
In this tutorial, we will learn how to write a C++ program to add two polynomial using a linked list with corresponding code.

Linked list:
Linked List is a linear data structure that consists of a group of nodes that are linked with pointers. Each node consists of data and the address of the next node.

Polynomial:
Polynomials are expressions that consist of both variables and coefficients. We can perform operations such as addition, subtraction, multiplication, and non-negative integer exponents of variables but not division by variable.

A polynomial is stored in a linked list as:

Adding two polynomial using Linked List in C++

Let us take two polynomials 4x^5 + 2x^3 + 5x^0, 2x^3 + 5x^2 + 5x^1 represented by p1, p2  respectively as input.
1. While p1 and p2 are not null, then repeat steps 2 and 3.
2. If the power of the node is greater, then store it in the result and move the head towards the next node.
3. If the power of both nodes is equal then add their coefficients and store it in the result.
4. Finally, Print the resultant node.

Now, Let us write a c++ program to add two polynomial according to above steps.

#include<bits/stdc++.h>
using namespace std;
struct Node
{
   int coeff;
   int power;
   struct Node *next;
};
void create_node(int x, int y, struct Node **temp)
{
   struct Node *a, *r;
   a = *temp;
   if(a == NULL)
   {
      r =(struct Node*)malloc(sizeof(struct Node));
      r->coeff = x;
      r->power = y;
      *temp = r;
      r->next = (struct Node*)malloc(sizeof(struct Node));
      r = r->next;
      r->next = NULL;
   } 
   else
   {
      r->coeff = x;
      r->power = y;
      r->next = (struct Node*)malloc(sizeof(struct Node));
      r = r->next;
      r->next = NULL;
   }
}
//adding two polynomials

void add(struct Node *p1, struct Node *p2, struct Node *result)
{
   while(p1->next && p2->next) 
   {
      if(p1->power > p2->power) 
      {
         result->power = p1->power;
         result->coeff = p1->coeff;
         p1 = p1->next;
      }
      else if(p1->power < p2->power)
      {
         result->power = p2->power;
         result->coeff = p2->coeff;
         p2 = p2->next;
      } 
      else 
      {
         result->power = p1->power;
         result->coeff = p1->coeff+p2->coeff;
         p1 = p1->next;
         p2 = p2->next;
      }
      result->next = (struct Node *)malloc(sizeof(struct Node));
      result = result->next;
      result->next = NULL;
   }
   while(p1->next || p2->next)
   {
      if(p1->next)
      {
         result->power = p1->power;
         result->coeff = p1->coeff;
         p1 = p1->next;
      }
      if(p2->next)
      {
         result->power = p2->power;
         result->coeff = p2->coeff;
         p2 = p2->next;
      }
      result->next = (struct Node *)malloc(sizeof(struct Node));
      result = result->next;
      result->next = NULL;
   }
}
//display function to print resultant polynomial
void display(struct Node *node)
{
   while(node->next != NULL)
   {
      printf("%dx^%d", node->coeff, node->power);
      node = node->next;
      if(node->next != NULL)
         printf(" + ");
   }
}
int main()
{
   struct Node *p1 = NULL, *p2 = NULL, *result = NULL;
   //creating polynomial1 p1 and polynomial2 p2
   create_node(4,5,&p1);
   create_node(2,3,&p1);
   create_node(5,0,&p1);
   create_node(2,3,&p2);
   create_node(5,2,&p2);
   create_node(5,1,&p2);
   printf("polynomial 1: ");
   display(p1);
   printf("\npolynomial 2: ");
   display(p2);
   result = (struct Node *)malloc(sizeof(struct Node));
   add(p1, p2, result);
   printf("\nresultant polynomial: ");
   display(result);
   return 0;
}

Output:

polynomial 1: 4x^5 + 2x^3 + 5x^0
polynomial 2: 2x^3 + 5x^2 + 5x^1
resultant polynomial: 4x^5 + 4x^3 + 5x^2 + 5x^1 + 5x^0

Thus, I hope this tutorial will help you.

You may also visit:

Thank you.

Leave a Reply

Your email address will not be published. Required fields are marked *