Polynomial addition in a data structure is necessary for performing tasks such as
manipulating algebraic formulas, fitting curves in engineering programs, interpreting
signals in communication, and more.
A simple example of a polynomial is P(x) = 4x2+3x+5, where x is the variable,
the coefficients are [4, 3, 5], and the exponents are [2,1,0].
Adding two polynomials in algebra involves adding terms with the same exponent and
adding the constants to give a result. In programming, before we can add polynomials,
it’s essential to understand how polynomials are stored in terms of arrays, linked lists, or
other structures.
In this article, we explore how polynomials are represented and look into the algorithm
for polynomial addition in data structure. With examples, we can grasp the
fundamentals and learn how polynomial addition is applied in real-world scenarios.
Representation of Polynomials in
Data Structure
Polynomials can be represented as arrays or linked lists depending on the specific
requirements of the program.
Array Representation
The array is a straightforward representation of a polynomial in a data structure. Here,
the polynomial is stored using an array where each index corresponds to the power of
the variable, and the value of that index represents the coefficient of the variable.
For example, if the polynomial is 4x6+3x+5, the array would look like:
0 1 2 3 4 5 6
5 -2 0 0 0 0 4
Here, the coefficient 5 is in slot 0 of the array, which represents 5 x0
The coefficient -2 is in slot 1 of the array, which represents -2 x1
The coefficient 4 is in slot 6 of the array and represents 4 x6
As it is evident, arrays work well for dense polynomials where most terms have non-
zero coefficients. However, sparse polynomials like 4x100+5, where many coefficients are
zero, can waste a lot of space.
Link List Representation
With a linked list representation, each term of a polynomial is stored as a node in a
linked list. Each node contains three elements:
1. The coefficient of the term.
2. The exponent of the term.
3. Address of the next node in the list.
Coefficient Exponent Address of the next node
Considering the same example as above, the polynomial 4x6+3x+5 can be written as
Here, each node holds the coefficient and exponent as a pair, and the pointer links to
the following term in sequence. Linked list representation works very well for sparse
polynomials as there is no need to store zero coefficients.
Concept of Polynomial Addition
The polynomial addition in data structure occurs in a manner similar to that of a math
class. It involves adding two like polynomials by combining their coefficients. For
example, consider adding 4x2+3x+5 and 2x2+3x+5. The resulting polynomial would be
6x2+6x+10.
Examples of Polynomial Addition
Now let’s take a look at how it can be done with arrays and link lists with the help of
examples:
Polynomial Addition Using Array
Let’s take two different polynomials as examples of the algorithm for polynomial
addition in data structure:
A = 3x+5x2+7x3
B = 7+ 3x + 4x2
The steps to add the polynomials are as follows:
Start by determining the polynomial with the highest degree, as the resulting
polynomial will have the same degree.
Store each coefficient in the array index corresponding to its exponent.
Add the coefficients from the same index positions in both arrays and save the
sum in the corresponding index of the resulting array.
A = 3x+5x2+7x3
A = 0x0+3x1+5x2+7x3
0 1 2 3
0 3 5 7
B = 7x0+ 3x1 + 4x2
B = 7x0+ 3x1 + 4x2+ 0x3
0 1 2 3
7 3 4 0
The summation,
C= 7x0+ 6x1 + 9x2+ 7x3
0 1 2 3
7 6 9 7
Addition of Polynomials Represented as
Linked Lists
Now, let’s consider an example of polynomial addition in a data structure algorithm
using linked lists.
We have to add the polynomials 12x4 + 2x2 + 10 and 9x3 + 8x2 + x
Storing each as a linked list,
A = 12x4 + 2x2 + 10
B = 9x3 + 8x2 + x
Resultant linked list:
Algorithm for Polynomial Addition
in Data Structure
Here is an example of polynomial addition using linked list in a data structure in c:
Input:
// C program to add two polynomials
#include <stdio.h>
#include <stdlib.h>
// Define the Node structure for representing polynomial terms
struct Node {
int coeff;
int pow;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int c, int p) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->coeff = c;
newNode->pow = p;
newNode->next = NULL;
return newNode;
}
// Function to add two polynomials
struct Node* addPolynomial(struct Node* head1, struct Node* head2) {
// If any list is empty, return the other list
if (head1 == NULL) return head2;
if (head2 == NULL) return head1;
// Compare powers and recursively process the lists
if (head1->pow > head2->pow) {
struct Node* nextPtr = addPolynomial(head1->next, head2);
head1->next = nextPtr;
return head1;
} else if (head1->pow < head2->pow) {
struct Node* nextPtr = addPolynomial(head1, head2->next);
head2->next = nextPtr;
return head2;
} else {
// Add coefficients if powers are equal
struct Node* nextPtr = addPolynomial(head1->next, head2->next);
head1->coeff += head2->coeff;
head1->next = nextPtr;
return head1;
}
}
// Function to print the polynomial
void printList(struct Node* head) {
struct Node* curr = head;
while (curr != NULL) {
printf("%d,%d ", curr->coeff, curr->pow);
curr = curr->next;
}
printf("\n");
}
// Main function
int main() {
// Create 1st polynomial: 5x^2 + 4x^1 + 2x^0
struct Node* head1 = createNode(5, 2);
head1->next = createNode(4, 1);
head1->next->next = createNode(2, 0);
// Create 2nd polynomial: -5x^1 - 5x^0
struct Node* head2 = createNode(-5, 1);
head2->next = createNode(-5, 0);
// Add the two polynomials
struct Node* head = addPolynomial(head1, head2);
// Print the result
printList(head);
return 0;
}
