Which linked list is used for multiple variable polynomial equation efficient?

Multiplication of two polynomials using Linked list

Given two polynomials in the form of linked list. The task is to find the multiplication of both polynomials.

Table of Contents Show

• Multiplication of two polynomials using Linked list
• What is Polynomial?
• How do you add two polynomials to a linked list?
• How many fields will be in the node for performing polynomial addition?
• How do you multiply two polynomials using linked list?
• How do you add two polynomials using linked list algorithm?
• What is the time complexity of multiplying 2 polynomials represented in linked list?
• Which linked list is used for multiple variable polynomial?
• When multiplication of two polynomials is possible?
• How do you multiply two polynomials using a linked list?
• Which linked list is used for multiply variable polynomial equation efficiently?
• How do you represent a polynomial in a linked list?
• How do you add two polynomials to a linked list?

Examples:

Input: Poly1: 3x^2 + 5x^1 + 6, Poly2: 6x^1 + 8 Output: 18x^3 + 54x^2 + 76x^1 + 48 On multiplying each element of 1st polynomial with elements of 2nd polynomial, we get 18x^3 + 24x^2 + 30x^2 + 40x^1 + 36x^1 + 48 On adding values with same power of x, 18x^3 + 54x^2 + 76x^1 + 48 Input: Poly1: 3x^3 + 6x^1 - 9, Poly2: 9x^3 - 8x^2 + 7x^1 + 2 Output: 27x^6 - 24x^5 + 75x^4 - 123x^3 + 114x^2 - 51x^1 - 18

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach:

1. In this approach we will multiply the 2nd polynomial with each term of 1st polynomial.
2. Store the multiplied value in a new linked list.
3. Then we will add the coefficients of elements having the same power in resultant polynomial.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Node structure containing powerer // and coefficient of variable struct Node { int coeff, power; Node* next; }; // Function add a new node at the end of list Node* addnode(Node* start, int coeff, int power) { // Create a new node Node* newnode = new Node; newnode->coeff = coeff; newnode->power = power; newnode->next = NULL; // If linked list is empty if (start == NULL) return newnode; // If linked list has nodes Node* ptr = start; while (ptr->next != NULL) ptr = ptr->next; ptr->next = newnode; return start; } // Function To Display The Linked list void printList(struct Node* ptr) { while (ptr->next != NULL) { cout << ptr->coeff << "x^" << ptr->power ; if( ptr->next!=NULL && ptr->next->coeff >=0) cout << "+"; ptr = ptr->next; } cout << ptr->coeff << "\n"; } // Function to add coefficients of // two elements having same powerer void removeDuplicates(Node* start) { Node *ptr1, *ptr2, *dup; ptr1 = start; /* Pick elements one by one */ while (ptr1 != NULL && ptr1->next != NULL) { ptr2 = ptr1; // Compare the picked element // with rest of the elements while (ptr2->next != NULL) { // If powerer of two elements are same if (ptr1->power == ptr2->next->power) { // Add their coefficients and put it in 1st element ptr1->coeff = ptr1->coeff + ptr2->next->coeff; dup = ptr2->next; ptr2->next = ptr2->next->next; // remove the 2nd element delete (dup); } else ptr2 = ptr2->next; } ptr1 = ptr1->next; } } // Function two Multiply two polynomial Numbers Node* multiply(Node* poly1, Node* poly2, Node* poly3) { // Create two pointer and store the // address of 1st and 2nd polynomials Node *ptr1, *ptr2; ptr1 = poly1; ptr2 = poly2; while (ptr1 != NULL) { while (ptr2 != NULL) { int coeff, power; // Multiply the coefficient of both // polynomials and store it in coeff coeff = ptr1->coeff * ptr2->coeff; // Add the powerer of both polynomials // and store it in power power = ptr1->power + ptr2->power; // Invoke addnode function to create // a newnode by passing three parameters poly3 = addnode(poly3, coeff, power); // move the pointer of 2nd polynomial // two get its next term ptr2 = ptr2->next; } // Move the 2nd pointer to the // starting point of 2nd polynomial ptr2 = poly2; // move the pointer of 1st polynomial ptr1 = ptr1->next; } // this function will be invoke to add // the coefficient of the elements // having same powerer from the resultant linked list removeDuplicates(poly3); return poly3; } // Driver Code int main() { Node *poly1 = NULL, *poly2 = NULL, *poly3 = NULL; // Creation of 1st Polynomial: 3x^2 + 5x^1 + 6 poly1 = addnode(poly1, 3, 3); poly1 = addnode(poly1, 6, 1); poly1 = addnode(poly1, -9, 0); // Creation of 2nd polynomial: 6x^1 + 8 poly2 = addnode(poly2, 9, 3); poly2 = addnode(poly2, -8, 2); poly2 = addnode(poly2, 7, 1); poly2 = addnode(poly2, 2, 0); // Displaying 1st polynomial cout << "1st Polynomial:- "; printList(poly1); // Displaying 2nd polynomial cout << "2nd Polynomial:- "; printList(poly2); // calling multiply function poly3 = multiply(poly1, poly2, poly3); // Displaying Resultant Polynomial cout << "Resultant Polynomial:- "; printList(poly3); return 0; }

