Implementation of Polynomial Addition using Linked List in C

Example

Consider two polynomials:

Polynomial 1: 4x^3 + 3x^2 + 5x + 6

 Polynomial 2: 3x^3 + 7x^2 + 8

After addition, the result will be: (4+3)x^3 + (3+7)x^2 + 5x + (6+8) = 7x^3 + 10x^2 + 5x + 14

Representation Using Linked List

Each term of the polynomial is stored in a node with the following structure:

struct Node {
    int coefficient;
    int exponent;
    struct Node* next;
};

[Expected Approach – 1] Using Recursion – O(n+m) Time and O(max(m,n)) Space

The recursive approach involves merging two polynomial linked lists into a new list. It adds corresponding terms with the same exponent recursively.

Implementation

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int coefficient;
    int exponent;
    struct Node* next;
};

struct Node* createNode(int coefficient, int exponent) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->coefficient = coefficient;
    newNode->exponent = exponent;
    newNode->next = NULL;
    return newNode;
}

struct Node* addPolynomials(struct Node* poly1, struct Node* poly2) {
    if (!poly1) return poly2;
    if (!poly2) return poly1;
    
    struct Node* result;
    if (poly1->exponent > poly2->exponent) {
        result = createNode(poly1->coefficient, poly1->exponent);
        result->next = addPolynomials(poly1->next, poly2);
    } else if (poly1->exponent < poly2->exponent) {
        result = createNode(poly2->coefficient, poly2->exponent);
        result->next = addPolynomials(poly1, poly2->next);
    } else {
        result = createNode(poly1->coefficient + poly2->coefficient, poly1->exponent);
        result->next = addPolynomials(poly1->next, poly2->next);
    }
    return result;
}

void displayPolynomial(struct Node* poly) {
    while (poly) {
        printf("%dx^%d", poly->coefficient, poly->exponent);
        poly = poly->next;
        if (poly) printf(" + ");
    }
    printf("\n");
}

