Polynomial addition using linked list

 

Represent a Polynomial using Linked List

✅ A polynomial is a mathematical expression like:

$$5x^3 + 4x^2 + 2x + 7$$

✅ To represent this using a linked list, we create a node for each term.

✅ Each node contains:

• Coefficient (example: 5, 4, 2, 7)

• Exponent (example: 3, 2, 1, 0)

• Pointer to the next node

✅ Linked list nodes are connected from highest exponent to lowest exponent.

---

Structure of a Node

In C language, the structure will look like:

struct Node {
    int coeff;      // Coefficient
    int exp;        // Exponent
    struct Node* next; // Pointer to next node
};

---

Example

For polynomial:

4x^3+9x^2+6x+7

Linked list will look like:

Where [coefficient, exponent] is stored inside each node.

Why Linked List for Polynomials?

• Easy to add, subtract, or multiply polynomials.

• Can easily insert and delete terms.

• Memory efficient — no wasted space.

Algorithm to Create a Polynomial Linked List

Algorithm CreatePolynomial():

1. Start with head = NULL

2. Repeat until the user finishes entering terms:

   • Read coefficient and exponent

   • Create a new node with the given coefficient and exponent

   • If head == NULL:

     • Set head = new node

   • Else:

     • Attach new node at the end

3. Return head

Adding Two Polynomials

• Each polynomial is stored as a linked list with (coefficient, exponent) pairs.

• Compare exponents:

  • If exponents are equal, add coefficients and create a new term.

  • If exponent of first polynomial is greater, copy that term.

  • If exponent of second polynomial is greater, copy that term.

• Move forward in the respective list after handling each term.

Algorithm: AddPolynomials(P1, P2)

Input:
Two polynomial linked lists P1 and P2 (sorted by decreasing exponents).

Output:
A new polynomial linked list representing the sum.

---

Steps:

1. Start

2. Create a new empty list Result

3. Set pointers ptr1 to head of P1, and ptr2 to head of P2

4. While both ptr1 and ptr2 are not NULL:

   • If ptr1->exp > ptr2->exp:

     • Create new node with ptr1->coeff and ptr1->exp

     • Move ptr1 to next node

   • Else if ptr2->exp > ptr1->exp:

     • Create new node with ptr2->coeff and ptr2->exp

     • Move ptr2 to next node

   • Else (exponents are equal):

     • Sum = ptr1->coeff + ptr2->coeff

     • If sum ≠ 0:

       • Create new node with sum and ptr1->exp

     • Move both ptr1 and ptr2 to next nodes

5. While ptr1 is not NULL:

   • Copy remaining terms from ptr1 to Result

6. While ptr2 is not NULL:

   • Copy remaining terms from ptr2 to Result

7. End

Example

Suppose:

P1 = 5x⁴ + 3x² + 1
P2 = 6x³ + 2x² + 8

Addition step-by-step:

Compare	Action
5x⁴ vs 6x³	5x⁴ copied
6x³ vs 3x²	6x³ copied
3x² vs 2x²	3+2 = 5 ⇒ 5x²
1 vs 8	1+8 = 9 ⇒ 9

Result = 5x⁴ + 6x³ + 5x² + 9

C program - Polynomial addition using Linked List

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int coeff;

    int exp;

    struct Node *next;

};

struct Node *createNode(int coeff, int exp) {

    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));

    newNode->coeff = coeff;

    newNode->exp = exp;

    newNode->next = NULL;

    return newNode;

}

struct Node *insertNode(struct Node *head, int coeff, int exp) {

    struct Node *newNode = createNode(coeff, exp);

    if (head == NULL) {

        head = newNode;

    } else {

        struct Node *temp = head;

        while (temp->next != NULL)

            temp = temp->next;

        temp->next = newNode;

    }

    return head;

}

void display(struct Node *head) {

    struct Node *temp = head;

    if (temp == NULL) {

        printf("0\n");

        return;

    }

    while (temp != NULL) {

        printf("%dx^%d", temp->coeff, temp->exp);

        if (temp->next != NULL)

            printf(" + ");

        temp = temp->next;

    }

    printf("\n");

}

struct Node *addPolynomials(struct Node *p1, struct Node *p2) {

    struct Node *result = NULL;

    while (p1 != NULL && p2 != NULL) {

        if (p1->exp > p2->exp) {

            result = insertNode(result, p1->coeff, p1->exp);

            p1 = p1->next;

        } else if (p2->exp > p1->exp) {

            result = insertNode(result, p2->coeff, p2->exp);

            p2 = p2->next;

        } else {

            int sum = p1->coeff + p2->coeff;

            if (sum != 0)

                result = insertNode(result, sum, p1->exp);

            p1 = p1->next;

            p2 = p2->next;

        }

    }

    while (p1 != NULL) {

        result = insertNode(result, p1->coeff, p1->exp);

        p1 = p1->next;

    }

    while (p2 != NULL) {

        result = insertNode(result, p2->coeff, p2->exp);

        p2 = p2->next;

    }

    return result;

}

void main() {

    struct Node *p1 = NULL, *p2 = NULL, *sum = NULL;

    int n,m, coeff, exp, i;

    printf("Enter number of terms in first polynomial: ");

    scanf("%d", &n);

    for (i = 0; i < n; i++) {

        printf("Enter coefficient and exponent for term %d: ", i+1);

        scanf("%d%d", &coeff, &exp);

        p1 = insertNode(p1, coeff, exp);

    }

    printf("\nEnter number of terms in second polynomial: ");

    scanf("%d", &m);

    for (i = 0; i < m; i++) {

        printf("Enter coefficient and exponent for term %d: ", i+1);

        scanf("%d%d", &coeff, &exp);

        p2 = insertNode(p2, coeff, exp);

    }

    printf("\nFirst Polynomial: ");

    display(p1);

    printf("Second Polynomial: ");

    display(p2);

    sum = addPolynomials(p1, p2);

    printf("\nSum of Polynomials: ");

    display(sum);

}

Output

Enter number of terms in first polynomial: 3

Enter coefficient and exponent for term 1: 5 4

Enter coefficient and exponent for term 2: 3 2

Enter coefficient and exponent for term 3: 1 0

Enter number of terms in second polynomial: 3

Enter coefficient and exponent for term 1: 6 3

Enter coefficient and exponent for term 2: 2 2

Enter coefficient and exponent for term 3: 8 0

First Polynomial: 5x^4 + 3x^2 + 1x^0

Second Polynomial: 6x^3 + 2x^2 + 8x^0

Sum of Polynomials: 5x^4 + 6x^3 + 5x^2 + 9x^0