  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

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 problem, we are given two polynomials represented by linked lists and are asked to add them. For example,

Input:

``````5x4 + 3x2 + 1
4x4 + 2x2 + x``````

Output:

``9x4 + 5x2 + x + 1``

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

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.

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.

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.

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);

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^0``````

Time 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.

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;
} else if (poly1->exp > poly2->exp) {
result = (Node*) malloc(sizeof(Node));
result->coef = poly1->coef;
result->exp = poly1->exp;
} else {
result = (Node*) malloc(sizeof(Node));
result->coef= poly2->coef;
result->exp = poly2->exp;
}
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);

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^0``````

Time 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.

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.

• 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.

• 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.

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.