In the context of B.Tech Data Structures Notes 2025, representing a polynomial using arrays is often considered the simplest approach. However, this approach has limitations, especially when dealing with sparse polynomials or operations like insertion and deletion of terms. A more efficient and dynamic method for representing polynomials is through Linked Lists. In this chapter of Unit 2 Notes Data Structures, we will explore the intricacies of polynomial representation using linked lists in a detailed manner to serve as a comprehensive Engineering Study Material. This chapter is available for Free Download PDF for students seeking structured knowledge.
Definition and Need for Polynomial Representation
A polynomial is a mathematical expression consisting of variables (also known as indeterminates), coefficients, and non-negative integer exponents. For example:
P(x) = 6x^5 + 2x^3 – 4x + 7
This expression has terms with varying degrees. Representing such a polynomial in a program requires storage of the coefficient and exponent of each term. While arrays can be used, they are inefficient for sparse polynomials, as they waste memory for zero coefficients. A Linked List provides a more memory-efficient alternative.
Why Use Linked Lists for Polynomial Representation?
- Linked Lists allow dynamic memory allocation, which means no pre-defined size is needed.
- Insertion and deletion of terms are more efficient, especially in sorted order.
- Sparse polynomials with large gaps in exponent values are handled without wasting memory.
- Operations like addition, subtraction, and multiplication are easier to implement modularly using linked list traversal.
Structure of a Polynomial Term Node
Each node in a polynomial-linked list represents a term in the polynomial and contains the following:
- Coefficient (int or float)
- Exponent (int)
- Pointer to the next term (next)
In C-style pseudo-code:
struct PolyNode {
int coefficient;
int exponent;
struct PolyNode* next;
};This structure allows the storage of any polynomial in descending or ascending order of exponents.
Creating a Polynomial Linked List
To create a polynomial, we create multiple nodes for each term and link them. A utility function to insert nodes can be written as:
struct PolyNode* insertTerm(struct PolyNode* head, int coeff, int expo) {
struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
newNode->coefficient = coeff;
newNode->exponent = expo;
newNode->next = NULL;
if (head == NULL || expo > head->exponent) {
newNode->next = head;
head = newNode;
} else {
struct PolyNode* current = head;
while (current->next != NULL && current->next->exponent > expo) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
return head;
}Displaying a Polynomial
To display a polynomial stored in a linked list:
void displayPolynomial(struct PolyNode* head) {
struct PolyNode* current = head;
while (current != NULL) {
printf("%dx^%d", current->coefficient, current->exponent);
if (current->next != NULL && current->next->coefficient >= 0)
printf(" + ");
current = current->next;
}
printf("\n");
}Addition of Two Polynomials Using Linked List
To add two polynomials represented by linked lists:
struct PolyNode* addPolynomials(struct PolyNode* p1, struct PolyNode* p2) {
struct PolyNode* result = NULL;
while (p1 != NULL && p2 != NULL) {
if (p1->exponent == p2->exponent) {
result = insertTerm(result, p1->coefficient + p2->coefficient, p1->exponent);
p1 = p1->next;
p2 = p2->next;
} else if (p1->exponent > p2->exponent) {
result = insertTerm(result, p1->coefficient, p1->exponent);
p1 = p1->next;
} else {
result = insertTerm(result, p2->coefficient, p2->exponent);
p2 = p2->next;
}
}
while (p1 != NULL) {
result = insertTerm(result, p1->coefficient, p1->exponent);
p1 = p1->next;
}
while (p2 != NULL) {
result = insertTerm(result, p2->coefficient, p2->exponent);
p2 = p2->next;
}
return result;
}Insert diagram here for Polynomial Addition Step-by-Step Traversal
Multiplication of Two Polynomials Using Linked List
Polynomial multiplication involves multiplying each term of one polynomial with every term of the other.
struct PolyNode* multiplyPolynomials(struct PolyNode* p1, struct PolyNode* p2) {
struct PolyNode* result = NULL;
for (struct PolyNode* ptr1 = p1; ptr1 != NULL; ptr1 = ptr1->next) {
for (struct PolyNode* ptr2 = p2; ptr2 != NULL; ptr2 = ptr2->next) {
int coeff = ptr1->coefficient * ptr2->coefficient;
int expo = ptr1->exponent + ptr2->exponent;
result = insertTerm(result, coeff, expo);
}
}
return result;
}Insert diagram here for Term-by-Term Polynomial Multiplication
Comparison: Arrays vs Linked Lists for Polynomial Representation
| Criteria | Arrays | Linked Lists |
|---|---|---|
| Memory Usage | Fixed, wasteful for sparse | Dynamic, efficient |
| Insertion | Expensive (shifting) | Efficient |
| Deletion | Expensive | Easy |
| Traversal | Fast | Slower |
| Flexibility | Low | High |
Key Points
- Linked List is ideal for sparse polynomials.
- Each node represents one term with coefficient and exponent.
- Insertion keeps polynomial sorted for easy operations.
- Addition and Multiplication are modular and manageable using traversal.
Short Answer Questions (2-3 marks)
Q1. Define polynomial. A polynomial is a mathematical expression comprising coefficients and variables raised to non-negative integer exponents, e.g., 5x^3 + 2x + 7.
Q2. Why is linked list preferred over array for polynomial representation? Because it uses dynamic memory, avoids memory wastage, and makes insertion/deletion efficient.
Q3. What does each node in a polynomial linked list contain? Each node contains a coefficient, exponent, and a pointer to the next term.
Q4. How are polynomials added using linked lists? By traversing both polynomials and adding terms with the same exponent.
Q5. What is the complexity of polynomial addition using linked list? It is O(m + n), where m and n are the number of terms in each polynomial.
Long Answer Questions (5-10 marks)
Q1. Explain how a polynomial is represented using linked list with suitable code. Polynomials are represented using nodes containing coefficient, exponent, and a pointer to the next node. The list is maintained in decreasing order of exponents. Code involves struct creation and insertion logic to maintain order.
Q2. Write an algorithm and C code to add two polynomials using linked lists. The algorithm involves traversing both lists, comparing exponents, adding when equal, or directly inserting the term otherwise. The result is stored in a new list. (Refer to code above in “Addition of Two Polynomials”)
Q3. Describe with code how multiplication of two polynomials is done using linked lists. Each term of the first polynomial is multiplied with every term of the second, and results are inserted into the result polynomial. This ensures all cross products are computed. (Refer to code above in “Multiplication of Two Polynomials”)
Q4. Compare arrays and linked lists in the context of polynomial representation. Arrays use contiguous memory and are inefficient for sparse polynomials. Linked lists are dynamic, reduce memory waste, and allow efficient term manipulation.
Q5. Discuss advantages of using linked lists for polynomial representation. Advantages include dynamic memory allocation, ease of insertion/deletion, support for sparse polynomials, and modular implementation of operations.
Chapter Summary
Polynomials are collections of terms with coefficients and exponentsLinked lists represent polynomials dynamicallyEach term is stored in a node with a pointer to the next nodeOperations like addition and multiplication are efficiently handled through traversalLinked lists are superior to arrays for sparse polynomialsInsertion functions maintain sorted order for simplicity of operationTraversal of linked lists supports modular implementation of algebraic operationsEfficient memory usage due to dynamic allocationCode in C-style pseudo-code enhances learning and implementation
Model Questions / Sample Internal Exam Questions
- Explain with code how to represent a polynomial using a linked list.
- Write an algorithm to add two polynomials using linked lists.
- How does polynomial multiplication differ from addition in linked list implementation?
- Compare and contrast array and linked list representation of polynomials.
- Write a C program to multiply two polynomials using linked lists.
