Last Updated on July 27, 2023 by Mayank Dham
Polynomial addition in c programming is a fundamental operation in mathematics and computer science, widely used in various applications such as signal processing, computer graphics, and scientific simulations. We will do the polynomial addition using linked list in C programming. When dealing with polynomials, it is essential to have an efficient and flexible data structure to represent and perform operations on them. Linked lists provide an elegant solution for efficiently handling polynomials due to their dynamic memory allocation and straightforward implementation.
In this article, we will delve into the concept of polynomial addition and explore how linked lists can be leveraged in C programming to perform this operation seamlessly. We will cover the fundamentals of linked lists and polynomial representation, along with step-by-step guidance on implementing the polynomial addition algorithm using linked lists. Additionally, we will discuss the advantages of using linked lists over other data structures for polynomial manipulation. Here we will learn about Polynomial Addition using Linked List in C.
What is Polynomial Addition using Linked List in C?
In this problem, we are given two polynomials represented by linked lists and are asked to add them. For example,
Input:
5x4 + 3x2 + 1
4x4 + 2x2 + xOutput:
9x4 + 5x2 + x + 1What is Polynomial Addition using Linked List in C?
Let us try to understand the above example:
Given List1 = 5×4 + 3×2 + 1 and List2 = 4×4 + 2×2 + x
- 5×4 and 4×4 are like terms, so we add their coefficients,
- Resultant list = 9×4
- 3×2 and 2×2 are like terms, so we add their coefficients.
- Resultant list = 9×4 + 5×2
- 1 and x are not like terms as x which is also x1 has a degree greater than 1 which is x0 so we append x to our resultant list.
- Resultant list = 9×4 + 5×2 + x
- 1 is left, so we append 1 to our resultant list.
- Resultant list = 9×4 + 5×2 + x + 1
Polynomial Addition using Linked List in C: Observations
Some helpful Observations which will aid us in performing the Polynomial Addition using Linked List in C are:
- We only added the coefficients of the like terms (terms having the same variables and the same degree).
- The terms are placed in descending order by degree.
So, we will use the above observations to design our algorithm.
Structure of Node
For, this particular problem, The linked list node contains three values:
- Coefficient: The numeric value.
- Degree: The power of the variable x.
- Address: The address of the next node of the linked list.
Naive Approach for Polynomial Addition using Linked List in C
To add two polynomials that are represented as a linked list, we will add the coefficients of variables with the degree.
We will traverse both the list and at any step, we will compare the degree of current nodes in both lists:
- We will add their coefficients if their degree is the same and append them to the resultant list.
- Otherwise, we will append the node with a greater node in the resultant list.
Algorithm for Performing the Polynomial Addition using Linked List in C
The algorithm for performing the Polynomial Addition using Linked List in C is given below:
- Create a new linked list, newHead to store the resultant list.
- Traverse both lists until one of them is null.
- If any list is null insert the remaining node of another list in the resultant list.
- Otherwise compare the degree of both nodes, a (first list’s node) and b (second list’s node). Here three cases are possible:
- If the degree of a and b is equal, we insert a new node in the resultant list with the coefficient equal to the sum of coefficients of a and b and the same degree.
- If the degree of a is greater than b, we insert a new node in the resultant list with the coefficient and degree equal to that of a.
- If the degree of b is greater than a, we insert a new node in the resultant list with the coefficient and degree equal to that of b.
Dry Run for Polynomial Addition using Linked List in C
Let the linked lists are:
List1 = 5×4 + 3×2 + 1
List2 = 4×4 + 2×2 + x
Note: For better understanding follow the code along with the dry run.
- First of all, we will initialize the resultant list which will contain the addition of the two given input polynomials in form of a linked list (Node newHead = new Node(0, 0)).
- We will create three-pointers a, b, and c and will make pointer a point to the head of List1, pointer b point to the head of List2, and pointer c point to the head of the resultant list newHead.
- As a(5×4) and b(4×4) are not null, so we enter the while loop (where a(5×4) means that pointer a is pointing to 5×4 in List1 and similarly b(4×4) means that pointer b is pointing to 4×4 in List2).
- As a.degree is equal to b.degree so c.next will be a + b i.e, 9×4.
- Move a, b, and c to their next pointers.
- Now, as a(3×2) and b(2×2) are still not null so we will be still in the while loop.
- As a.degree is still equal to b.degree so c.next will be a + b i.e, 5×2.
- Again move a, b, and c to their next pointers.
- a(1) and b(x) are still not null so we will be still in the while loop.
- As now a.degree is less than b.degree so c.next will point to the one with a higher degree, which is b(x).
- Again move b and c to their next pointers.
- But as now b is null so make the next of c points to a(1).
- Again move a and c to their next pointers.
- As now a and b both are null so we will exit the while loop.
Finally when we exit the while loop, newHead.next will contain the addition of the two given input polynomials in form of a linked list.
Code Implementation for Polynomial Addition using Linked List in C
Here is the code for Polynomial Addition using Linked List in C.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int coef;
int exp;
struct Node* next;
};
typedef struct Node Node;
void insert(Node** poly, int coef, int exp) {
Node* temp = (Node*) malloc(sizeof(Node));
temp->coef = coef;
temp->exp = exp;
temp->next = NULL;
if (*poly == NULL) {
*poly = temp;
return;
}
Node* current = *poly;
while (current->next != NULL) {
current = current->next;
}
current->next = temp;
}
void print(Node* poly) {
if (poly == NULL) {
printf("0\n");
return;
}
Node* current = poly;
while (current != NULL) {
printf("%dx^%d", current->coef, current->exp);
if (current->next != NULL) {
printf(" + ");
}
current = current->next;
}
printf("\n");
}
Node* add(Node* poly1, Node* poly2) {
Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->exp == poly2->exp) {
insert(&result, poly1->coef + poly2->coef, poly1->exp);
poly1 = poly1->next;
poly2 = poly2->next;
} else if (poly1->exp > poly2->exp) {
insert(&result, poly1->coef, poly1->exp);
poly1 = poly1->next;
} else {
insert(&result, poly2->coef, poly2->exp);
poly2 = poly2->next;
}
}
while (poly1 != NULL) {
insert(&result, poly1->coef, poly1->exp);
poly1 = poly1->next;
}
while (poly2 != NULL) {
insert(&result, poly2->coef, poly2->exp);
poly2 = poly2->next;
}
return result;
}
int main() {
Node* poly1 = NULL;
insert(&poly1, 5, 4);
insert(&poly1, 3, 2);
insert(&poly1, 1, 0);
Node* poly2 = NULL;
insert(&poly2, 4, 4);
insert(&poly2, 2, 2);
insert(&poly2, 1, 1);
printf("First polynomial: ");
print(poly1);
printf("Second polynomial: ");
print(poly2);
Node* result = add(poly1, poly2);
printf("Result: ");
print(result);
return 0;
}
Output
First polynomial: 5x^4 + 3x^2 + 1x^0
Second polynomial: 4x^4 + 2x^2 + 1x^1
Result: 9x^4 + 5x^2 + 1x^1 + 1x^0Time Complexity: O(m+n) is the time complexity for the polynomial addition using linked list in C, m and n being the size of the linked lists.
Space Complexity: O(m+n) is the space complexity for the polynomial addition using linked list in C, as in the worst case we need to allocate memory for each node in both lists.
Recursive Approach to perform Polynomial Addition using Linked List in C
We can also do Polynomial Addition using Linked List in C recursively. The algorithm for the recursive approach is given below.
- If either of the input linked lists is empty, return the other linked list.
- Otherwise, create a new node in the result linked list with the sum of the coefficients of the first terms of the two input linked lists, and the exponent of the first term of either linked list.
- Recursively call the add function with the next terms of the input linked lists, and the tail of the result linked list.
- Return the head of the result-linked list.
Code for Polynomial Addition using Linked List in C using Recursion
Here is the code for the algorithm explained above.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int coef;
int exp;
struct Node* next;
} Node;
void insert(Node** poly, int coef, int exp) {
Node* temp = (Node*) malloc(sizeof(Node));
temp->coef = coef;
temp->exp = exp;
temp->next = NULL;
if (*poly == NULL || (*poly)->exp < exp) {
temp->next = *poly;
*poly = temp;
} else {
Node* current = *poly;
while (current->next != NULL && current->next->exp >= exp) {
current = current->next;
}
temp->next = current->next;
current->next = temp;
}
}
void print(Node* poly) {
if (poly == NULL) {
printf("0\n");
return;
}
Node* current = poly;
while (current != NULL) {
printf("%dx^%d", current->coef, current->exp);
if (current->next != NULL) {
printf(" + ");
}
current = current->next;
}
printf("\n");
}
Node* add(Node* poly1, Node* poly2) {
if (poly1 == NULL) {
return poly2;
}
if (poly2 == NULL) {
return poly1;
}
Node* result = NULL;
if (poly1->exp == poly2->exp) {
result = (Node*) malloc(sizeof(Node));
result->coef = poly1->coef + poly2->coef;
result->exp = poly1->exp;
result->next = add(poly1->next, poly2->next);
} else if (poly1->exp > poly2->exp) {
result = (Node*) malloc(sizeof(Node));
result->coef = poly1->coef;
result->exp = poly1->exp;
result->next = add(poly1->next, poly2);
} else {
result = (Node*) malloc(sizeof(Node));
result->coef= poly2->coef;
result->exp = poly2->exp;
result->next = add(poly1, poly2->next);
}
return result;
}
int main() {
Node* poly1 = NULL;
Node* poly2 = NULL;
insert(&poly1, 1, 2);
insert(&poly1, 3, 1);
insert(&poly1, 2, 0);
printf("Poly 1: ");
print(poly1);
insert(&poly2, 4, 3);
insert(&poly2, 2, 1);
printf("Poly 2: ");
print(poly2);
Node* sum = add(poly1, poly2);
printf("Sum: ");
print(sum);
return 0;
}
Output:
Poly 1: 1x^2 + 3x^1 + 2x^0
Poly 2: 4x^3 + 2x^1
Sum: 4x^3 + 1x^2 + 5x^1 + 2x^0Time Complexity: O(m+n), m and n being the size of the linked lists.
Space Complexity: O(m+n), as in the worst case we need to allocate memory for each node in both lists.
Applications of Polynomial Addition using Linked List in C
Some of the Applications of Polynomial Addition using Linked List in C are given below.
- Polynomial Addition using Linked List in C can be used to solve mathematical problems which involves the addition and subtraction of polynomials.
- Can be used in Image Processing where the image is represented as a polynomial function.
Advantages of Polynomial Addition using Linked List in C
Performing Polynomial Addition using Linked List has the following advantages.
- Unlike arrays, linked lists can handle polynomials of any degree.
- Linked Lists can efficiently handle the storage and retrieval of polynomial coefficients and degrees.
- If we use Linked List, we can also perform Polynomial Addition recursively.
Disadvantages of Polynomial Addition using Linked List in C
The Polynomial Addition using Linked List in C also have some disadvantages which are listed below.
- The performance of Polynomial Addition using a Linked List is slower than arrays because of the overhead of linked list operations.
- Implementation of Polynomial Addition using Linked List is more complex.
- Polynomial Addition using Linked List also require more memory overhead than arrays as they need to store pointers and dynamic memory allocation.
Conclusion
In conclusion, polynomial addition using linked lists in C offers an elegant and efficient solution to handle mathematical operations on polynomials. By representing polynomials as linked lists, we can easily add, subtract, and manipulate them, making it a powerful tool for various applications in signal processing, computer graphics, and scientific simulations.
Throughout this article, we explored the fundamentals of linked lists and polynomial representation, guiding readers through the step-by-step process of implementing the polynomial addition algorithm in C. We witnessed the flexibility and simplicity of linked lists, allowing for dynamic memory allocation and straightforward traversal, which is crucial in dealing with polynomials of varying degrees.
Frequently Asked Questions (FAQs) on Polynomial addition using linked list in C.
Here are some Frequently Asked Questions on Polynomial Addition using Linked List in C.
1. What is polynomial addition using linked lists in C?
Polynomial addition using linked lists in C is a method to add two polynomials represented as linked lists, resulting in a new polynomial representing their sum.
2. How are polynomials represented as linked lists in C?
In linked list representation, each node of the list holds the coefficient and exponent of a term in the polynomial, forming a chain of nodes connected by pointers.
3. Why use linked lists for polynomial addition?
Linked lists allow dynamic memory allocation, making them suitable for handling polynomials of varying degrees.
They provide efficient insertion and deletion, essential for arithmetic operations on polynomials.
4. What are the steps to perform polynomial addition using linked lists in C?
Create a linked list for each polynomial, sorted by exponents.
Traverse both linked lists simultaneously and add corresponding terms with the same exponent.
Append any remaining terms from either polynomial to the result linked list.
5. How do linked lists handle sparse polynomials?
Linked lists are efficient in handling sparse polynomials, as they only store non-zero terms, avoiding memory wastage.