Java

// Java implementation of above approach import java.util.*; class GFG { // Node structure containing powerer // and coefficient of variable static class Node { int coeff, power; Node next; }; // Function add a new node at the end of list static Node addnode(Node start, int coeff, int power) { // Create a new node Node newnode = new Node(); newnode.coeff = coeff; newnode.power = power; newnode.next = null; // If linked list is empty if (start == null) return newnode; // If linked list has nodes Node ptr = start; while (ptr.next != null) ptr = ptr.next; ptr.next = newnode; return start; } // Function To Display The Linked list static void printList( Node ptr) { while (ptr.next != null) { System.out.print( ptr.coeff + "x^" + ptr.power + " + "); ptr = ptr.next; } System.out.print( ptr.coeff +"\n"); } // Function to add coefficients of // two elements having same powerer static void removeDuplicates(Node start) { Node ptr1, ptr2, dup; ptr1 = start; /* Pick elements one by one */ while (ptr1 != null && ptr1.next != null) { ptr2 = ptr1; // Compare the picked element // with rest of the elements while (ptr2.next != null) { // If powerer of two elements are same if (ptr1.power == ptr2.next.power) { // Add their coefficients and put it in 1st element ptr1.coeff = ptr1.coeff + ptr2.next.coeff; dup = ptr2.next; ptr2.next = ptr2.next.next; } else ptr2 = ptr2.next; } ptr1 = ptr1.next; } } // Function two Multiply two polynomial Numbers static Node multiply(Node poly1, Node poly2, Node poly3) { // Create two pointer and store the // address of 1st and 2nd polynomials Node ptr1, ptr2; ptr1 = poly1; ptr2 = poly2; while (ptr1 != null) { while (ptr2 != null) { int coeff, power; // Multiply the coefficient of both // polynomials and store it in coeff coeff = ptr1.coeff * ptr2.coeff; // Add the powerer of both polynomials // and store it in power power = ptr1.power + ptr2.power; // Invoke addnode function to create // a newnode by passing three parameters poly3 = addnode(poly3, coeff, power); // move the pointer of 2nd polynomial // two get its next term ptr2 = ptr2.next; } // Move the 2nd pointer to the // starting point of 2nd polynomial ptr2 = poly2; // move the pointer of 1st polynomial ptr1 = ptr1.next; } // this function will be invoke to add // the coefficient of the elements // having same powerer from the resultant linked list removeDuplicates(poly3); return poly3; } // Driver Code public static void main(String args[]) { Node poly1 = null, poly2 = null, poly3 = null; // Creation of 1st Polynomial: 3x^2 + 5x^1 + 6 poly1 = addnode(poly1, 3, 2); poly1 = addnode(poly1, 5, 1); poly1 = addnode(poly1, 6, 0); // Creation of 2nd polynomial: 6x^1 + 8 poly2 = addnode(poly2, 6, 1); poly2 = addnode(poly2, 8, 0); // Displaying 1st polynomial System.out.print("1st Polynomial:- "); printList(poly1); // Displaying 2nd polynomial System.out.print("2nd Polynomial:- "); printList(poly2); // calling multiply function poly3 = multiply(poly1, poly2, poly3); // Displaying Resultant Polynomial System.out.print( "Resultant Polynomial:- "); printList(poly3); } } // This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the above approach # Node structure containing powerer # and coefficient of variable class Node: def __init__(self): self.coeff = None self.power = None self.next = None # Function add a new node at the end of list def addnode(start, coeff, power): # Create a new node newnode = Node(); newnode.coeff = coeff; newnode.power = power; newnode.next = None; # If linked list is empty if (start == None): return newnode; # If linked list has nodes ptr = start; while (ptr.next != None): ptr = ptr.next; ptr.next = newnode; return start; # Function To Display The Linked list def printList(ptr): while (ptr.next != None): print(str(ptr.coeff) + 'x^' + str(ptr.power), end = '') if( ptr.next != None and ptr.next.coeff >= 0): print('+', end = '') ptr = ptr.next print(ptr.coeff) # Function to add coefficients of # two elements having same powerer def removeDuplicates(start): ptr2 = None dup = None ptr1 = start; # Pick elements one by one while (ptr1 != None and ptr1.next != None): ptr2 = ptr1; # Compare the picked element # with rest of the elements while (ptr2.next != None): # If powerer of two elements are same if (ptr1.power == ptr2.next.power): # Add their coefficients and put it in 1st element ptr1.coeff = ptr1.coeff + ptr2.next.coeff; dup = ptr2.next; ptr2.next = ptr2.next.next; else: ptr2 = ptr2.next; ptr1 = ptr1.next; # Function two Multiply two polynomial Numbers def multiply(poly1, Npoly2, poly3): # Create two pointer and store the # address of 1st and 2nd polynomials ptr1 = poly1; ptr2 = poly2; while (ptr1 != None): while (ptr2 != None): # Multiply the coefficient of both # polynomials and store it in coeff coeff = ptr1.coeff * ptr2.coeff; # Add the powerer of both polynomials # and store it in power power = ptr1.power + ptr2.power; # Invoke addnode function to create # a newnode by passing three parameters poly3 = addnode(poly3, coeff, power); # move the pointer of 2nd polynomial # two get its next term ptr2 = ptr2.next; # Move the 2nd pointer to the # starting point of 2nd polynomial ptr2 = poly2; # move the pointer of 1st polynomial ptr1 = ptr1.next; # this function will be invoke to add # the coefficient of the elements # having same powerer from the resultant linked list removeDuplicates(poly3); return poly3; # Driver Code if __name__=='__main__': poly1 = None poly2 = None poly3 = None; # Creation of 1st Polynomial: 3x^2 + 5x^1 + 6 poly1 = addnode(poly1, 3, 3); poly1 = addnode(poly1, 6, 1); poly1 = addnode(poly1, -9, 0); # Creation of 2nd polynomial: 6x^1 + 8 poly2 = addnode(poly2, 9, 3); poly2 = addnode(poly2, -8, 2); poly2 = addnode(poly2, 7, 1); poly2 = addnode(poly2, 2, 0); # Displaying 1st polynomial print("1st Polynomial:- ", end = ''); printList(poly1); # Displaying 2nd polynomial print("2nd Polynomial:- ", end = ''); printList(poly2); # calling multiply function poly3 = multiply(poly1, poly2, poly3); # Displaying Resultant Polynomial print("Resultant Polynomial:- ", end = ''); printList(poly3); # This code is contributed by rutvik_56

