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 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.
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 mean performing mathematical calculations on polynomial expressions stored inside Linked Lists.
The three most important operations for Data Structure exams are:
Addition
Add the coefficients of terms with equal exponents.
Subtraction
Subtract coefficients of terms with equal exponents.
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.
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.
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.
Rules of Polynomial Addition
Equal Exponents
Add the coefficients and keep the same exponent.
Different Exponents
Do not combine these terms. Keep both in the result.
Solved Example: Addition
Consider the following polynomials:
We have to calculate P(x) + Q(x).
Step-by-Step Dry Run
P contains 4x⁴ and Q has no x⁴ term. Copy 4x⁴ to the result.
Q contains 2x³ and P has no x³ term. Copy 2x³ to the result.
P contains 3x² and Q contains -3x². Their sum is zero, so this term is not included.
P contains -2x and Q contains 2x. Their sum is zero, so skip this term.
P contains 5 and Q contains -5. Adding them gives zero.
Addition Dry Run Table
| Exponent | P Coefficient | Q Coefficient | Sum |
|---|---|---|---|
| 4 | 4 | 0 | 4 |
| 3 | 0 | 2 | 2 |
| 2 | 3 | -3 | 0 |
| 1 | -2 | 2 | 0 |
| 0 | 5 | -5 | 0 |
Linked List Diagram After Addition
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.
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.
Easy Rule for Polynomial Subtraction
This means subtraction can be understood as addition after reversing the signs of Q.
Solved Example: Subtraction
Take the same polynomials:
We need to find P(x) - Q(x).
Step 1: Change Signs of Q
Original Q(x):
Negative of Q(x):
Step 2: Add P and -Q
| Exponent | P Coefficient | Q Coefficient | P - Q |
|---|---|---|---|
| 4 | 4 | 0 | 4 |
| 3 | 0 | 2 | -2 |
| 2 | 3 | -3 | 6 |
| 1 | -2 | 2 | -4 |
| 0 | 5 | -5 | 10 |
Step-by-Step Explanation
4 - 0 = 4, so the result contains 4x⁴.
0 - 2 = -2, so the result contains -2x³.
3 - (-3) = 6, so the result contains 6x².
-2 - 2 = -4, so the result contains -4x.
5 - (-5) = 10, so the result contains constant 10.
Result Linked List
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
Time Complexity of Subtraction
Just like addition, we compare and process each node once when both input lists are sorted.
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.
Two Important Multiplication Rules
Multiply Coefficients
Multiply the numerical values of the two terms.
Add Exponents
When the variable is the same, add the exponents.
Solved Example: Multiplication
For an easy dry run, take two smaller polynomials:
We have to calculate A(x) × B(x).
Step 1: Multiply Every Term of A by x
Step 2: Multiply Every Term of A by 2
Step 3: Combine Like Terms
| Term from A | Term from B | Product |
|---|---|---|
| 2x² | x | 2x³ |
| 2x² | 2 | 4x² |
| 3x | x | 3x² |
| 3x | 2 | 6x |
| 1 | x | x |
| 1 | 2 | 2 |
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.
Result Linked List Diagram
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?
Start with 2x².
Create 2x³ and 4x².
Multiply 3x by both terms of B. Add products to the result.
Combine 4x² and 3x² into one 7x² node.
Continue until all pairs are processed. Keep the result in descending exponent order.
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.
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
Coefficients are added. Exponent stays 1.
Coefficients are subtracted. Exponent stays 1.
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.
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
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.
Q2. What is Polynomial Addition?
Polynomial Addition is the process of combining two polynomials by adding coefficients of terms with equal exponents.
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.
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.
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.
- Start from HEAD of both lists.
- Compare the exponents of current nodes.
- If exponents are equal, add coefficients.
- If they differ, copy the higher exponent term.
- Move the appropriate pointers forward.
- Append the remaining terms.
If the sum of two coefficients becomes zero, skip that term. The result is another polynomial Linked List.
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.
The resulting nodes are stored in descending exponent order. The operation takes O(m + n) time for sorted lists.
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.
- Select one node of the first list.
- Multiply it with every node of the second list.
- Multiply coefficients.
- Add exponents.
- Insert the product into the result.
- Combine terms with equal exponents.
- Repeat until all term pairs are processed.
The final result is stored as a polynomial Linked List.
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.
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
Add the following polynomials.
P(x) = 2x² + 3x + 1
Q(x) = 4x² + 2x + 5
Show Answer
P(x) + Q(x) = 6x² + 5x + 6
Subtract the following polynomials.
P(x) = 5x² + 4x + 7
Q(x) = 2x² + 3x + 2
Show Answer
P(x) - Q(x) = 3x² + x + 5
Multiply the following polynomials.
A(x) = x + 2
B(x) = x + 3
Show Answer
A(x) × B(x) = x² + 5x + 6
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.
Coefficient + Exponent + Next
Same exponent, add coefficients.
Reverse Q signs, then add.
Multiply coefficients, add exponents.
Skip zero-result terms.
Descending exponents.
O(m + n) for sorted lists.
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.
