Polynomial addition using linked list

 

Represent a Polynomial using Linked List

✅ A polynomial is a mathematical expression like:

5x3+4x2+2x+75x^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:

CompareAction
5x⁴ vs 6x³ 5x⁴ copied
6x³ vs 3x²        6x³ copied
3x² vs 2x²3+2 = 5 ⇒ 5x²
1 vs 81+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

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more