Polynomial Representation using Linked List

The array-based polynomial representation needs a size decided up front, either one slot per exponent (wasteful for a sparse polynomial) or two parallel arrays sized to the number of non-zero terms (which still needs a maximum capacity fixed in advance). A linked list avoids both: one node per non-zero term, allocated exactly when needed, with no upper limit on how many terms a polynomial can have.

Node structure

For 5x⁴ + 3x² + 7:

Only the three non-zero terms get a node, unlike the simple array representation, where the exponents 3 and 1 (missing from this polynomial) would still occupy array slots holding 0. Reading the chain from POLY gives the terms in order: 5x⁴, then 3x², then 7x⁰ (the constant term).

In C, a node is written as:

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

Creating a term node

CREATE_TERM(coef, exp)
 
1. Create NEW
2. NEW->coef = coef
3. NEW->exp = exp
4. NEW->link = NULL
5. Return NEW

Building the polynomial 5x⁴ + 3x² + 7 means calling this once per term, then linking the resulting nodes together in decreasing exponent order, exactly the same chain-building process as any other linked list, just with two data fields being set per node instead of one.

Adding two polynomials

Adding two polynomials means walking both lists together, term by term, comparing exponents at each step:

ADD_POLY(POLY1, POLY2)
 
1. RESULT = empty list
2. While POLY1 != NULL and POLY2 != NULL
       If POLY1->exp == POLY2->exp
           sum = POLY1->coef + POLY2->coef
           If sum != 0
               Add term (sum, POLY1->exp) to RESULT
           POLY1 = POLY1->link
           POLY2 = POLY2->link
       Else if POLY1->exp > POLY2->exp
           Add term (POLY1->coef, POLY1->exp) to RESULT
           POLY1 = POLY1->link
       Else
           Add term (POLY2->coef, POLY2->exp) to RESULT
           POLY2 = POLY2->link
3. Copy any terms left in POLY1 or POLY2 straight into RESULT
4. Return RESULT

Each "add term to RESULT" is just an insertion at the end of a linked list, the same insert-at-the-rear operation already covered, done once per new term as it's decided.

Example: matching exponents. Adding 5x⁴ + 3x² and 2x⁴ + 4x. Both lists start with exponent 4:

POLY1->exp == POLY2->exp (both 4), so their coefficients combine: 5 + 2 = 7, giving a 7x⁴ term in RESULT, and both POLY1 and POLY2 advance. Next, POLY1 holds exponent 2 and POLY2 holds exponent 1: since 2 > 1, 3x² is added from POLY1 alone, and POLY1 advances to NULL. Since POLY1 is now exhausted, step 3 copies whatever remains of POLY2, the 4x term, straight into RESULT:

RESULT is 7x⁴ + 3x² + 4x.

Example: a term cancels to zero. Adding 5x² and -5x². Both exponents match (2), so the coefficients combine: 5 + (-5) = 0. The sum != 0 check in step 2 catches this and skips adding a term entirely, since a zero-coefficient term shouldn't appear in the result at all, matching how a sparse representation never stores zero terms in the first place.

Step 3 exists because the two polynomials rarely run out of terms at exactly the same moment; whichever list still has terms left over just gets copied straight into RESULT, since there's nothing left to compare against. Polynomial addition is O(n + m), where n and m are the number of terms in each polynomial, since each node in both lists is visited exactly once.

Why this beats the array version

Quick recall

• A polynomial term node stores COEF, EXP, and LINK; nodes are kept in decreasing order of exponent.
• Only non-zero terms get a node, same motivation as the sparse array representation, but with no capacity decided in advance.
• Adding two polynomials walks both lists together, comparing exponents: equal exponents combine (dropped if the sum is 0), and a larger exponent copies through unchanged while the smaller side catches up.
• Once either list is exhausted, whatever remains of the other list is copied straight into the result.
• Polynomial addition is O(n + m), visiting every node in both lists exactly once.