In this article, we will learn how to perform the multiplication of two polynomials using linked lists. We will quickly brush up our knowledge on polynomials and Linked List. Then we will see how to represent polynomials using linked lists followed by a few examples to increase the clarity.
Quick reference:
What is Polynomial?
A polynomial is an algebraic expression consisting of variables, coefficients, and operations such as addition, subtraction, multiplication, and non-negative exponentiation of variables.
E.g., P(x) = x² − 5x + 9
Example
Now let us see some examples of polynomials. An example of a polynomial with one variable is x2-x+12. In this polynomial, there are three terms: x2, -x, and 12. Examples of monomials are 6x, 6a4, and 3xy. Examples of binomials are 6x+4a and 12x4 + 10x. Examples of trinomials are -8x4+3x+10 and 2x2 + 9b + 10.
Problem Statement
You are given the head pointers two linked lists representing two polynomials, say head1 and head2. Perform the multiplication of the two polynomials and return the output as a linked list. The structure of the linked list is provided below.
Now, let's take a look at an example of the multiplication of two polynomials.
Let say we have, P(x) = x² − 5x + 9 and Q(x) = x3 − 10x2 + 9x + 1
We need to find the product P(x)*Q(x).
P(x)*Q(x) = (x² − 5x + 9) * (x3 − 10x2 + 9x + 1)
Every term of P(x) will be multiplied to Q(x) in this way -
In this example, we found the product using the pen-paper method. Now, let's learn how to do the same using a linked list.`
Polynomial representation using linked list
This section will see how to represent polynomials using linked lists.
Each node in the linked list denotes one term of the polynomial.
Every node stores -
Value of exponent
Value of coefficient
Pointer to the next node
So, the structure of the node looks like this -
Example - P(x) = x² − 5x + 9 is represented by a linked list containing 3 nodes as it has 3 terms which are as follows -
Exponent = 2 and Coefficient=1
Exponent = 1 and Coefficient = -5
Exponent = 0 and Coefficient=9
Algorithm
From the previous sections, we know now how to represent a polynomial as a linked list.
So, now according to the problem statement, we have two pointers pointing to the head nodes of the given polynomials.
The algorithm is quite simple. We only need to iterate over the two linked lists, multiply the corresponding coefficients, and add the exponents. Let's see all the steps one by one below -
Define two pointers ptr1 and ptr2, which point to head1 and head2, respectively. These pointers will be used to iterate over the two lists.
Define a new node head3 which points to the head node of the resulting product polynomial.
Multiply the terms pointed by ptr1 and ptr2.
Declare two variables coefficient and exponent where coefficient = ptr1->coefficient*ptr2->coefficient and exponent = ptr1->exponent + ptr2->exponent.
Create a new node with the coefficient and exponent found above. And append it to the list pointed by head3.
Update ptr2 to point to the next node in the second polynomial and repeat the above steps till ptr2 becomes NULL.
Similarly, after each complete pass over the second polynomial, reset ptr2 to point to head2 and update ptr1 to point to the next node in the first polynomial.
Let’s see the code implementation and the time and space complexity analysis in the next section.
C++ Implementation
/*C++ code to demonstrate multiplication of polynomials using linked lists*/
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int coefficient;
int exponent;
Node *next;
};
void mergeNodes(Node *head);
void displayPolynomial(Node *ptr);
Node *appendNode(Node *start, int coefficient, int exponent);
Node *multiplyPolynomialLL(Node *head1, Node *head2,
Node *head3)
{
/* declare ptr1 and ptr2 to iterate over the two polynomials */
Node *ptr1, *ptr2;
ptr1 = head1;
ptr2 = head2;
while (ptr1 != NULL)
{
while (ptr2 != NULL)
{
int coeff, exponent;
/*multiply the coefficients*/
coeff = ptr1->coefficient * ptr2->coefficient;
/* add the exponents*/
exponent = ptr1->exponent + ptr2->exponent;
/*create and append a new node to the product list */
head3 = appendNode(head3, coeff, exponent);
// update ptr2 to point to next node
ptr2 = ptr2->next;
}
// reset ptr2 to point to head2
ptr2 = head2;
// update ptr1 to point to next node
ptr1 = ptr1->next;
}
/* call this function to merge the nodes having same exponent value */
mergeNodes(head3);
return head3;
}
// function to print the linked list as a polynomial
void displayPolynomial(Node *ptr)
{
while (ptr->next != NULL)
{
if (ptr->coefficient != 0 && ptr->coefficient != 1)
{
if (ptr->exponent != 0 && ptr->exponent != 1)
cout << ptr->coefficient << "x^" << ptr->exponent;
else if (ptr->exponent == 1)
cout << ptr->coefficient << "x";
else
cout << ptr->coefficient;
}
else if (ptr->coefficient == 1)
{
if (ptr->exponent != 0 && ptr->exponent != 1)
cout << "x^" << ptr->exponent;
else if (ptr->exponent == 1)
cout << "x";
else
cout << ptr->coefficient;
}
if (ptr->next != NULL && ptr->next->coefficient >= 0)
cout << "+";
ptr = ptr->next;
}
cout << ptr->coefficient << "\n";
}
// function to add a new term to a polynomial in the linked list
Node *appendNode(Node *start, int coefficient, int exponent)
{
// create a new node
Node *newnode = new Node;
newnode->coefficient = coefficient;
newnode->exponent = exponent;
newnode->next = NULL;
// if the linked list is empty
if (start == NULL)
return newnode;
Node *ptr = start;
// iterate till the last node
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = newnode;
return start;
}
/* function to add the coefficients of the terms having equal coefficients
in the linked list */
void mergeNodes(Node *head)
{
Node *ptr1, *ptr2, *dup;
ptr1 = head;
/* iterate over the nodes*/
while (ptr1 != NULL && ptr1->next != NULL)
{
ptr2 = ptr1;
/*compare the current node's exponent with the other nodes */
while (ptr2->next != NULL)
{
if (ptr1->exponent == ptr2->next->exponent)
{
// add the coefficients
ptr1->coefficient = ptr1->coefficient + ptr2->next->coefficient;
dup = ptr2->next;
ptr2->next = ptr2->next->next;
/* delete this node as its coefficient has been added */
delete (dup);
}
else
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}
int main()
{
Node *head1, *head2, *head3;
head1 = head2 = head3 = NULL;
/*P(x) = x² − 5x + 9*/
head1 = appendNode(head1, 1, 2);
head1 = appendNode(head1, -5, 1);
head1 = appendNode(head1, 9, 0);
/*Q(x) = x3 − 10x2 + 9x + 1*/
head2 = appendNode(head2, 1, 3);
head2 = appendNode(head2, -10, 2);
head2 = appendNode(head2, 9, 1);
head2 = appendNode(head2, 1, 0);
head3 = multiplyPolynomialLL(head1, head2, head3);
cout << "P(x) = ";
displayPolynomial(head1);
cout << "Q(x) = ";
displayPolynomial(head2);
cout << "P(x)*Q(x) = ";
displayPolynomial(head3);
return 0;
}
You can also try this code with Online C++ Compiler
// Java implementation of above approach
import java.util.*;
class Main
{
// 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);
}
}
You can also try this code with Online Java Compiler
# 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);
You can also try this code with Online Python Compiler
The time complexity for the above-discussed approach is O(n*m), where n is the number of nodes in the first polynomial and m is the number of nodes in the second polynomial because we used two nested loops.
Space Complexity
The space complexity for the above approach is O(n+m), we need to store all the multiplied values in the node.
Frequently Asked Questions
What is polynomial representation?
A polynomial object is an ordered collection of homogeneous pairs of exponents and coefficients, where each coefficient is distinct. Returning the degree, obtaining the coefficient for an exponent supplied, adding, multiplying, and evaluating an input are examples of operations.
How to do polynomial multiplication using linked list?
Here we multiply the second polynomial by each term in the first polynomial. The multiplied value should be kept in a new linked list. The coefficients of elements with the same power will then be added to the polynomial that results.
What are the advantages of representing polynomial using a linked list?
The manipulation of polynomials is effective using this format. It improves processing effectiveness. A linked list can be used to display it. A node in the linked list is represented by each polynomial term.
Can linked list be used for polynomial manipulation?
Yes, a linked list can be used for polynomial manipulation. The manipulation of polynomials is effective using this format. Each term of the polynomial is represented as a node in the linked list.
Conclusion
In this article, we first learned about the representation of polynomials as a linked list, followed by the algorithm for the multiplication of two polynomials.
8+ registered 