Describe the picture

If you are learning Data Structures for the first time, you have probably seen expressions like this one:

5x³ + 4x² + 7x + 2

You have also met linked lists.

At first, these two topics look completely unrelated. You might even be thinking:

"What does a linked list have to do with a polynomial?"

Quite a lot, actually. A linked list is a very convenient way to store a polynomial, especially when many powers of x are missing.

In this article, we start from the absolute beginning and slowly build up to:

  • what a polynomial is,
  • why an array is not always the best way to store one,
  • how a linked list stores one,
  • addition, subtraction, multiplication and evaluation, each written as a short, simple C-style algorithm,
  • test cases, so you can check your own answers.

A word about how the code is written. We have kept it as simple as possible for a beginner:

  • no pointer-to-pointer (**) and no passing of addresses (&),
  • our three polynomials are global variables, so every function can see them without any passing around.

Global variables are not how big professional programs are usually written, but they take a lot of confusion out of the first learning step. Once you are comfortable, you can rewrite everything to pass the lists as parameters.

One more thing. This article gives you the important functions, not a finished program. You still write main(), the input and the menu yourself, and that is where much of the real learning happens. You can also watch every step in our Polynomial visualizer and compare it with your own program afterwards.

Don't worry if linked lists still feel shaky. We take it one step at a time.

First: What Is a Polynomial?

You have seen expressions such as:

3x² + 5x + 7

That is a polynomial: an expression made of terms, where each term is a number multiplied by a power of a variable.

Take this one:

5x³ + 4x² + 7x + 2

It has four terms: 5x³, 4x², 7x and 2.

Every term has two important parts:

  • Coefficient: the number in front.
  • Exponent: the power of x.
Term Coefficient Exponent
5x³ 5 3
4x² 4 2
7x 7 1
2 2 0

Two small things might surprise you:

  • 7x really means 7x¹, so its exponent is 1.
  • A plain number like 2 has exponent 0. That works because x⁰ = 1, so 2 = 2x⁰.

Now look at that table again and think: each row is one term. What if every row lived inside one node of a linked list? That is the whole idea of this article.

Why Not Simply Use an Array?

A natural question from any beginner:

"Why don't we just use an array?"

Good question. We can, and for some polynomials it works well. Let the index be the exponent and the value be the coefficient:

5x³ + 4x² + 7x + 2

Exponent:     0   1   2   3
Coefficient:  2   7   4   5

Perfect. Now try this polynomial:

8x¹⁰⁰ + 5x² + 7

The highest exponent is 100, so the array needs 101 slots. But there are only three real terms:

Exponent:     0  1  2  3  4  5  ...  100
Coefficient:  7  0  5  0  0  0  ...   8

Almost everything is a zero. It is like booking a 101-seat bus for 3 passengers.

A polynomial like this is called sparse (most of its terms are missing). Sparse polynomials are exactly where linked lists shine.

A Linked List Stores Only the Terms That Exist

Instead of 101 slots, we store just the three terms:

[8 | 100] → [5 | 2] → [7 | 0] → NULL

Each box is a node with three fields:

[ coefficient | exponent | next ]

Think of it like a train

Imagine a train. Each coach carries one term of the polynomial. Every coach knows:

  1. its coefficient,
  2. its exponent,
  3. where the next coach is.

The last coach points to nothing (NULL). Our polynomial 5x³ + 4x² + 7x + 2 becomes:

[5 | 3] → [4 | 2] → [7 | 1] → [2 | 0] → NULL

One rule we will follow throughout:

Keep the terms in descending order of exponent (biggest power first).

That order is what makes addition and subtraction so neat, as you will see.

The Building Blocks

Our setup: three global lists

We keep three polynomials in global variables, which means variables declared outside every function, so every function can use them directly:

struct Node
{
    int coefficient;
    int exponent;
    struct Node *next;
};

struct Node *poly1  = NULL;    // the first polynomial
struct Node *poly2  = NULL;    // the second polynomial
struct Node *result = NULL;    // the answer of an operation

Each of these is just a pointer to the first node (the head) of a list. NULL means "this list is empty".

