Multiplication of Two Polynomials using Linked List

In this article, we will learn polynomial multiplication in data structure. There are two polynomial which are stored in two linked list, we have to perform operations to give result as a polynomial multiplication. One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.Let’s Discuss how can we can do polynomial multiplication using linked list.

We are given 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 Polynomials using Linked List

We have been given two linked lists representing a polynomial each. Let’s say Poly1 and Poly2 is the given polynomials, so we need to multiply the polynomials and print the output.

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: 3x3 + 6x1 – 9
Poly2: 9x3 – 8x2 + 7x1 + 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 list has a different power of x.

Output

Resultant Polynomial: 27x6 – 24x5 + 75x4 – 123x3 + 114x2 – 51x1 – 18

Some other examples:

Input 1
Poly1: 6x1 – 9
Poly2: 7x1 + 2

Output 1
Resultant Polynomial: 42x2 – 51x1 – 18

Input 2
Poly1: 8x1 + 7
Poly2: 4x2 + 5

Output 2
Resultant Polynomial: 32x3 + 28x2 + 40x1 + 35

Now 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

- First, we will traverse the Poly1 and multiply each of its nodes, with each and every node in Poly2.
- We will multiply the power of the nodes and store it in a variable power.
- We will multiply the coefficients of the nodes and store it in a variable coeff.
- Then we will add a new node in Poly3 with power and coeff values.
  1. We will perform step 1 until each node in Poly1 has been multiplied with every node of Poly2.
  2. After all the terms in the given polynomials are multiplied and stored in a new list Poly3, then we will combine the different terms with the same power.
    • We will traverse the Poly3 to compare the power of each factor, starting with the next node.
    • If the power is same for any factors, we will add the coefficients and remove the other duplicate node.
  3. So now what we have is the required polynomial, and we can print the answer.

    Dry run of Polynomial Multiplication Using Linked List

    Let’s dry run 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 3x3 with every other term in Poly2.(result: 27x6 – 24x5 + 21x4 + 6x3)
    • Now we take 6x1 and multiply it with every other term in Poly2.(result: 27x6 – 24x5 + 21x4 + 6x3 + 54x4 – 48x3 + 42x2 + 12x1)
    • Now we take -9 and multiply it with every other term in Poly2.(result: 27x6 – 24x5 + 21x4 + 6x3 + 54x4 – 48x3 + 42x2 + 12x1 – 81x3 + 72x2 – 63x1 – 18)
    • We will remove all the duplicates, i.e., add the value of nodes with the same powers.
    • So the final result: 27x6 – 24x5 + 75x4 – 123x3 + 114x2 – 51x1 – 18

    You can take examples by yourself to get a better understanding of the problem.

    Code Implementation of Multiplication of two polynomials using Linked List:

    #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 + 48

    Time Complexity of Polynomial Multiplication Using Linked List: 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: O(n+m), we need to store all the multiplied values in the node.

    Conclusion

    This blog has tried to explain how you can do polynomial multiplication using a linked list. The linked list is one of the important topics of the Data Structures which plays a very crucial role in the placement of any job seeker in the IT industry. If you want to practice more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

FAQ Related to Polynomial Multiplication Using Linked List

  1. Is a linked list suitable for polynomial manipulation?
    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.

  2. What is the advantage of using a linked list for representing polynomials over an array?
    A few advantages of linked lists over arrays are :

    • Dynamic size.
    • Efficient implementation of data structures.
    • No memory wastage.
    • Efficient insertion and deletion operation.
  3. How is a polynomial stored using a linked list?
    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.

Leave a Reply

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