Polynomial Operations Using Linked List: Addition, Subtraction & Multiplication

CHAPTER 21 • DATA STRUCTURE

Polynomial Operations Using Linked List: Addition, Subtraction & Multiplication

Learn how to add, subtract and multiply polynomials using Linked Lists with simple explanations, diagrams, step-by-step dry runs, algorithms and C programs.

Polynomial Addition Polynomial Subtraction Polynomial Multiplication C Programming

Polynomial operations can feel difficult when we study them in Data Structure. In Mathematics, we simply add, subtract or multiply expressions. But in programming, we have to perform the same operations using nodes and pointers.

Many students understand the formula but become confused when two Linked Lists have different exponents or negative coefficients.

The good thing is that the concept becomes much easier when we compare one term at a time and understand what happens to the next pointer.

Quick Answer: Polynomial Operations Using Linked List are methods of performing addition, subtraction and multiplication on polynomials stored as connected nodes. Each node contains a coefficient, exponent and next pointer. In addition and subtraction, terms with equal exponents are combined. In multiplication, coefficients are multiplied, exponents are added, and like terms are merged.

Before solving these operations, you should understand how nodes are connected. You can revise Linked List in Data Structure: Types, Operations and Examples .

What are Polynomial Operations Using Linked List?

Polynomial Operations Using Linked List: Addition, Subtraction & Multiplication

Polynomial Operations mean performing mathematical calculations on polynomial expressions stored inside Linked Lists.

The three most important operations for Data Structure exams are:

Operation 01

Addition

Add the coefficients of terms with equal exponents.

Operation 02

Subtraction

Subtract coefficients of terms with equal exponents.

Operation 03

Multiplication

Multiply every term and combine the resulting like terms.

Quick Revision: Polynomial Node

Every polynomial term is stored in a node containing three fields.

Node = Coefficient + Exponent + Next
Orange: Coefficient Blue: Exponent Green: Next Pointer
Figure 1: A polynomial node representing 4x³

The next pointer connects the current term to the following term.

For the algorithms in this chapter, both input Linked Lists are arranged in descending order of exponents, with only one node per non-zero term.

Memory Trick: CEN

C = Coefficient, E = Exponent, N = Next Pointer.

Remember CEN whenever a polynomial Linked List node diagram is asked in an examination.

1. Polynomial Addition Using Linked List

Polynomial Addition means adding two polynomials by combining the terms that have the same exponent.

When both Linked Lists are sorted by exponent, we compare their first nodes and then move the pointers forward step by step.

Definition: Polynomial Addition Using Linked List is the process of merging two polynomial lists by adding coefficients of equal-exponent terms and copying unmatched terms into a result list.

Rules of Polynomial Addition

Equal Exponents

3x² + 4x² = 7x²

Add the coefficients and keep the same exponent.

Different Exponents

3x³ + 4x²

Do not combine these terms. Keep both in the result.

Solved Example: Addition

Consider the following polynomials:

P(x) = 4x4 + 3x2 - 2x + 5
Q(x) = 2x3 - 3x2 + 2x - 5

We have to calculate P(x) + Q(x).

Step-by-Step Dry Run

1
Compare exponent 4.

P contains 4x⁴ and Q has no x⁴ term. Copy 4x⁴ to the result.

2
Compare exponent 3.

Q contains 2x³ and P has no x³ term. Copy 2x³ to the result.

3
Compare exponent 2.

P contains 3x² and Q contains -3x². Their sum is zero, so this term is not included.

4
Compare exponent 1.

P contains -2x and Q contains 2x. Their sum is zero, so skip this term.

5
Compare constant terms.

P contains 5 and Q contains -5. Adding them gives zero.

Addition Dry Run Table

Exponent P Coefficient Q Coefficient Sum
4404
3022
23-30
1-220
05-50
Final Addition Result:
P(x) + Q(x) = 4x4 + 2x3

Linked List Diagram After Addition

Figure 2: Addition produces only two non-zero polynomial nodes.
Important Concept: Zero Cancellation

When two coefficients add up to zero, we do not need a node for that term. This is why the result contains only two nodes, even though the original lists contained more terms.

Algorithm for Polynomial Addition

START

