Skip to main content

Polynomial representation and addition algorithm

Short answer

Polynomial terms are stored as nodes (coef, exp, next) in descending exponent order. Addition: traverse both lists, compare exponents; if p.exp > q.exp, append p's term; if <, append q's term; if equal, add coefficients (if non-zero append). Append remaining terms from the non-empty list. Time O(m+n).

How do you represent polynomial equation using linked list? Write an algorithm to add two polynomial equations.

Representation

Each non-zero term of the polynomial is one node holding the coefficient, the exponent and a pointer to the next term. The terms are stored in decreasing order of exponent.

struct term { int coef; int exp; struct term *next; };

Example: 7x⁴ − 3x² + 5

poly -> [7|4]->[-3|2]->[5|0]->NULL

Algorithm POLYADD(p, q) -> result list r

  1. Set r = NULL (empty). Let p, q point to the first terms.
  2. While p ≠ NULL and q ≠ NULL:
    • If p->exp > q->exp: append term (p->coef, p->exp) to r; p = p->next.
    • Else if p->exp < q->exp: append (q->coef, q->exp) to r; q = q->next.
    • Else: s = p->coef + q->coef; if s ≠ 0 append (s, p->exp) to r; p = p->next; q = q->next.
  3. While p ≠ NULL: append p's term to r; p = p->next.
  4. While q ≠ NULL: append q's term to r; q = q->next.
  5. Return r.

Example: (3x³ + 2x + 1) + (4x² − 2x + 6)

p termq termActionr
3x³4x²p bigger, copy 3x³3x³
2x4x²q bigger, copy 4x²3x³ + 4x²
2x−2xequal, sum 0, drop3x³ + 4x²
16equal, 1+6 = 73x³ + 4x² + 7

Time is O(m + n) for m and n terms.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 4 questions →