Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Polynomial?
2.1.
Example
3.
Problem Statement
4.
Polynomial representation using linked list
5.
Algorithm
5.1.
C++ Implementation
5.2.
Java Implementation
5.3.
Python Implementation
5.4.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What is polynomial representation?
6.2.
How to do polynomial multiplication using linked list?
6.3.
What are the advantages of representing polynomial using a linked list?
6.4.
Can linked list be used for polynomial manipulation?
7.
Conclusion
Last Updated: May 23, 2024
Medium

Polynomials Using Linked List and Arrays

Author Yukti Kumari
3 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Polynomial Representation Using Linked List

Introduction

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. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 - 

P(x)*Q(x) x² (x3 − 10x2 + 9x + 1) - 5x(x3 − 10x2 + 9x + 1+ 9(x3−10x2+  9x + 1)

To multiply any two terms, we multiply their coefficients and add up the exponents of the variable.

So, we get - 

P(x)*Q(x) =x5 - 10x4 + 9x3 + x2 - 5x4+50x3 -45x2 - 5x + 9x- 90x2 + 81x + 9 

                =x -15x4 +68x3 -134x2 +76x +9

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 - 

 

structure of the node

ExampleP(x) x² − 5x + 9 is represented by a linked list containing 3 nodes as it has 3 terms which are as follows - 

  1. Exponent = 2 and Coefficient=1
  2. Exponent = 1 and Coefficient = -5
  3. Exponent = 0 and Coefficient=9
     
Linked list to represent polynomials

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 - 

  1. Define two pointers ptr1 and ptr2, which point to head1 and head2, respectively. These pointers will be used to iterate over the two lists.
     
  2. Define a new node head3 which points to the head node of the resulting product polynomial.
     
  3. Multiply the terms pointed by ptr1 and ptr2
     
  4. Declare two variables coefficient and exponent where coefficient = ptr1->coefficient*ptr2->coefficient and exponent = ptr1->exponent + ptr2->exponent.
     
  5. Create a new node with the coefficient and exponent found above. And append it to the list pointed by head3.
     
  6. Update ptr2 to point to the next node in the second polynomial and repeat the above steps till ptr2 becomes NULL
     
  7. 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;
}

Java Implementation

// 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);
}
}

Python Implementation

# 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);

Output 

P(x) = x^2-5x+9
Q(x) = x^3-10x^2+9x+1
P(x)*Q(x) = x^5-15x^4+68x^3-134x^2+76x+9

Complexity Analysis

Time Complexity

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. 

This is one of the widely popular applications of linked lists.

If you want to learn linked lists from scratch, then do check out this amazing article on the Advantages and Disadvantages of Linked List. Also, see Data Structures and algorithms in C++.

Some of the questions are based on applications of the linked list, which you must solve to test your understanding.


To practice more problems based on the linked list, you can check out - The Linked List Archives.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series and check out some Interview Experiences on Code360 now!

Previous article
Merge One Linked List into Another at Alternate Positions
Next article
Union and Intersection of two Linked Lists (using Merge Sort)
Live masterclass