P = HEAD1
Q = HEAD2
RESULT = EMPTY

WHILE P != NULL AND Q != NULL

    IF P.exp == Q.exp
        SUM = P.coeff + Q.coeff

        IF SUM != 0
            APPEND(RESULT, SUM, P.exp)
        END IF

        P = P.next
        Q = Q.next

    ELSE IF P.exp > Q.exp

        APPEND(RESULT, P.coeff, P.exp)
        P = P.next

    ELSE

        APPEND(RESULT, Q.coeff, Q.exp)
        Q = Q.next

    END IF

END WHILE

APPEND remaining terms from P and Q

RETURN RESULT

STOP

Time Complexity of Addition

If P contains m nodes and Q contains n nodes, we traverse the two sorted lists only once.

Addition Time Complexity = O(m + n)

2. Polynomial Subtraction Using Linked List

Polynomial Subtraction is similar to addition, but one important rule changes. We subtract the coefficients instead of adding them.

Many students make mistakes because they forget to change the signs of the second polynomial.

Definition: Polynomial Subtraction Using Linked List is the process of subtracting the coefficients of equal-exponent terms while creating a new result list. It can also be performed by changing the signs of the second polynomial and applying polynomial addition.

Easy Rule for Polynomial Subtraction

P(x) - Q(x) = P(x) + [-Q(x)]

This means subtraction can be understood as addition after reversing the signs of Q.

Solved Example: Subtraction

Take the same polynomials:

P(x) = 4x4 + 3x2 - 2x + 5
Q(x) = 2x3 - 3x2 + 2x - 5

We need to find P(x) - Q(x).

Step 1: Change Signs of Q

Sign Reversal

Original Q(x):

2x3 - 3x2 + 2x - 5

Negative of Q(x):

-2x3 + 3x2 - 2x + 5

Step 2: Add P and -Q

Exponent P Coefficient Q Coefficient P - Q
4404
302-2
23-36
1-22-4
05-510

Step-by-Step Explanation

1
Exponent 4

4 - 0 = 4, so the result contains 4x⁴.

2
Exponent 3

0 - 2 = -2, so the result contains -2x³.

3
Exponent 2

3 - (-3) = 6, so the result contains 6x².

4
Exponent 1

-2 - 2 = -4, so the result contains -4x.

5
Constant Term

5 - (-5) = 10, so the result contains constant 10.

Final Subtraction Result:
P(x) - Q(x) = 4x4 - 2x3 + 6x2 - 4x + 10

Result Linked List

Figure 3: Subtraction result with positive and negative coefficients.

Algorithm for Polynomial Subtraction

START

P = HEAD1
Q = HEAD2
RESULT = EMPTY

WHILE P != NULL AND Q != NULL

    IF P.exp == Q.exp

        DIFF = P.coeff - Q.coeff

        IF DIFF != 0
            APPEND(RESULT, DIFF, P.exp)
        END IF

        P = P.next
        Q = Q.next

    ELSE IF P.exp > Q.exp

        APPEND(RESULT, P.coeff, P.exp)
        P = P.next

    ELSE

        APPEND(RESULT, -Q.coeff, Q.exp)
        Q = Q.next

    END IF

END WHILE

APPEND remaining P terms unchanged

APPEND remaining Q terms with negative coefficients

RETURN RESULT

STOP
Common Exam Mistake: When a term is present only in Q, do not copy it with the original sign. During P - Q, its coefficient must become negative.

Time Complexity of Subtraction

Just like addition, we compare and process each node once when both input lists are sorted.

Subtraction Time Complexity = O(m + n)

3. Polynomial Multiplication Using Linked List

Multiplication requires a different approach from addition and subtraction.

Instead of simply comparing the current exponents, we multiply every term of the first polynomial by every term of the second polynomial.

Definition: Polynomial Multiplication Using Linked List is the process of multiplying each term of the first polynomial with each term of the second polynomial. For every pair, coefficients are multiplied, exponents are added, and terms with equal resulting exponents are combined.

Two Important Multiplication Rules

Rule 1

Multiply Coefficients

2 × 3 = 6

Multiply the numerical values of the two terms.

Rule 2

Add Exponents

x² × x³ = x⁵