int main() {
    struct Node* poly1 = createNode(4, 3);
    poly1->next = createNode(3, 2);
    poly1->next->next = createNode(5, 1);
    poly1->next->next->next = createNode(6, 0);

    struct Node* poly2 = createNode(3, 3);
    poly2->next = createNode(7, 2);
    poly2->next->next = createNode(8, 0);

    struct Node* result = addPolynomials(poly1, poly2);
    displayPolynomial(result);
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output:

7x^3 + 10x^2 + 5x + 14

[Expected Approach] Using Iterative Method – O(n+m) Time and O(1) Space

The iterative method uses two pointers to traverse both polynomials and merge them into a new linked list iteratively.

Implementation

struct Node* addPolynomialsIterative(struct Node* poly1, struct Node* poly2) {
    struct Node dummy;
    struct Node* tail = &dummy;
    dummy.next = NULL;
    
    while (poly1 && poly2) {
        if (poly1->exponent > poly2->exponent) {
            tail->next = createNode(poly1->coefficient, poly1->exponent);
            poly1 = poly1->next;
        } else if (poly1->exponent < poly2->exponent) {
            tail->next = createNode(poly2->coefficient, poly2->exponent);
            poly2 = poly2->next;
        } else {
            tail->next = createNode(poly1->coefficient + poly2->coefficient, poly1->exponent);
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
        tail = tail->next;
    }
    tail->next = poly1 ? poly1 : poly2;
    return dummy.next;
}

You can also try this code with Online C Compiler

Run Code

Algorithm for Performing the Polynomial Addition using Linked List in C

1. Create a linked list to store each polynomial.
    
2. Traverse both linked lists simultaneously.
    
3. If exponents match, add coefficients and store the result.
    
4. If one exponent is larger, append the term to the result.
    
5. Continue until all terms are processed.
    
6. Return the resultant linked list.

Dry Run for Polynomial Addition using Linked List in C

Consider two polynomials: 

Polynomial 1: 4x³ + 3x² + 5x + 6

 Polynomial 2: 3x³ + 7x² + 8

Applications of Polynomial Addition using Linked List in C  

1. Mathematical Computations  

Polynomials are widely used in mathematical computations, such as solving equations, curve fitting, & numerical analysis. Linked lists allow us to handle polynomials of any degree efficiently, making them ideal for these tasks.  
 

2. Computer Graphics  

In computer graphics, polynomials are used to represent curves & surfaces. Adding polynomials helps in blending shapes or creating smooth transitions between objects. Linked lists make it easier to manage these operations dynamically.  
 

3. Signal Processing  

Polynomials are used in signal processing to model & filter signals. Adding polynomials is often required when combining or modifying signals. Linked lists provide the flexibility to handle large & complex polynomials in real-time systems.  
 

4. Machine Learning  

In machine learning, polynomials are used in regression models to fit data. Adding polynomials helps in combining multiple models or improving accuracy. Linked lists ensure that these operations are performed efficiently, even with high-degree polynomials.  
 

5. Educational Tools  

Polynomial addition is a common topic in computer science & mathematics courses. Implementing it using linked lists helps students understand both data structures & polynomial operations better.  

Advantages of Polynomial Addition using Linked List in C  

 1. Dynamic Memory Allocation  

Linked lists allow dynamic memory allocation, meaning memory is allocated only when needed. This is particularly useful for polynomials with varying degrees, as it avoids wasting memory on unused terms.  

2. Efficient Handling of Sparse Polynomials  

Sparse polynomials (polynomials with many zero coefficients) are common in real-world applications. Linked lists store only non-zero terms, making them more efficient than arrays, which would waste space storing zeros.  
 

3. Flexibility in Operations  

Linked lists make it easier to insert, delete, or modify terms in a polynomial. For example, adding a new term or removing an existing one is straightforward with linked lists, whereas arrays require shifting elements.  

4. No Fixed Size Limitation  

Arrays have a fixed size, which can be a limitation when dealing with large polynomials. Linked lists, on the other hand, can grow or shrink as needed, providing more flexibility.  
 

5. Simplified Polynomial Addition  

Adding polynomials using linked lists is simpler & more intuitive. You can traverse both lists simultaneously, compare exponents, & combine like terms without worrying about array indices or resizing.  

Disadvantages of Polynomial Addition using Linked List in C  

1. Increased Memory Overhead  

Each node in a linked list requires additional memory to store the pointer to the next node. This overhead can be significant, especially for polynomials with many terms, compared to arrays where only the coefficients & exponents are stored.  
 

2. Slower Access Time  

Accessing a specific term in a linked list requires traversing the list from the beginning, which takes O(n) time. In contrast, arrays allow direct access to any term in O(1) time using indices.  
 

3. Complex Implementation  

Implementing linked lists involves more complex code compared to arrays. Managing pointers, dynamic memory allocation, & ensuring proper memory deallocation can be error-prone, especially for beginners.  

4. No Random Access  

Linked lists do not support random access, meaning you cannot directly access a term at a specific position. This limitation makes certain operations, like sorting or searching, less efficient compared to arrays.  

5. Memory Fragmentation  

Dynamic memory allocation in linked lists can lead to memory fragmentation over time. This can reduce the efficiency of memory usage & potentially slow down the program.  

Frequently Asked Questions

Why do we use linked lists for polynomial addition?

Linked Lists provide dynamic memory allocation, allowing efficient representation and manipulation of polynomials.

What is the time complexity of polynomial addition using linked lists?

Both recursive and iterative approaches have O(n + m) time complexity.

Which approach is better for polynomial addition, recursive or iterative?

The iterative approach is better due to O(1) space complexity, making it more memory-efficient.

Conclusion

In this article, we explored the implementation of polynomial addition using a linked list in C. By representing each term as a node in a linked list, we efficiently performed addition of two polynomials while maintaining their structure. This approach helps in dynamic memory allocation and is widely used in mathematical computations and computer algebra systems.