Create a node

struct Node* createNode(int c, int e)
{
    struct Node *node;

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

    node->coefficient = c;
    node->exponent = e;
    node->next = NULL;

    return node;
}

If malloc() is new to you, read it as: "give me some memory to hold one node." The arrow -> means "go to the node this pointer points to, and use its field." So node->exponent = e; means "put e into the exponent of that node."

Insert a term (the one helper that does the hard work)

Almost everything in this article uses one helper function, insertTerm. It does three jobs, always keeping the list in descending order of exponent:

  1. Find the right place for the new term.
  2. If a term with the same exponent already exists, combine the two (and remove the node if the coefficient becomes 0).
  3. Otherwise, insert a new node.
struct Node* insertTerm(struct Node *head, int c, int e)
{
    struct Node *prev = NULL;      // the node just before our place
    struct Node *curr = head;      // the node we are looking at
    struct Node *node;

    if (c == 0)
        return head;               // a term with coefficient 0 is not stored

    // Job 1: walk forward while the exponents are bigger than e
    while (curr != NULL && curr->exponent > e)
    {
        prev = curr;
        curr = curr->next;
    }

    // Job 2: same exponent found? Combine the two terms.
    if (curr != NULL && curr->exponent == e)
    {
        curr->coefficient = curr->coefficient + c;

        if (curr->coefficient == 0)        // they cancelled out: remove the node
        {
            if (prev == NULL)
                head = curr->next;
            else
                prev->next = curr->next;

            free(curr);
        }
        return head;
    }

    // Job 3: otherwise insert a new node between prev and curr
    node = createNode(c, e);
    node->next = curr;

    if (prev == NULL)
        head = node;               // it goes to the very front
    else
        prev->next = node;

    return head;
}

Notice that the function returns the head. Why? Because inserting can change which node is first (for example, when the new term has the biggest exponent). So we always store the answer back, like this:

poly1 = insertTerm(poly1, 5, 3);     // 5x³
poly1 = insertTerm(poly1, 4, 2);     // 4x²
poly1 = insertTerm(poly1, 2, 0);     // 2

That one habit, list = insertTerm(list, ...), replaces all the double-pointer trickery you may have seen in other tutorials.

Let's see it work. The list is [5 | 3] → [2 | 0] and we insert 4x²:

[5 | 3] → [2 | 0]        insert 4x²
 prev      curr
  • curr is 5x³. Its exponent 3 is bigger than 2, so we step forward.
  • Now prev is 5x³ and curr is 2x⁰. Its exponent 0 is not bigger than 2, so we stop.
  • The exponents differ, so we insert a new node between prev and curr:
[5 | 3] → [4 | 2] → [2 | 0]

A nice bonus: because insertTerm finds the right place itself, the user can type the terms in any order and the list still comes out sorted.

Display the polynomial

void display(struct Node *head)
{
    if (head == NULL)
        printf("0");

    while (head != NULL)
    {
        printf("%dx^%d", head->coefficient, head->exponent);

        if (head->next != NULL)
            printf(" + ");

        head = head->next;
    }
    printf("\n");
}

(Passing head like this is perfectly fine. It is just a copy of the pointer, so the original is not disturbed. What we avoid is a pointer to a pointer.)

Small challenge: a term like -2x^2 prints as + -2x^2 with this simple version. Can you make it print - 2x^2 instead? (Hint: look at the sign of the coefficient.)

Polynomial Addition

Suppose:

poly1 = 5x³ + 4x² + 2
poly2 = 3x³ + 6x² + 7x + 1

Just as in school, add the terms that have the same exponent:

5x³ + 3x³ = 8x³
4x² + 6x² = 10x²
       7x = 7x         (poly1 has no x term)
    2 + 1 = 3

So the answer is 8x³ + 10x² + 7x + 3.

The key idea:

Terms with the same exponent are added. Terms that have no partner are simply copied.

How the linked lists help

Both lists are sorted by exponent, so we can walk along them with two pointers, p (on poly1) and q (on poly2), always looking at the two current terms:

  • Same exponent? Add the coefficients, put the result in the answer, move both pointers.
  • p's exponent is bigger? Copy p's term, move p.
  • q's exponent is bigger? Copy q's term, move q.