When the variable is the same, add the exponents.

Solved Example: Multiplication

For an easy dry run, take two smaller polynomials:

A(x) = 2x² + 3x + 1
B(x) = x + 2

We have to calculate A(x) × B(x).

Step 1: Multiply Every Term of A by x

x(2x² + 3x + 1) = 2x³ + 3x² + x

Step 2: Multiply Every Term of A by 2

2(2x² + 3x + 1) = 4x² + 6x + 2

Step 3: Combine Like Terms

Term from A Term from B Product
2x²x2x³
2x²24x²
3xx3x²
3x26x
1xx
122

Now combine the terms containing the same exponent.

x³ Term

2x³ remains unchanged.

x² Terms

4x² + 3x² = 7x².

x Terms

6x + x = 7x.

Constant Term

The constant is 2.

Final Multiplication Result:
A(x) × B(x) = 2x3 + 7x2 + 7x + 2

Result Linked List Diagram

Figure 4: Polynomial multiplication produces four distinct non-zero terms.

Algorithm for Polynomial Multiplication

START

RESULT = EMPTY
P = HEAD1

WHILE P != NULL

    Q = HEAD2

    WHILE Q != NULL

        COEFF = P.coeff * Q.coeff
        EXP = P.exp + Q.exp

        INSERT_OR_COMBINE(
            RESULT, COEFF, EXP
        )

        Q = Q.next

    END WHILE

    P = P.next

END WHILE

RETURN RESULT

STOP

How Does the Algorithm Work?

1
Select the first term of A.

Start with 2x².

2
Multiply it by every term of B.

Create 2x³ and 4x².

3
Move to the next term of A.

Multiply 3x by both terms of B. Add products to the result.

4
Combine repeated powers.

Combine 4x² and 3x² into one 7x² node.

5
Finish the remaining terms.

Continue until all pairs are processed. Keep the result in descending exponent order.

Memory Trick for Multiplication:

MCA Rule

M = Multiply coefficients
C = Combine like terms
A = Add exponents for each product

C Program for Polynomial Addition, Subtraction and Multiplication

The following C program performs all three polynomial operations using Linked Lists.

The program keeps nodes sorted by exponent, combines equal-exponent terms and removes terms whose coefficient becomes zero.

Complete C Program

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    long long coeff;
    int exp;
    struct Node *next;
} Node;

Node *newNode(long long coeff, int exp) {
    Node *node = malloc(sizeof *node);

    if (!node) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    node->coeff = coeff;
    node->exp = exp;
    node->next = NULL;
    return node;
}

void insertTerm(Node **head, long long coeff, int exp) {
    if (coeff == 0) return;

    Node **place = head;

    while (*place && (*place)->exp > exp)
        place = &(*place)->next;

    if (*place && (*place)->exp == exp) {
        (*place)->coeff += coeff;

        if ((*place)->coeff == 0) {
            Node *old = *place;
            *place = old->next;
            free(old);
        }

        return;
    }

    Node *node = newNode(coeff, exp);
    node->next = *place;
    *place = node;
}

void appendTerm(Node **head, Node **tail,
                long long coeff, int exp) {
    if (coeff == 0) return;

    Node *node = newNode(coeff, exp);

    if (*tail)
        (*tail)->next = node;
    else
        *head = node;

    *tail = node;
}

Node *combine(const Node *a, const Node *b,
              int subtract) {
    Node *head = NULL;
    Node *tail = NULL;

    while (a && b) {
        if (a->exp == b->exp) {
            appendTerm(
                &head, &tail,
                a->coeff + (subtract ? -b->coeff : b->coeff),
                a->exp
            );

            a = a->next;
            b = b->next;

        } else if (a->exp > b->exp) {
            appendTerm(&head, &tail,
                       a->coeff, a->exp);
            a = a->next;

        } else {
            appendTerm(
                &head, &tail,
                subtract ? -b->coeff : b->coeff,
                b->exp
            );

            b = b->next;
        }
    }

    while (a) {
        appendTerm(&head, &tail,
                   a->coeff, a->exp);
        a = a->next;
    }

    while (b) {
        appendTerm(
            &head, &tail,
            subtract ? -b->coeff : b->coeff,
            b->exp
        );

        b = b->next;
    }

    return head;
}

