Last Updated on July 27, 2023 by Mayank Dham
To perform polynomial multiplication in C, we can represent each polynomial as a linked list of nodes, each with a coefficient and an exponent. The exponent represents the degree. The polynomial multiplication using a linked list in c has two polynomials that are stored in two linked lists, and we must perform operations to obtain the result as a polynomial multiplication. g a linked list in c has two polynomials which are stored in two linked lists, we have to perform operations to give the result as a polynomial multiplication. One of the most crucial data structures to learn while preparing for interviews is the linked list. We start with two polynomials in the form of linked lists, and we need to make a new list that contains the multiplicative product of the given polynomials.
We assume two polynomials in the form of linked lists, and we need to create a new list containing the multiplicative product of the given polynomials.
Multiplication of 2 for Polynomial Multiplication using Linked List
Let’s try to understand the problem with the help of examples by referring to the websites to learn to program.
Suppose the given linked lists are:
Poly1: 3×3 + 6×1 – 9
Poly2: 9×3 – 8×2 + 7×1 + 2
- Now, according to the problem statement, we need to multiply these polynomials Poly1 and Poly2.
- So we will multiply each term in Poly1 with every term in Poly2, and then we will add up all the terms with the same power of x such that each term in the final resultant polynomial multiplication using linked list has a different power of x.
Output
Resultant Polynomial: 27x6 – 24x5 + 75x4 – 123x3 + 114x2 – 51x1 – 18Some other examples:
Input 1
Poly1: 6x1 – 9
Poly2: 7x1 + 2Output 1
Resultant Polynomial: 42x2 – 51x1 – 18Input 2
Poly1: 8x1 + 7
Poly2: 4x2 + 5Output 2
Resultant Polynomial: 32x3 + 28x2 + 40x1 + 35Now I think from the above examples the problem statement is clear. So, let’s see How can we do polynomial multiplication using linked list?
Approach and Algorithm of Polynomial Multiplication using Linked List in C
Here is the algorithm for polynomial multiplication using linked lists in C:
- First define the node structure to hold the coefficient and exponent values, as well as a pointer to the next node.
- Create a function to create a new node with the specified coefficient and exponent values.
- Create a function to insert a new node into a linked list based on its exponent value.
- Create a function to print the linked list.
- Create a function to multiply two polynomials represented as linked lists.
- Iterate over each term in the first polynomial, multiply it with each term in the second polynomial, and add the resulting term to the result polynomial using the insert_node() function.
- Return the resulting polynomial as a linked list.
Dry Run of Polynomial Multiplication using Linked List in C
Let’s dry run the polynomial multiplication using linked list with an example:
Poly1: 3x^3 + 6x^1 – 9
Poly2: 9x^3 – 8x^2 + 7x^1 + 2
To multiply the above polynomials Poly1 and Poly2 we will have to perform the following operations:
We have to multiply all the terms of Poly1 one by one with every term of Poly2, so first, we will multiply 3×3 with every other term in Poly2.(result: 27×6 – 24×5 + 21×4 + 6×3)
Now we take 6×1 and multiply it with every other term in Poly2.(result: 27×6 – 24×5 + 21×4 + 6×3 + 54×4 – 48×3 + 42×2 + 12×1)
Now we take -9 and multiply it with every other term in Poly2.(result: 27×6 – 24×5 + 21×4 + 6×3 + 54×4 – 48×3 + 42×2 + 12×1 – 81×3 + 72×2 – 63×1 – 18)
We will remove all the duplicates, i.e., add the value of nodes with the same powers.
So the final result: 27×6 – 24×5 + 75×4 – 123×3 + 114×2 – 51×1 – 18
You can take examples by yourself to get a better understanding of the problem.
Code Implementation of Polynomial Multiplication using Linked List in C
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
// Define useful field of Node
int data;
int power;
struct Node * next;
}Node;
Node * getNode(int data, int power)
{
// Create dynamic memory of Node
Node * ref = (Node * ) malloc(sizeof(Node));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
ref->data = data;
ref->power = power;
ref->next = NULL;
return ref;
}
// Update node value
void updateRecord(Node * ref, int data, int power)
{
ref->data = data;
ref->power = power;
}
typedef struct MultiplyPolynomial
{
// Define useful field of MultiplyPolynomial
struct Node * head;
}MultiplyPolynomial;
MultiplyPolynomial * getMultiplyPolynomial()
{
// Create dynamic memory of MultiplyPolynomial
MultiplyPolynomial * ref = (MultiplyPolynomial * )
malloc(sizeof(MultiplyPolynomial));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
ref->head = NULL;
return ref;
}
// Insert Node element
void insert(MultiplyPolynomial * ref, int data, int power)
{
if (ref->head == NULL)
{
// Add first node
ref->head = getNode(data, power);
}
else
{
Node * node = NULL;
Node * temp = ref->head;
Node * location = NULL;
// Find the valid new node location
while (temp != NULL && temp->power >= power)
{
location = temp;
temp = temp->next;
}
if (location != NULL && location->power == power)
{
// When polynomial power already exists
// Then add current add to previous data
location->data = location->data + data;
}
else
{
node = getNode(data, power);
if (location == NULL)
{
// When add node in begining
node->next = ref->head;
ref->head = node;
}
else
{
// When adding node in intermediate
// location or end location
node->next = location->next;
location->next = node;
}
}
}
}
// Perform multiplication of given polynomial
MultiplyPolynomial * multiplyPolynomials(
MultiplyPolynomial * ref, MultiplyPolynomial * other)
{
// Define some useful variable
MultiplyPolynomial * result = getMultiplyPolynomial();
// Get first node of polynomial
Node * poly1 = ref->head;
Node * temp = other->head;
int power_value = 0;
int coefficient = 0;
// Execute loop until when polynomial are exist
while (poly1 != NULL)
{
temp = other->head;
while (temp != NULL)
{
// Get result info
power_value = poly1->power + temp->power;
coefficient = poly1->data * temp->data;
insert(result, coefficient, power_value);
// Visit to next node
temp = temp->next;
}
// Visit to next node
poly1 = poly1->next;
}
// return first node
return result;
}
// Display given polynomial nodes
void display(MultiplyPolynomial * ref)
{
if (ref->head == NULL)
{
printf("Empty Polynomial ");
}
printf(" ");
Node * temp = ref->head;
while (temp != NULL)
{
if (temp != ref->head)
{
printf(" + %d", temp->data);
}
else
{
printf("%d",temp->data);
}
if (temp->power != 0)
{
printf("x^%d", temp->power);
}
// Visit to next node
temp = temp->next;
}
printf("\n");
}
int main()
{
MultiplyPolynomial * a = getMultiplyPolynomial();
MultiplyPolynomial * b = getMultiplyPolynomial();
// Add node in polynomial A
insert(a, 9, 3);
insert(a, 4, 2);
insert(a, 3, 0);
insert(a, 7, 1);
insert(a, 3, 4);
// Add node in polynomial b
insert(b, 7, 3);
insert(b, 4, 0);
insert(b, 6, 1);
insert(b, 1, 2);
// Display Polynomial nodes
printf("\n Polynomial A\n");
display(a);
printf(" Polynomial B\n");
display(b);
MultiplyPolynomial * result = multiplyPolynomials(a, b);
// Display calculated result
printf(" Result\n");
display(result);
}
import java.util.*;
class PrepBytes
{
static class Node {
int coeff, power;
Node next;
};
static Node addnode(Node start, int coeff, int power)
{
Node newnode = new Node();
newnode.coeff = coeff;
newnode.power = power;
newnode.next = null;
if (start == null)
return newnode;
Node ptr = start;
while (ptr.next != null)
ptr = ptr.next;
ptr.next = newnode;
return start;
}
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");
}
static void removeDuplicates(Node start)
{
Node ptr1, ptr2, dup;
ptr1 = start;
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
while (ptr2.next != null) {
if (ptr1.power == ptr2.next.power) {
ptr1.coeff = ptr1.coeff + ptr2.next.coeff;
dup = ptr2.next;
ptr2.next = ptr2.next.next;
}
else
ptr2 = ptr2.next;
}
ptr1 = ptr1.next;
}
}
static Node multiply(Node poly1, Node poly2,
Node poly3)
{
Node ptr1, ptr2;
ptr1 = poly1;
ptr2 = poly2;
while (ptr1 != null) {
while (ptr2 != null) {
int coeff, power;
coeff = ptr1.coeff * ptr2.coeff;
power = ptr1.power + ptr2.power;
poly3 = addnode(poly3, coeff, power);
ptr2 = ptr2.next;
}
ptr2 = poly2;
ptr1 = ptr1.next;
}
removeDuplicates(poly3);
return poly3;
}
public static void main(String args[])
{
Node poly1 = null, poly2 = null, poly3 = null;
poly1 = addnode(poly1, 3, 2);
poly1 = addnode(poly1, 5, 1);
poly1 = addnode(poly1, 6, 0);
poly2 = addnode(poly2, 6, 1);
poly2 = addnode(poly2, 8, 0);
poly3 = multiply(poly1, poly2, poly3);
System.out.print( "Resultant Polynomial: ");
printList(poly3);
}
}
class Node:
def __init__(self):
self.coeff = None
self.power = None
self.next = None
def addnode(start, coeff, power):
newnode = Node()
newnode.coeff = coeff
newnode.power = power
newnode.next = None
if (start == None):
return newnode
ptr = start
while (ptr.next != None):
ptr = ptr.next
ptr.next = newnode
return start
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)
def removeDuplicates(start):
ptr2 = None
dup = None
ptr1 = start
while (ptr1 != None and ptr1.next != None):
ptr2 = ptr1
while (ptr2.next != None):
if (ptr1.power == ptr2.next.power):
ptr1.coeff = ptr1.coeff + ptr2.next.coeff
dup = ptr2.next
ptr2.next = ptr2.next.next
else:
ptr2 = ptr2.next
ptr1 = ptr1.next
def multiply(poly1, Npoly2, poly3):
ptr1 = poly1
ptr2 = poly2
while (ptr1 != None):
while (ptr2 != None):
coeff = ptr1.coeff * ptr2.coeff
power = ptr1.power + ptr2.power
poly3 = addnode(poly3, coeff, power)
ptr2 = ptr2.next
ptr2 = poly2
ptr1 = ptr1.next
removeDuplicates(poly3)
return poly3
if __name__=='__main__':
poly1 = None
poly2 = None
poly3 = None
poly1 = addnode(poly1, 3, 2)
poly1 = addnode(poly1, 5, 1)
poly1 = addnode(poly1, 6, 0)
poly2 = addnode(poly2, 6, 1)
poly2 = addnode(poly2, 8, 0)
poly3 = multiply(poly1, poly2, poly3)
print("Resultant Polynomial:- ", end = '')
printList(poly3)
Output:
Resultant Polynomial: 18x3 + 54x2 + 76x1 + 48Time Complexity of polynomial multiplication using linked list : The time complexity of polynomial multiplication using linked list is O(n*m), where n is the total number of nodes in the first polynomial and m is the number of nodes in the second polynomial.
Space Complexity of polynomial multiplication using linked list: The space complexity of polynomial multiplication using linked list is O(n+m), we need to store all the multiplied values in the node.
Conclusion
Polynomial multiplication with linked lists is a quick and easy way to multiply polynomials. Polynomial multiplication in C is accomplished by expressing each polynomial as a linked list of nodes, multiplying each term in one polynomial by each term in the other polynomial, and adding the resultant terms to a new linked list to represent the final polynomial. This polynomial multiplication method in C may be simply implemented by utilising the functions. The linked list is an important topic in Data Structures that plays a significant part in the placement of any job applicant in the IT sector.
FAQ Related to Polynomial Multiplication Using Linked List
Q1. What is a linked list?
Ans: A linked list is a data structure that consists of a sequence of nodes, each containing some data and a pointer to the next node in the list.
Q2. Is a linked list suitable for polynomial manipulation?
Ans: Polynomial manipulation can be represented using a linked list. This representation makes polynomial manipulation efficient. While representing a polynomial using a linked list, each polynomial term represents a node in the linked list.
Q3. What is the advantage of using a linked list for representing polynomials over an array?
Ans: A few advantages of linked lists over arrays are :
- Dynamic size.
- Efficient implementation of data structures.
- No memory wastage.
- Efficient insertion and deletion operation.
Q4. How is a polynomial stored using a linked list?
Ans: We store each polynomial as a singly linked list where each node stores the exponent and coefficient in the data part and a reference to the next node. Their sum is then stored in another linked list.
Q5. How efficient is polynomial multiplication using linked lists?
Ans: Polynomial multiplication using linked lists is a relatively efficient method, with a time complexity of O(n^2), where n is the number of terms in the polynomials. However, other methods such as the Fast Fourier Transform algorithm can achieve a faster time complexity of O(n log n) for large polynomials.
Q6. Can polynomial multiplication using linked lists be used for real-world applications?
Ans: Yes, polynomial multiplication using linked lists can be used for real-world applications such as signal processing, image processing, and cryptography, where polynomials are commonly used to represent signals, images, and encryption keys.