Does this remind you of something? It is exactly the merge step of merge sort: two sorted lists become one sorted list.

The algorithm

We write addition and subtraction together, using a number called sign: +1 for addition, −1 for subtraction. Ignore subtraction for now, and read it as addition:

void combine(int sign)
{
    struct Node *p = poly1;        // walks along poly1
    struct Node *q = poly2;        // walks along poly2

    result = NULL;                 // start with an empty answer

    while (p != NULL && q != NULL)
    {
        if (p->exponent == q->exponent)
        {
            result = insertTerm(result, p->coefficient + sign * q->coefficient, p->exponent);
            p = p->next;
            q = q->next;
        }
        else if (p->exponent > q->exponent)
        {
            result = insertTerm(result, p->coefficient, p->exponent);
            p = p->next;
        }
        else
        {
            result = insertTerm(result, sign * q->coefficient, q->exponent);
            q = q->next;
        }
    }

    while (p != NULL)              // leftover terms of poly1
    {
        result = insertTerm(result, p->coefficient, p->exponent);
        p = p->next;
    }

    while (q != NULL)              // leftover terms of poly2
    {
        result = insertTerm(result, sign * q->coefficient, q->exponent);
        q = q->next;
    }
}

To add, simply call:

combine(1);          // result = poly1 + poly2
display(result);

Let's trace our example:

p points to q points to What happens Result so far
5x³ 3x³ same exponent → 5 + 3 8x³
4x² 6x² same exponent → 4 + 6 8x³ + 10x²
2x⁰ 7x¹ q's exponent is bigger → copy 7x ... + 7x
2x⁰ 1x⁰ same exponent → 2 + 1 ... + 3

Done: 8x³ + 10x² + 7x + 3.

Two details that catch beginners

  • Terms that cancel out. Add 3x² + 5x and −3x² + 1. The x² terms give 3 − 3 = 0. We must not keep a 0x² node. Our insertTerm already ignores terms whose coefficient is 0, so the answer is correctly 5x + 1.
  • Leftovers. When one list finishes first, the other still has terms waiting. The last two loops copy them over. Forgetting them is a classic bug.

Note: insertTerm starts from the head every time, so this version is a little slower on very long polynomials. For learning that is perfectly fine. A good challenge for later: remember the last node so each insert is instant.

Polynomial Subtraction

Subtraction is the same walk. Using the same polynomials:

poly1 − poly2 = (5 − 3)x³ + (4 − 6)x² + (0 − 7)x + (2 − 1)
              = 2x³ − 2x² − 7x + 1

Look closely at the x term. poly1 has no x term, so we computed 0 − 7 = −7. A term that comes only from poly2 must be negated.

That is exactly why combine has sign * q->coefficient in three places: the equal-exponent case, the "q's exponent is bigger" case, and q's leftovers. To subtract, call:

combine(-1);         // result = poly1 - poly2
display(result);

The classic mistake: changing only the + to a − in the "same exponent" case. Then the 7x is copied with the wrong sign and you get +7x instead of −7x. Test it with the example above to see for yourself.

Subtracting a polynomial from itself should give the zero polynomial (an empty list, which display prints as 0). A nice test.

Polynomial Multiplication

Now something a little more interesting. Let's multiply:

(2x + 3)(x + 4)

Just like in school, multiply every term of the first by every term of the second:

2x × x = 2x²
2x × 4 = 8x
3  × x = 3x
3  × 4 = 12

Then combine the like terms (8x + 3x = 11x):

2x² + 11x + 12

The rule for multiplying two terms

Multiply the coefficients. Add the exponents.

5x³ × 4x²  =  (5 × 4) x^(3 + 2)  =  20x⁵

Remember: x² × x³ = x⁵, so the exponents add. (A very common slip is to multiply them.)

The algorithm

Multiplication produces terms in a messy order, and often several with the same exponent (8x and 3x). But we already have the perfect tool: insertTerm puts each product in the right place and combines like terms. So multiplication is just two loops:

