---
title: "Polynomial addition using linked list"
subject: "Data Structure and Algorithm"
chapter: 4
key: "semester_4/data_structure_and_algorithm:polynomial-addition-linked-list"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/polynomial-addition-linked-list
site: BCT Engineering
---

# Polynomial addition using linked list

Data Structure and Algorithm · Chapter 4: Linked lists

- Asked in: 2074 Bhadra, 5 marks; 2072 Magh, 4 marks; 2071 Magh, 5 marks (asked 3 times)
- Video: [Polynomial Addition Using Linked List Algorithm](https://www.youtube.com/watch?v=V_ZNKu_pUPQ) — TutorialsPoint
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/polynomial-addition-linked-list
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-4

## Question

Explain how the addition of two polynomials is done using linked list.

## Short answer

Two polynomials stored as linked lists in decreasing exponent order are added by merging-like traversal: compare exponents, sum coefficients if equal, skip zero sums. Resulting polynomial has no zero terms. Time is O(m+n). Example: 5x³+4x²+2 and 3x³-4x²+7x+1 yield 8x³+7x+3.

## Answer

A polynomial is stored as a linked list where each node holds one non-zero term: its **coefficient**, its **exponent** and a **link** to the next term. Terms are kept in decreasing order of exponent, so two polynomials can be added by walking through both lists together (like merging).

```c
struct term {
    int coef;           /* coefficient */
    int exp;            /* exponent    */
    struct term *next;
};
```

#### Example
P = 5x³ + 4x² + 2 and Q = 3x³ − 4x² + 7x + 1
```text
P: [5|3]->[4|2]->[2|0]->NULL
Q: [3|3]->[-4|2]->[7|1]->[1|0]->NULL
```

#### Algorithm (p points to P, q to Q, R is the result list)
1. Set `p` and `q` to the first nodes; R is empty.
2. While `p != NULL` and `q != NULL`:
   - if `p->exp > q->exp`: append (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 (equal exponents): `sum = p->coef + q->coef`; if sum ≠ 0 append (sum, p->exp) to R; move both `p` and `q`.
3. Copy the remaining nodes of whichever list is not finished to R.
4. Return R.

#### Trace
| Step | p term | q term | Action | R so far |
|---|---|---|---|---|
| 1 | 5x³ | 3x³ | equal, 5+3 = 8 | 8x³ |
| 2 | 4x² | −4x² | equal, sum 0, skip | 8x³ |
| 3 | 2x⁰ | 7x¹ | q larger, copy 7x | 8x³ + 7x |
| 4 | 2x⁰ | 1x⁰ | equal, 2+1 = 3 | 8x³ + 7x + 3 |

**Result: R = 8x³ + 7x + 3** (checked by running the C code below).

```c
struct term *add(struct term *p, struct term *q) {
    struct term head, *t = &head;     /* dummy head simplifies appending */
    head.next = NULL;
    while (p && q) {
        if (p->exp > q->exp)      { t->next = mk(p->coef, p->exp); p = p->next; t = t->next; }
        else if (p->exp < q->exp) { t->next = mk(q->coef, q->exp); q = q->next; t = t->next; }
        else {
            int s = p->coef + q->coef;
            if (s != 0) { t->next = mk(s, p->exp); t = t->next; }
            p = p->next; q = q->next;
        }
    }
    for (; p; p = p->next) { t->next = mk(p->coef, p->exp); t = t->next; }
    for (; q; q = q->next) { t->next = mk(q->coef, q->exp); t = t->next; }
    return head.next;
}
```
`mk(c, e)` allocates a node with coefficient `c`, exponent `e` and `next = NULL`. Time is O(m + n) for lists of m and n terms.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does each node of the polynomial linked list hold?
   A. Coefficient, exponent and a link to the next term
   B. Only the coefficient and the degree of the polynomial
   C. Exponent and a pointer to the previous term
   D. A coefficient and a pointer to the result list
   Answer: A. Each non-zero term is one node with coef, exp and next. (Key point: Node structure)

2. In the addition algorithm, what is done when p->exp equals q->exp?
   A. Append both terms separately and move p only
   B. Add coefficients; append the term only if the sum is non-zero, and move both pointers
   C. Append the larger coefficient and move q
   D. Multiply the coefficients and move both pointers
   Answer: B. Like terms combine; a zero sum is dropped. (Key point: Equal exponents)

3. If p->exp > q->exp, what is done?
   A. Copy q's term and advance q
   B. Add the coefficients
   C. Copy p's term to the result and advance p
   D. Stop and copy the rest of p
   Answer: C. The higher-exponent term cannot combine with any term in q, so it is copied. (Key point: Unequal exponents)

4. P = 5x^3 + 4x^2 + 2 and Q = 3x^3 - 4x^2 + 7x + 1. What is P + Q?
   A. 8x^3 + 8x^2 + 7x + 3
   B. 8x^3 + 7x + 1
   C. 2x^3 + 8x^2 + 7x + 3
   D. 8x^3 + 7x + 3
   Answer: D. x^3: 5+3=8, x^2: 4-4=0 dropped, x: 7, constant: 2+1=3. (Key point: Result of example)

## Related in Data Structure and Algorithm

- [Polynomial representation and addition algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Apolynomial-representation-addition-algorithm) — Data Structure and Algorithm, chapter 4

## Related in other subjects

- [Express x³−5x²+x+2 in Legendre polynomials](https://www.bctengineer.com/question.md?key=semester_2%2Fmathematics%3Aexpress-x3-5x2-x-2) — Mathematics, chapter 4, asked 3×