C#

// C# implementation of above approach using System; class GFG { // Node structure containing powerer // and coefficient of variable public class Node { public int coeff, power; public Node next; }; // Function add a new node at the end of list static Node addnode(Node start, int coeff, int power) { // Create a new node Node newnode = new Node(); newnode.coeff = coeff; newnode.power = power; newnode.next = null; // If linked list is empty if (start == null) return newnode; // If linked list has nodes Node ptr = start; while (ptr.next != null) ptr = ptr.next; ptr.next = newnode; return start; } // Function To Display The Linked list static void printList( Node ptr) { while (ptr.next != null) { Console.Write( ptr.coeff + "x^" + ptr.power + " + "); ptr = ptr.next; } Console.Write( ptr.coeff +"\n"); } // Function to add coefficients of // two elements having same powerer static void removeDuplicates(Node start) { Node ptr1, ptr2, dup; ptr1 = start; /* Pick elements one by one */ while (ptr1 != null && ptr1.next != null) { ptr2 = ptr1; // Compare the picked element // with rest of the elements while (ptr2.next != null) { // If powerer of two elements are same if (ptr1.power == ptr2.next.power) { // Add their coefficients and put it in 1st element ptr1.coeff = ptr1.coeff + ptr2.next.coeff; dup = ptr2.next; ptr2.next = ptr2.next.next; } else ptr2 = ptr2.next; } ptr1 = ptr1.next; } } // Function two Multiply two polynomial Numbers static Node multiply(Node poly1, Node poly2, Node poly3) { // Create two pointer and store the // address of 1st and 2nd polynomials Node ptr1, ptr2; ptr1 = poly1; ptr2 = poly2; while (ptr1 != null) { while (ptr2 != null) { int coeff, power; // Multiply the coefficient of both // polynomials and store it in coeff coeff = ptr1.coeff * ptr2.coeff; // Add the powerer of both polynomials // and store it in power power = ptr1.power + ptr2.power; // Invoke addnode function to create // a newnode by passing three parameters poly3 = addnode(poly3, coeff, power); // move the pointer of 2nd polynomial // two get its next term ptr2 = ptr2.next; } // Move the 2nd pointer to the // starting point of 2nd polynomial ptr2 = poly2; // move the pointer of 1st polynomial ptr1 = ptr1.next; } // this function will be invoke to add // the coefficient of the elements // having same powerer from the resultant linked list removeDuplicates(poly3); return poly3; } // Driver Code public static void Main(String []args) { Node poly1 = null, poly2 = null, poly3 = null; // Creation of 1st Polynomial: 3x^2 + 5x^1 + 6 poly1 = addnode(poly1, 3, 2); poly1 = addnode(poly1, 5, 1); poly1 = addnode(poly1, 6, 0); // Creation of 2nd polynomial: 6x^1 + 8 poly2 = addnode(poly2, 6, 1); poly2 = addnode(poly2, 8, 0); // Displaying 1st polynomial Console.Write("1st Polynomial:- "); printList(poly1); // Displaying 2nd polynomial Console.Write("2nd Polynomial:- "); printList(poly2); // calling multiply function poly3 = multiply(poly1, poly2, poly3); // Displaying Resultant Polynomial Console.Write( "Resultant Polynomial:- "); printList(poly3); } } // This code has been contributed by 29AjayKumar

