Polynomial Representation and Addition using Linked List

Mathematical polynomials jaise P(x) = 5x^4 - 2x^2 + 7x + 3 ko memory me efficiently store aur manipulate karne ke liye linked lists ideal data structure hain. Agar hum array use karein aur polynomial me powers high hon (jaise 10x^100 + 4), toh size 101 ka array waste hoga jisme 99 entries zeroes hongi.

Node Structure for Polynomial Term

struct PolyNode {
    int coeff;              // Coefficient (e.g. 5)
    int exp;                // Exponent (e.g. 4)
    struct PolyNode* next;  // Link to next term
};

Poly 1: 5x^2 + 4x + 2
[ 5 | 2 | Next ] ---> [ 4 | 1 | Next ] ---> [ 2 | 0 | NULL ]

Poly 2: 3x^2 + 6
[ 3 | 2 | Next ] ---> [ 6 | 0 | NULL ]

Result (Poly 1 + Poly 2): 8x^2 + 4x + 8
[ 8 | 2 | Next ] ---> [ 4 | 1 | Next ] ---> [ 8 | 0 | NULL ]

Polynomial Addition Algorithm

Dono polynomials ko head se compare karte hue merge sort ki tarah traverse karte hain:

• Agar p1->exp == p2->exp: Coefficients add karein sum = p1->coeff + p2->coeff, aur naya term result list me daalein. Dono pointers aage badhayein.
• Agar p1->exp > p2->exp: p1 ka term result me daalein aur p1 = p1->next karein.
• Agar p2->exp > p1->exp: p2 ka term result me daalein aur p2 = p2->next karein.

Time Complexity: O(m + n) jahan m aur n dono polynomials me number of terms hain.

Agli post me hum start karenge DSA Part-4: Stacks, Queues & Recursion, jisme pehla topic hoga Stack Data Structure: Array Implementation.