Polynomial Representation Using Linked List in Data Structure With Examples
Understand how a polynomial is stored using Linked List nodes, with pictorial diagrams, step-by-step examples, polynomial addition, multiplication, C programs and exam-ready notes.
Polynomials are familiar to students because we study expressions such as 3x³ + 2x² + 5 in Mathematics. But when the same topic appears in Data Structure, many students become confused.
The main question is simple: how can we store a mathematical polynomial inside a Linked List? And how can we add or multiply two polynomials using these nodes?
The concept becomes easier when we understand that every term contains a coefficient and an exponent. We can store both values inside a Linked List node and connect the terms using pointers.
If you want to revise the basic structure of nodes and pointers, first understand Linked List in Data Structure: Types, Operations and Examples .
What is a Polynomial in Data Structure?

A polynomial is a mathematical expression consisting of one or more terms. Each term normally contains a coefficient and a non-negative integer exponent of a variable.
In this expression, there are three non-zero terms:
| Term | Coefficient | Exponent |
|---|---|---|
| 3x³ | 3 | 3 |
| 2x² | 2 | 2 |
| 5 | 5 | 0 |
The constant term 5 has exponent 0 because x raised to power 0 is equal to 1.
Important Terminology
Coefficient
The numerical value multiplying the variable.
Exponent
The power of the variable in a particular term.
Degree
The highest exponent with a non-zero coefficient.
Why Do We Need Linked List for Polynomial Representation?
A polynomial can be stored using an array, but arrays may reserve positions for zero coefficients that are not useful.
Suppose we have:
This polynomial contains only three non-zero terms, but a normal dense coefficient array covering powers from 0 to 100 needs 101 positions.
A Linked List can represent the polynomial using only three term nodes.
101 Positions
Stores coefficients for powers 0 to 100, including the zero coefficients.
3 Term Nodes
Stores only the three non-zero terms, together with their exponents and links.
Polynomial Representation Using Linked List
In Linked List representation, every non-zero polynomial term is stored in a separate node.
A node generally contains three fields:
Coefficient
Stores the numerical value of the term.
Exponent
Stores the power of the variable.
Next Pointer
Stores the address of the next node.
Pictorial Representation of Polynomial
Let us represent the following polynomial:
Explanation of the Diagram
Coefficient = 3 and exponent = 3. Therefore, it represents 3x³.
Coefficient = 2 and exponent = 2. Therefore, it represents 2x².
Coefficient = 5 and exponent = 0. Therefore, it represents constant 5.
The final node points to NULL, indicating the end of the list.
Why Do We Arrange Exponents in Descending Order?
Polynomial nodes are commonly arranged from the highest exponent to the lowest.
When two polynomials follow this order, we can compare their terms step by step. This makes polynomial addition efficient because equal exponents can be combined during a single traversal.
How to Create a Polynomial Using Linked List
Creating a polynomial Linked List means converting every non-zero term into a node and joining the nodes in the correct order.
Steps to Create a Polynomial Linked List
Identify all terms and their coefficients and exponents.
A term with coefficient zero need not occupy a node.
Store each term's coefficient and exponent in a new node.
Maintain descending exponent order. Combine terms if their exponents are the same.
Link every node to the next node and set the last pointer to NULL.
Example: Creating Nodes
Consider:
| Node | Coefficient | Exponent |
|---|---|---|
| Node 1 | 4 | 4 |
| Node 2 | 3 | 2 |
| Node 3 | 7 | 0 |
The completed Linked List stores:
Each pair represents (Coefficient, Exponent).
Pseudocode for Polynomial Traversal
START
PTR = HEAD
WHILE PTR != NULL
PRINT PTR.coefficient
PRINT PTR.exponent
PTR = PTR.next
END WHILE
STOP
Traversal visits one node at a time and processes every polynomial term. For n nodes, traversal takes O(n) time.
Polynomial Addition Using Linked List
Polynomial Addition means adding two polynomial expressions by combining terms that have the same exponent.
A Linked List makes this operation easier when the nodes of both polynomials are arranged in descending exponent order.
Solved Example: Addition of Two Polynomials
Suppose we have:
We have to calculate:
Step-by-Step Dry Run
P contains 3x³ and Q contains 2x². Since exponent 3 is greater than 2, copy 3x³ to the result.
P contains 2x² and Q contains 2x². Exponents are equal, so add the coefficients: 2 + 2 = 4. The result contains 4x².
Q contains 4x, while P has no x term. Copy 4x into the result.
P contains 5 and Q contains 1. Add 5 + 1 = 6.
| Exponent | P Coefficient | Q Coefficient | Result |
|---|---|---|---|
| 3 | 3 | 0 | 3x³ |
| 2 | 2 | 2 | 4x² |
| 1 | 0 | 4 | 4x |
| 0 | 5 | 1 | 6 |
Linked List Representation of the Result
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(SUM, P.exp)
END IF
P = P.next
Q = Q.next
ELSE IF P.exp > Q.exp
APPEND(P.coeff, P.exp)
P = P.next
ELSE
APPEND(Q.coeff, Q.exp)
Q = Q.next
END IF
END WHILE
APPEND remaining terms of P
APPEND remaining terms of Q
RETURN RESULT
STOP
Time Complexity of Polynomial Addition
If the first Linked List contains m terms and the second contains n terms, each node is processed once when the lists are already sorted by exponent.
A separate result list may require O(m + n) additional node storage in the worst case.
Polynomial Multiplication Using Linked List
Polynomial Multiplication is slightly more difficult than addition because every term of the first polynomial must be multiplied by every term of the second polynomial.
After multiplication, terms with equal exponents are combined.
Rules of Polynomial Multiplication
Multiply Coefficients
Multiply the numerical values of both terms.
Add Exponents
Add powers when multiplying terms of the same variable.
Example of Polynomial Multiplication
Take the same two polynomials:
We have to find:
Step 1: Multiply Every Term
| Term From P | Term From Q | Product |
|---|---|---|
| 3x³ | 2x² | 6x⁵ |
| 3x³ | 4x | 12x⁴ |
| 3x³ | 1 | 3x³ |
| 2x² | 2x² | 4x⁴ |
| 2x² | 4x | 8x³ |
| 2x² | 1 | 2x² |
| 5 | 2x² | 10x² |
| 5 | 4x | 20x |
| 5 | 1 | 5 |
Step 2: Combine Like Terms
Now group the terms that contain equal exponents.
6x⁵
Only one term.
16x⁴
12x⁴ + 4x⁴ = 16x⁴
11x³
3x³ + 8x³ = 11x³
12x²
2x² + 10x² = 12x²
20x
Only one term.
5
Constant term.
Step 3: Write the Final Polynomial
Linked List Representation of the Product
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
Polynomial Representation Using Linked List in C
In C programming, we can represent each polynomial term using a structure containing a coefficient, exponent and next pointer.
Structure of a Polynomial Node
struct Node {
long long coeff;
int exp;
struct Node *next;
};
Here, coeff stores the
coefficient, exp stores
the exponent and next
points to the next polynomial term.
Complete C Program: Addition and Multiplication
The following program creates two polynomial Linked Lists, adds them and multiplies them. It also combines terms with equal exponents, skips zero terms and releases allocated memory.
#include <stdio.h>
#include <stdlib.h>
struct Node {
long long coeff;
int exp;
struct Node *next;
};
typedef struct Node Node;
Node *createNode(long long c, int e) {
Node *p = malloc(sizeof *p);
if (p == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
p->coeff = c;
p->exp = e;
p->next = NULL;
return p;
}
void insertTerm(Node **head, long long c, int e) {
if (c == 0) {
return;
}
Node **cur = head;
while (*cur != NULL && (*cur)->exp > e) {
cur = &(*cur)->next;
}
if (*cur != NULL && (*cur)->exp == e) {
(*cur)->coeff += c;
if ((*cur)->coeff == 0) {
Node *old = *cur;
*cur = old->next;
free(old);
}
return;
}
Node *p = createNode(c, e);
p->next = *cur;
*cur = p;
}
void appendTerm(Node **head, Node **tail,
long long c, int e) {
if (c == 0) {
return;
}
Node *p = createNode(c, e);
if (*head == NULL) {
*head = p;
} else {
(*tail)->next = p;
}
*tail = p;
}
Node *addPoly(const Node *a, const Node *b) {
Node *result = NULL;
Node *tail = NULL;
while (a != NULL && b != NULL) {
if (a->exp == b->exp) {
appendTerm(&result, &tail,
a->coeff + b->coeff,
a->exp);
a = a->next;
b = b->next;
} else if (a->exp > b->exp) {
appendTerm(&result, &tail,
a->coeff, a->exp);
a = a->next;
} else {
appendTerm(&result, &tail,
b->coeff, b->exp);
b = b->next;
}
}
while (a != NULL) {
appendTerm(&result, &tail,
a->coeff, a->exp);
a = a->next;
}
while (b != NULL) {
appendTerm(&result, &tail,
b->coeff, b->exp);
b = b->next;
}
return result;
}
Node *multiplyPoly(const Node *a, const Node *b) {
Node *result = NULL;
for (const Node *p = a; p != NULL; p = p->next) {
for (const Node *q = b; q != NULL; q = q->next) {
insertTerm(&result,
p->coeff * q->coeff,
p->exp + q->exp);
}
}
return result;
}
void printPoly(const Node *p) {
if (p == NULL) {
printf("0\n");
return;
}
int first = 1;
while (p != NULL) {
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;
}
printf("\n");
}
void freePoly(Node *p) {
while (p != NULL) {
Node *next = p->next;
free(p);
p = next;
}
}
int main(void) {
Node *p = NULL;
Node *q = NULL;
insertTerm(&p, 3, 3);
insertTerm(&p, 2, 2);
insertTerm(&p, 5, 0);
insertTerm(&q, 2, 2);
insertTerm(&q, 4, 1);
insertTerm(&q, 1, 0);
Node *sum = addPoly(p, q);
Node *product = multiplyPoly(p, q);
printf("P(x) = ");
printPoly(p);
printf("Q(x) = ");
printPoly(q);
printf("Addition = ");
printPoly(sum);
printf("Multiplication = ");
printPoly(product);
freePoly(p);
freePoly(q);
freePoly(sum);
freePoly(product);
return 0;
}
Expected Output
P(x) = 3x^3 + 2x^2 + 5
Q(x) = 2x^2 + 4x + 1
Addition = 3x^3 + 4x^2 + 4x + 6
Multiplication = 6x^5 + 16x^4 + 11x^3 + 12x^2 + 20x + 5
Explanation of the Program
Allocates memory for a polynomial term and stores its coefficient and exponent.
Inserts terms in descending exponent order. If an exponent already exists, it combines the coefficients.
Compares exponents of two sorted Linked Lists and creates the sum using the appropriate terms.
Multiplies every term of the first polynomial by every term of the second polynomial.
Releases the dynamically allocated nodes to avoid memory leaks.
Array vs Linked List Representation of Polynomial
Both arrays and Linked Lists can store polynomial expressions, but they use different storage methods.
| Feature | Array Representation | Linked List Representation |
|---|---|---|
| Storage | Indexed coefficient positions | Connected term nodes |
| Zero Terms | Dense arrays store zero coefficients | Zero terms can be omitted |
| Memory | Can be efficient for dense polynomials | Often useful for sparse polynomials |
| Size | Depends on allocated array capacity | Can grow dynamically |
| Random Access | Direct index access | Sequential node traversal |
| Extra Fields | Index often indicates exponent | Stores exponent and next pointer |
| Updating Terms | Efficient when array index exists | May require searching for exponent |
| Best Use | Many non-zero terms across a manageable degree | Few non-zero terms across widely separated powers |
This concept is related to how we store only useful data in a Sparse Matrix in Data Structure . Both topics demonstrate why storage representation matters.
Time Complexity of Polynomial Linked List Operations
Complexity depends on the number of stored terms and the way nodes are inserted, searched or combined.
| Operation | Time Complexity | Explanation |
|---|---|---|
| Traverse Polynomial | O(n) | Visit all stored terms |
| Search Exponent | O(n) | May inspect every node |
| Insert at Head | O(1) | When insertion position is valid |
| Sorted Insert | O(n) | May search for proper position |
| Polynomial Addition | O(m + n) | Merge two sorted lists |
| Generate Multiplication Pairs | O(mn) | Multiply every pair of terms |
| Multiplication With Sorted Insertion | O(mnr) | Each product may scan up to r result terms |
Here, m and n are the number of terms in the input polynomials, while r is the maximum number of stored result terms during multiplication.
The multiplication time shown applies to the simple sorted-insertion C implementation in this chapter. Other multiplication implementations can use different accumulation methods and have different complexity.
Space Complexity
Polynomial Addition
Worst-case additional node storage when creating a separate result.
Polynomial Multiplication
Additional storage for distinct non-zero terms in the result.
Advantages of Polynomial Representation Using Linked List
1. Dynamic Storage
New polynomial terms can be inserted without requiring a fixed-size coefficient array.
2. Sparse Storage
Only non-zero terms need to be stored, reducing unnecessary zero entries in sparse cases.
3. Flexible Operations
Polynomial terms can be inserted, removed and combined using pointer operations.
4. Efficient Addition
Two sorted polynomial lists can be added in O(m + n) time using a merge-style algorithm.
Disadvantages of Polynomial Linked List
- Every node needs extra space for a next pointer.
- Nodes may require separate memory allocations.
- Searching for an exponent can take O(n) time.
- Pointer handling makes the implementation more complex.
- Linked List traversal may have poor cache locality compared with arrays.
- A dense polynomial may be better stored using a normal coefficient array.
Applications of Polynomial Linked List
Polynomial Linked Lists are mainly useful for representing and manipulating symbolic expressions, especially when many powers have zero coefficients.
Symbolic Mathematics
Expressions can be stored as terms and manipulated using addition, multiplication or simplification.
Educational Algebra Systems
Polynomial nodes help demonstrate algebraic operations through programming and data structures.
Sparse Expressions
Expressions with high degrees and very few non-zero terms can use compact term-based storage.
Expression Processing
Term-based structures help explain how symbolic expressions can be organised before mathematical processing.
Common Mistakes Students Make
1. Adding Different Exponents
During polynomial addition, only coefficients of equal exponents can be combined.
2. Multiplying Powers Incorrectly
When multiplying x³ and x², add exponents to get x⁵. Do not multiply the exponents.
3. Ignoring Constant Exponent
The constant term 5 must be represented using exponent 0.
4. Forgetting Sorted Order
The merge-style addition algorithm requires both polynomial lists to be sorted consistently.
5. Keeping Duplicate Exponents
Terms with equal exponents should be combined in the normalised representation.
6. Forgetting Memory Release
Nodes created dynamically in C must be released using free() when no longer required.
Memory Tricks for Semester Exams
C E N
C = Coefficient
E = Exponent
N = Next Pointer
Add vs Multiply
Add: Equal exponent,
add coefficients.
Multiply: Multiply
coefficients, add exponents.
Important Exam Questions With Answers
Q1. What is Polynomial Representation Using Linked List?
Polynomial Representation Using Linked List is a method of storing polynomial terms in connected nodes. Each node contains a coefficient, exponent and a pointer to the next node.
Q2. What are the fields of a polynomial node?
A polynomial Linked List node contains three fields: coefficient, exponent and next pointer.
Q3. Why are polynomial terms arranged in descending exponent order?
Descending exponent order makes polynomial traversal and addition easier. Equal exponents can be identified and combined efficiently.
Q4. Explain Polynomial Representation Using Linked List With Example.
Polynomial Representation Using Linked List is a method in which each non-zero polynomial term is stored in a separate node.
Every node contains three fields: coefficient, exponent and next pointer. The nodes are generally arranged in descending exponent order.
Consider the polynomial:
Its Linked List representation is:
The first value in each pair is the coefficient, while the second value is the exponent.
This representation supports dynamic storage and can avoid storing zero-coefficient terms.
Q5. Explain Polynomial Addition Using Linked List.
Polynomial Addition using Linked List is performed by comparing the exponents of two polynomial lists.
- Start from the HEAD of both lists.
- Compare exponents of current nodes.
- If equal, add coefficients.
- If unequal, copy the higher exponent term.
- Move the appropriate pointers forward.
- Append remaining terms when one list finishes.
When the input lists are sorted, the algorithm takes O(m + n) time for m and n terms.
Q6. Explain Polynomial Representation Using Linked List and Its Operations.
A polynomial is a mathematical expression containing terms with coefficients and non-negative integer exponents.
In Linked List representation, every non-zero term is stored in a node containing a coefficient, exponent and next pointer.
Structure of a Node
Example
For P(x) = 3x³ + 2x² + 5:
Polynomial Addition
Two sorted polynomial lists are traversed. Terms with equal exponents have their coefficients added. Other terms are copied to the result in the correct order.
Polynomial Multiplication
Every term of the first polynomial is multiplied by every term of the second polynomial. Coefficients are multiplied, exponents are added, and like terms are combined.
Advantages
- Dynamic storage of polynomial terms.
- Zero-coefficient terms can be omitted.
- Flexible insertion and deletion.
- Efficient addition of sorted polynomial lists.
Disadvantages
- Extra memory is required for pointers.
- Sequential access is needed.
- Pointer operations require careful handling.
Conclusion: Linked List representation is useful for storing and processing polynomials, especially sparse polynomial expressions. Its main operations include creation, traversal, addition and multiplication.
Practice Questions for Students
Represent the following polynomial using Linked List.
Show Answer
(5,4) → (3,2) → (8,0) → NULL
Add the following polynomials.
P(x) = 2x² + 3x + 1
Q(x) = 4x² + 2x + 5
Show Answer
P(x) + Q(x) = 6x² + 5x + 6
Multiply the following polynomials.
P(x) = x + 2
Q(x) = x + 3
Show Answer
(x + 2)(x + 3) = x² + 5x + 6
What happens if two equal-exponent terms add up to zero?
Show Answer
The resulting coefficient becomes zero. In a compact polynomial Linked List, that term should be omitted or removed.
Quick Revision Before Exam
Remember these important points before attempting semester exam questions.
Coefficient + Exponent + Next
Points to the first polynomial term.
Next pointer contains NULL.
Usually descending exponent order.
Combine coefficients of equal exponents.
Multiply coefficients and add exponents.
O(n) for n stored terms.
O(m + n) for two lists.
Frequently Asked Questions
What is Polynomial Representation Using Linked List?
It is a method of storing polynomial terms as connected nodes. Every node contains a coefficient, exponent and next pointer.
How many fields are stored in a polynomial node?
A basic polynomial node contains three fields: coefficient, exponent and a pointer to the next node.
Why is Linked List useful for sparse polynomials?
A sparse polynomial contains relatively few non-zero terms. Linked Lists can store only these terms without reserving positions for every missing exponent.
What is the time complexity of Polynomial Addition?
Polynomial addition takes O(m + n) time when both lists are already sorted and a merge-style algorithm is used.
Can polynomial multiplication be implemented using Linked List?
Yes. Every term of the first list is multiplied by each term of the second. Terms with equal resulting exponents are combined into the result list.
Which is better for a polynomial: Array or Linked List?
Arrays are often suitable for dense polynomials, while Linked Lists can be useful for sparse expressions and dynamically changing terms. The better choice depends on the operations and storage requirements.
Conclusion
Polynomial Representation Using Linked List becomes easy when we remember that every polynomial term can be stored as a node containing its coefficient, exponent and next pointer.
Linked Lists can avoid unnecessary zero-coefficient terms and make it possible to manipulate sparse polynomials using dynamically connected nodes.
For polynomial addition, compare exponents and combine coefficients when the powers are equal.
For polynomial multiplication, multiply coefficients, add exponents and combine like terms.
Final Memory Trick: Addition means same exponent, add coefficients. Multiplication means multiply coefficients, add exponents.
Once you understand these two rules and the three fields of a polynomial node, most university exam questions on this topic become much easier to solve and explain.