Javascript

<script> // Javascript implementation of above approach // Link list node class Node { constructor() { this.coeff = 0; this.power = 0; this.next = null; } } // Function add a new node at the end of list function addnode(start, coeff, power) { // Create a new node var newnode = new Node(); newnode.coeff = coeff; newnode.power = power; newnode.next = null; // If linked list is empty if (start == null) return newnode; // If linked list has nodes var ptr = start; while (ptr.next != null) ptr = ptr.next; ptr.next = newnode; return start; } // Function To Display The Linked list function printList( ptr) { while (ptr.next != null) { document.write( ptr.coeff + "x^" + ptr.power + " + "); ptr = ptr.next; } document.write( ptr.coeff +"</br>"); } // Function to add coefficients of // two elements having same powerer function removeDuplicates( start) { var ptr1, ptr2, dup; ptr1 = start; /* Pick elements one by one */ while (ptr1 != null && ptr1.next != null) { ptr2 = ptr1; // Compare the picked element // with rest of the elements while (ptr2.next != null) { // If powerer of two elements are same if (ptr1.power == ptr2.next.power) { // Add their coefficients and put it in 1st element ptr1.coeff = ptr1.coeff + ptr2.next.coeff; dup = ptr2.next; ptr2.next = ptr2.next.next; } else ptr2 = ptr2.next; } ptr1 = ptr1.next; } } // Function two Multiply two polynomial Numbers function multiply( poly1, poly2, poly3) { // Create two pointer and store the // address of 1st and 2nd polynomials var ptr1, ptr2; ptr1 = poly1; ptr2 = poly2; while (ptr1 != null) { while (ptr2 != null) { let coeff, power; // Multiply the coefficient of both // polynomials and store it in coeff coeff = ptr1.coeff * ptr2.coeff; // Add the powerer of both polynomials // and store it in power power = ptr1.power + ptr2.power; // Invoke addnode function to create // a newnode by passing three parameters poly3 = addnode(poly3, coeff, power); // move the pointer of 2nd polynomial // two get its next term ptr2 = ptr2.next; } // Move the 2nd pointer to the // starting point of 2nd polynomial ptr2 = poly2; // move the pointer of 1st polynomial ptr1 = ptr1.next; } // this function will be invoke to add // the coefficient of the elements // having same powerer from the resultant linked list removeDuplicates(poly3); return poly3; } // Driver Code var poly1 = null, poly2 = null, poly3 = null; // Creation of 1st Polynomial: 3x^2 + 5x^1 + 6 poly1 = addnode(poly1, 3, 2); poly1 = addnode(poly1, 5, 1); poly1 = addnode(poly1, 6, 0); // Creation of 2nd polynomial: 6x^1 + 8 poly2 = addnode(poly2, 6, 1); poly2 = addnode(poly2, 8, 0); // Displaying 1st polynomial document.write("1st Polynomial:- "); printList(poly1); // Displaying 2nd polynomial document.write("2nd Polynomial:- "); printList(poly2); // calling multiply function poly3 = multiply(poly1, poly2, poly3); // Displaying Resultant Polynomial document.write( "Resultant Polynomial:- "); printList(poly3); // This code is contributed by jana_sayantan. </script>