Node *multiply(const Node *a, const Node *b) {
    Node *result = NULL;

    for (const Node *p = a; p; p = p->next) {
        for (const Node *q = b; q; q = q->next) {
            insertTerm(
                &result,
                p->coeff * q->coeff,
                p->exp + q->exp
            );
        }
    }

    return result;
}

void printPoly(const Node *p) {
    if (!p) {
        puts("0");
        return;
    }

    int first = 1;

    while (p) {
        long long c = p->coeff;

        if (c < 0) {
            printf(first ? "-" : " - ");
            c = -c;
        } else if (!first) {
            printf(" + ");
        }

        if (p->exp == 0)
            printf("%lld", c);
        else if (p->exp == 1)
            printf("%lldx", c);
        else
            printf("%lldx^%d", c, p->exp);

        first = 0;
        p = p->next;
    }

    putchar('\n');
}

void freePoly(Node *head) {
    while (head) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void) {
    Node *p = NULL, *q = NULL;
    Node *a = NULL, *b = NULL;

    insertTerm(&p, 4, 4);
    insertTerm(&p, 3, 2);
    insertTerm(&p, -2, 1);
    insertTerm(&p, 5, 0);

    insertTerm(&q, 2, 3);
    insertTerm(&q, -3, 2);
    insertTerm(&q, 2, 1);
    insertTerm(&q, -5, 0);

    Node *sum = combine(p, q, 0);
    Node *difference = combine(p, q, 1);

    insertTerm(&a, 2, 2);
    insertTerm(&a, 3, 1);
    insertTerm(&a, 1, 0);

    insertTerm(&b, 1, 1);
    insertTerm(&b, 2, 0);

    Node *product = multiply(a, b);

    printf("P(x) = ");
    printPoly(p);

    printf("Q(x) = ");
    printPoly(q);

    printf("P + Q = ");
    printPoly(sum);

    printf("P - Q = ");
    printPoly(difference);

    printf("A(x) = ");
    printPoly(a);

    printf("B(x) = ");
    printPoly(b);

    printf("A * B = ");
    printPoly(product);

    freePoly(p);
    freePoly(q);
    freePoly(a);
    freePoly(b);
    freePoly(sum);
    freePoly(difference);
    freePoly(product);

    return 0;
}

Program Output

P(x) = 4x^4 + 3x^2 - 2x + 5
Q(x) = 2x^3 - 3x^2 + 2x - 5
P + Q = 4x^4 + 2x^3
P - Q = 4x^4 - 2x^3 + 6x^2 - 4x + 10
A(x) = 2x^2 + 3x + 1
B(x) = 1x + 2
A * B = 2x^3 + 7x^2 + 7x + 2

Explanation of Important Functions

newNode()

Allocates memory and creates a node containing coefficient and exponent.

insertTerm()

Inserts a term in descending exponent order and combines equal exponents.

combine()

Performs addition or subtraction depending on the subtract argument.

multiply()

Uses nested loops to multiply every pair of polynomial terms.

printPoly()

Displays the polynomial with coefficients, exponents and signs.

freePoly()

Releases allocated memory after the operations are completed.

Programming Note: The example assumes non-negative integer exponents and coefficients/results within the supported integer range. It is designed for learning Linked List operations rather than unrestricted symbolic mathematics.

Difference Between Polynomial Addition, Subtraction and Multiplication

All three operations use polynomial Linked Lists, but their working rules are different.

Basis Addition Subtraction Multiplication
Main Task Add terms Subtract terms Multiply terms
Coefficient Rule Add Subtract Multiply
Exponent Rule Match powers Match powers Add powers
Working Merge lists Merge with sign reversal Nested term pairing
Like Terms Combine Combine Combine products
Zero Terms Skip Skip Skip

One Example for All Three Operations

Addition
2x + 3x = 5x

Coefficients are added. Exponent stays 1.

Subtraction
5x - 2x = 3x

Coefficients are subtracted. Exponent stays 1.

Multiplication
2x × 3x = 6x²

Coefficients multiply. Exponents are added.

Time and Space Complexity of Polynomial Operations

Complexity tells us how the running time and memory usage increase when the number of polynomial terms grows.