void multiply(void)
{
    struct Node *a;
    struct Node *b;

    result = NULL;

    for (a = poly1; a != NULL; a = a->next)
    {
        for (b = poly2; b != NULL; b = b->next)
        {
            result = insertTerm(result,
                                a->coefficient * b->coefficient,
                                a->exponent + b->exponent);
        }
    }
}

Every term of poly1 meets every term of poly2.

Let's trace (2x + 3)(x + 4):

a (from poly1) b (from poly2) product result after insert
2x x 2x² 2x²
2x 4 8x 2x² + 8x
3 x 3x 2x² + 11x ← merged with 8x
3 4 12 2x² + 11x + 12

If poly1 has m terms and poly2 has n terms, we create m × n products, so multiplication does noticeably more work than addition.

Polynomial Evaluation

Evaluation means: put in a number for x and calculate the answer.

P(x) = 2x² + 3x + 1

P(2) = 2(2²) + 3(2) + 1
     = 8 + 6 + 1
     = 15

With a linked list, we just walk through it, work out coefficient × x^exponent for each term, and add everything up. This function evaluates poly1:

int evaluate(int x)
{
    int total = 0;
    struct Node *t;

    for (t = poly1; t != NULL; t = t->next)
    {
        int power = 1;
        int i;

        for (i = 0; i < t->exponent; i++)
            power = power * x;                 // x multiplied exponent times

        total = total + t->coefficient * power;
    }
    return total;
}

Notice we build x^exponent with a small loop of multiplications instead of a library function. That keeps the answers exact for whole numbers, and it shows what "x to the power 3" really means: x × x × x.

Watch out: an int can only hold numbers up to about two billion. A big x or a big exponent (like x¹⁰⁰) can overflow. For such cases, try long or long long.

Test Your Own Program (With Answers)

Here is the best part of writing your own program: you can check it. Run these and compare. If a result differs, you have just found a bug, which is a good thing.

Addition

poly1 poly2 poly1 + poly2
5x³ + 4x² + 2 3x³ + 6x² + 7x + 1 8x³ + 10x² + 7x + 3
3x² + 5x −3x² + 1 5x + 1 (the x² terms cancel)

Subtraction

poly1 poly2 poly1 − poly2
5x³ + 4x² + 2 3x³ + 6x² + 7x + 1 2x³ − 2x² − 7x + 1
x² + 1 x² + 1 0 (empty list)

Multiplication

poly1 poly2 poly1 × poly2
2x + 3 x + 4 2x² + 11x + 12
x + 1 x − 1 x² − 1 (the x terms cancel)
x² + x + 1 x − 1 x³ − 1
5x³ 4x² 20x⁵

Evaluation

poly1 x Answer
2x² + 3x + 1 2 15
2x³ + 4x + 5 2 29
3x² + 5x + 7 0 7
8x¹⁰⁰ + 5x² + 7 1 20

Don't Memorize, Understand the Shape

If you look at all those steps and think, "How will I remember all this?", good news: you don't have to. Remember the shape of the solution:

Polynomial
    ↓
Linked list, sorted by exponent
    ↓
Each node = coefficient + exponent + next
    ↓
Walk the list(s) with pointer(s)
    ↓
Do the operation (insertTerm builds every answer)

And the one-line idea behind each operation:

Operation The one-line idea
Add Walk both lists; same exponent → add; otherwise copy the bigger exponent
Subtract Same as add, but negate every term that comes from poly2
Multiply Every term × every term: multiply coefficients, add exponents, insertTerm combines like terms
Evaluate For each term, work out coefficient × x^exponent and add them up

Common Beginner Mistakes

1. Mixing up coefficient and exponent. In 7x⁴, the coefficient is 7 and the exponent is 4.

2. Not storing the head that insertTerm returns. Writing insertTerm(poly1, 5, 3); on its own throws the answer away. Always write poly1 = insertTerm(poly1, 5, 3);.

3. Forgetting to reset result = NULL; before a new operation. Otherwise the new answer gets mixed into the old one. (combine and multiply already do this at the top.)