Output 1st Polynomial:- 3x^3+6x^1-9 2nd Polynomial:- 9x^3-8x^2+7x^1+2 Resultant Polynomial:- 27x^6-24x^5+75x^4-123x^3+114x^2-51x^1-18

Article Tags :

Linked List

Technical Scripter

Linked-List-Polynomial

maths-polynomial

Technical Scripter 2018

Practice Tags :

Linked List

What is Polynomial?

A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + …. + jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative integer, which is called the degree of polynomial.

An essential characteristic of the polynomial is that each term in the polynomial expression consists of two parts:

• one is the coefficient
• other is the exponent

Example:

10x2 + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value.

Points to keep in Mind while working with Polynomials:

• The sign of each coefficient and exponent is stored within the coefficient and the exponent itself
• Additional terms having equal exponent is possible one
• The storage allocation for each term in the polynomial must be done in ascending and descending order of their exponent

How do you add two polynomials to a linked list?

Step 1: loop around all values of linked list and follow step 2& 3. Step 2: if the value of a node’s exponent. is greater copy this node to result node and head towards the next node. Step 3: if the values of both node’s exponent is same add the coefficients and then copy the added value with node to the result.

How many fields will be in the node for performing polynomial addition?

therefore polynomials are the expressions that contain the number of terms with non-zero exponents and coefficients. Consider the following General Represent of Polynomial. here, such as the linked representation of polynomials, each term considered as a node, therefore these node contains three fields.

How do you multiply two polynomials using linked list?

Given two polynomials in the form of linked list….Approach:

1. In this approach we will multiply the 2nd polynomial with each term of 1st polynomial.
2. Store the multiplied value in a new linked list.
3. Then we will add the coefficients of elements having the same power in resultant polynomial.

How do you add two polynomials using linked list algorithm?

Step 1: loop around all values of linked list and follow step 2& 3. Step 2: if the value of a node’s exponent. is greater copy this node to result node and head towards the next node. Step 3: if the values of both node’s exponent is same add the coefficients and then copy the added value with node to the result.

What is the time complexity of multiplying 2 polynomials represented in linked list?

Time complexity of the above solution is O(mn). If size of two polynomials same, then time complexity is O(n2).

Which linked list is used for multiple variable polynomial?

Generalized linked lists
Generalized linked lists are used because although the efficiency of polynomial operations using linked list is good but still, the disadvantage is that the linked list is unable to use multiple variable polynomial equation efficiently. It helps us to represent multi-variable polynomial along with the list of elements.

When multiplication of two polynomials is possible?

When the polynomials are multiplied it is possible they can be monomial, binomial, or trinomial. In order to multiply any two polynomials the steps used are: Multiply the coefficients. Multiply the variables using exponent rules as per the requirement.

How do you multiply two polynomials using a linked list?

Given two polynomials in the form of linked list….Approach:

1. In this approach we will multiply the 2nd polynomial with each term of 1st polynomial.
2. Store the multiplied value in a new linked list.
3. Then we will add the coefficients of elements having the same power in resultant polynomial.

Which linked list is used for multiply variable polynomial equation efficiently?

Implementation: Polynomials are implemented using single linked lists each node having a coefficient and an exponent part. Pointer is set to to highest coefficient and the lower coefficient are added as link part to one another … the end pointer being set to NULL.

How do you represent a polynomial in a linked list?

Step 1: loop around all values of linked list and follow step 2& 3. Step 2: if the value of a node’s exponent. is greater copy this node to result node and head towards the next node. Step 3: if the values of both node’s exponent is same add the coefficients and then copy the added value with node to the result.

How do you add two polynomials to a linked list?