Operation Time Extra Space
Addition of sorted lists O(m + n) O(m + n)
Subtraction of sorted lists O(m + n) O(m + n)
Generate multiplication products O(mn) Depends on storage
Multiplication using sorted insertion O(mnr) O(r)

Here, m is the number of nodes in the first polynomial, n is the number of nodes in the second polynomial, and r is the maximum number of distinct terms kept in the result.

Addition and subtraction use a merge-style process for sorted lists. The multiplication complexity shown is for the simple sorted-insertion implementation used here. Different algorithms can offer different complexity.

Common Mistake: Do not say every polynomial multiplication implementation takes only O(mn) time. Generating products requires O(mn) pairings, but combining them into the result may require additional searching or insertion work.

Advantages of Performing Polynomial Operations Using Linked List

Flexible Result Size

Result nodes can be created dynamically as new non-zero terms appear.

Zero Terms Can Be Removed

If addition or subtraction produces a zero coefficient, the term need not be stored.

Efficient Merge Operations

Sorted polynomial lists can be added or subtracted in linear time.

Useful for Sparse Polynomials

Only useful non-zero terms are stored in nodes, instead of every possible power.

Limitations of Polynomial Linked List Operations

  • Every node needs memory for a pointer.
  • Searching for a particular exponent may take O(n).
  • Multiplication may create many intermediate products.
  • Incorrect pointer updates can disconnect nodes.
  • Memory allocation and release require care in C.
  • Dense polynomial arrays can sometimes be more efficient.

Common Mistakes in Polynomial Operations

1. Adding Different Powers

Terms such as 3x² and 4x³ cannot be combined during addition or subtraction.

2. Forgetting Negative Signs

During P - Q, every coefficient of Q must be subtracted.

3. Multiplying Exponents

x² × x³ = x⁵, not x⁶. Add the exponents.

4. Keeping Zero Terms

Terms with zero coefficients should be removed from the compact representation.

5. Losing Sorted Order

Addition and subtraction algorithms expect terms in descending exponent order.

6. Forgetting NULL

The last node of a normal polynomial Singly Linked List must point to NULL.

Important Exam Questions With Answers

2 Marks

Q1. What are Polynomial Operations Using Linked List?

Polynomial Operations Using Linked List are methods of performing mathematical operations on polynomial terms stored in connected nodes. Common operations are addition, subtraction and multiplication.

2 Marks

Q2. What is Polynomial Addition?

Polynomial Addition is the process of combining two polynomials by adding coefficients of terms with equal exponents.

2 Marks

Q3. What is the rule for Polynomial Multiplication?

Multiply the coefficients of two terms and add their exponents. After multiplication, combine the terms having equal exponents.

2 Marks

Q4. What is the time complexity of Polynomial Addition?

The time complexity is O(m + n) when the two polynomial Linked Lists are sorted and processed using the merge algorithm.

5 Marks

Q5. Explain Polynomial Addition Using Linked List.

Polynomial Addition using Linked List is performed by comparing the exponents of terms stored in two sorted polynomial lists.

  1. Start from HEAD of both lists.
  2. Compare the exponents of current nodes.
  3. If exponents are equal, add coefficients.
  4. If they differ, copy the higher exponent term.
  5. Move the appropriate pointers forward.
  6. Append the remaining terms.

If the sum of two coefficients becomes zero, skip that term. The result is another polynomial Linked List.

5 Marks

Q6. Explain Polynomial Subtraction Using Linked List.

Polynomial Subtraction can be performed by subtracting coefficients of equal-exponent terms.

An alternative way is to reverse the signs of the second polynomial and apply polynomial addition.

P(x) - Q(x) = P(x) + [-Q(x)]

The resulting nodes are stored in descending exponent order. The operation takes O(m + n) time for sorted lists.

5 Marks

Q7. Explain Polynomial Multiplication Using Linked List.

Polynomial Multiplication is performed by multiplying every term of the first polynomial with every term of the second polynomial.

  1. Select one node of the first list.
  2. Multiply it with every node of the second list.
  3. Multiply coefficients.
  4. Add exponents.
  5. Insert the product into the result.
  6. Combine terms with equal exponents.
  7. Repeat until all term pairs are processed.