4. Forgetting to move the pointer in a loop. If you never write p = p->next; inside while (p != NULL), the loop runs forever.

5. Wrong sign in subtraction. Terms that come only from poly2 must be negated, not just the equal-exponent ones.

6. Keeping zero terms. A node like 0x² is wasteful and makes your output look wrong. insertTerm skips them for you, so don't bypass it.

7. Not combining like terms in multiplication. The answer is 11x, not 8x + 3x.

8. Multiplying exponents instead of adding them. x² × x³ = x⁵, not x⁶.

9. Forgetting to free memory. Every node you create with malloc should be released with free when you are done. Write a small freeList function and call it at the end (and before you reuse result).

Array vs Linked List: Which One Is Better?

Feature Array Linked list
Memory May store many zeros Stores only the terms that exist
Size Usually fixed Grows as needed
Sparse polynomials Wasteful A good fit
Inserting a term Can be awkward Easy: just change a few pointers
Reading the coefficient of x^k Instant (use the index) Must walk the list
Extra memory per term None One pointer

So there is no rule that says "linked lists are always better." For a short, dense polynomial like 3x² + 2x + 1, an array is perfectly fine and simpler. For a long, sparse one like 8x¹⁰⁰ + 5x² + 7, a linked list wins.

Choose the data structure that fits the problem, not the one you learned most recently.

Practice Problems

Now it is your turn. Try these without peeking at any solution.

Beginner

  1. Build a linked list for 3x² + 5x + 7 using insertTerm and display it.
  2. Count the number of terms in a polynomial.
  3. Find the highest exponent (the degree).
  4. Evaluate 2x³ + 4x + 5 for x = 2. (The answer is in the test table above, so check yourself.)

Intermediate

  1. Add two polynomials, then subtract them.
  2. Multiply two polynomials.
  3. Make your display function print signs nicely (3x^2 - 5x + 1 instead of 3x^2 + -5x^1 + 1x^0).
  4. Write a freeList function that releases every node of a list, and use it before each new operation.
  5. Read the terms of a polynomial from the keyboard (coefficient and exponent, one term at a time) and build the list with insertTerm.

Challenge

  1. Make the addition faster by remembering the last node of result, so each term is appended instantly instead of searching from the head.
  2. Build a small menu-driven program:
1. Enter polynomial 1
2. Enter polynomial 2
3. Display both
4. Add
5. Subtract
6. Multiply
7. Evaluate polynomial 1
8. Exit

It is a great mini-project, because it brings together structures, pointers, linked lists, functions and problem solving in one program.

See It Move, Then Code It

Reading is good, but watching is better. Open the Polynomial visualizer on our Linked Lists lesson. Type your own polynomials, press Play or step through with Next, and watch the pointers move for Represent, Add, Subtract, Multiply and Evaluate. The panel next to it shows the code in C, Python and Java.

My suggestion for the best learning:

  1. Read the algorithm here.
  2. Write your own program (main(), input, menu) around these functions and test it with the tables above.
  3. Only if you get stuck, watch the visualizer and compare.

Struggling for a while and then finding your own bug teaches far more than copying a finished program.

Final Thoughts

When you first hear "implement polynomial operations using linked lists", it sounds like a big, scary Data Structures question. Broken down, it is quite logical.

A polynomial is simply a collection of terms. Each term has a coefficient and an exponent. A linked-list node can store exactly that:

[ coefficient | exponent | next ]

So the whole polynomial is:

[5 | 3] → [4 | 2] → [7 | 1] → [2 | 0] → NULL

And the operations are just small, sensible steps:

  • Add: compare exponents and combine matching terms.
  • Subtract: the same, with the second polynomial's terms negated.
  • Multiply: multiply coefficients, add exponents, combine like terms.
  • Evaluate: work out each term for the given x and add the results.

The real skill in Data Structures is not memorizing a program. It is learning how to represent a problem, and then choosing the right steps to work on that representation.

Once that idea clicks, polynomial operations using linked lists become much less scary, and a lot more fun.

Happy learning, and keep building those lists!