PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q2(b)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Linked List

Question

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

Solution

Polynomial Representation Using a Linked List: A single-variable polynomial is represented as a singly linked list in descending order of exponents, where each node has three fields:

Only non-zero terms are stored, making sparse polynomials space-efficient.

Algorithm ADD_POLY(p1, p2):

Algorithm ADD_POLY(p1, p2):
1. Initialize result = NULL, tail = NULL
2. While p1 != NULL and p2 != NULL:
       If p1->exp > p2->exp:
           APPEND(result, tail, p1->coeff, p1->exp)
           p1 = p1->next
       Else if p1->exp < p2->exp:
           APPEND(result, tail, p2->coeff, p2->exp)
           p2 = p2->next
       Else:
           sum = p1->coeff + p2->coeff
           If sum != 0:
               APPEND(result, tail, sum, p1->exp)
           p1 = p1->next
           p2 = p2->next
3. While p1 != NULL:
       APPEND(result, tail, p1->coeff, p1->exp)
       p1 = p1->next
4. While p2 != NULL:
       APPEND(result, tail, p2->coeff, p2->exp)
       p2 = p2->next
5. Return result
Answer:

Each non-zero term is stored as a node (coeff, exp, next) ordered by decreasing exp. ADD_POLY merges two sorted polynomial lists in time by copying larger-exponent terms directly and summing coefficients when exponents match.

All past exam questions for Data Structure and Algorithms