The final result is stored as a polynomial Linked List.

10 Marks

Q8. Explain Polynomial Operations Using Linked List With Algorithms and Examples.

A polynomial Linked List stores each non-zero polynomial term inside a node containing a coefficient, exponent and next pointer.

Node = Coefficient | Exponent | Next

1. Polynomial Addition

Addition compares the current exponents of two sorted lists. Equal exponents have their coefficients added, and unmatched terms are copied.

2. Polynomial Subtraction

Subtraction follows a similar process, but coefficients of the second polynomial are subtracted from the first.

3. Polynomial Multiplication

Every term of the first list is multiplied by every term of the second list.

Coefficients are multiplied, exponents are added, and like terms are combined.

Advantages

  • Dynamic memory allocation.
  • Useful storage for sparse polynomials.
  • Flexible result-list creation.
  • Efficient addition and subtraction of sorted lists.

Limitations

  • Extra memory for pointers.
  • Sequential node access.
  • Complexity of pointer management.

Conclusion: Linked Lists provide a flexible way to represent and process polynomial expressions, especially when the polynomial contains relatively few non-zero terms.

Practice Questions With Answers

Practice 01

Add the following polynomials.

P(x) = 2x² + 3x + 1
Q(x) = 4x² + 2x + 5

Show Answer

P(x) + Q(x) = 6x² + 5x + 6

Practice 02

Subtract the following polynomials.

P(x) = 5x² + 4x + 7
Q(x) = 2x² + 3x + 2

Show Answer

P(x) - Q(x) = 3x² + x + 5

Practice 03

Multiply the following polynomials.

A(x) = x + 2
B(x) = x + 3

Show Answer

A(x) × B(x) = x² + 5x + 6

Practice 04

What happens when like terms cancel during addition?

Show Answer

Their coefficient becomes zero. The term is omitted from the compact result Linked List.

Quick Revision Before Semester Exam

Remember these rules to answer Polynomial Operations questions quickly and correctly.

Polynomial Node

Coefficient + Exponent + Next

Addition

Same exponent, add coefficients.

Subtraction

Reverse Q signs, then add.

Multiplication

Multiply coefficients, add exponents.

Zero Coefficients

Skip zero-result terms.

Node Order

Descending exponents.

Addition Complexity

O(m + n) for sorted lists.

Subtraction Complexity

O(m + n) for sorted lists.

Frequently Asked Questions

What are the main Polynomial Operations Using Linked List?

The main operations are polynomial addition, subtraction and multiplication. They are performed using polynomial terms stored in connected nodes.

How is Polynomial Addition performed using Linked List?

Compare the exponents of two sorted polynomial lists. If the exponents are equal, add the coefficients. Otherwise, copy the higher exponent term into the result.

How is Polynomial Subtraction different from Addition?

Addition combines coefficients by adding them, while subtraction subtracts coefficients. Subtraction can also be done by changing the signs of the second polynomial and then adding.

What is the rule for Polynomial Multiplication?

Multiply coefficients and add exponents for every pair of terms. Then combine products that have the same exponent.

What happens if a result coefficient becomes zero?

The zero term can be omitted from the polynomial Linked List because it does not contribute to the mathematical expression.

Why is descending exponent order important?

It allows two polynomial Linked Lists to be compared and merged efficiently during addition and subtraction.

Can Polynomial Operations be implemented in C?

Yes. C structures and pointers can be used to create polynomial nodes and implement addition, subtraction and multiplication.

Conclusion

Polynomial Operations Using Linked List become much easier when we understand how the coefficients and exponents are handled during each operation.

In addition, we combine coefficients having the same exponent. In subtraction, we subtract coefficients or reverse the signs of the second polynomial before adding.

In multiplication, we multiply every pair of terms, add their exponents and combine like terms.

For exams, remember this simple rule: Add means add coefficients, subtract means change signs, and multiply means multiply coefficients and add powers.

Once these rules are clear, polynomial algorithms, dry runs and C programs become much easier to understand and write.

Tags

Post a Comment

0 Comments
* Please Don't Spam Here. All the Comments are Reviewed by Admin.
Join Telegram Exam updates and free resources