# Polynomial Representation Using Linked List

Polynomial representation using linked lists is a critical concept in computer science and mathematics. In this guide, we explore how linked lists can effectively represent polynomials, especially in situations where polynomials are sparse (i.e., have many zero coefficients). Unlike arrays, linked lists provide a dynamic and memory-efficient way of representing polynomials, making operations like addition, subtraction, and multiplication more manageable and efficient. Understanding this representation is crucial for students and professionals dealing with complex mathematical computations and algorithm design.

Linked lists are fundamental data structures consisting of a sequence of nodes. Each node typically contains two parts: data and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, making them ideal for dynamic data storage. In the context of polynomial representation, each node in a linked list can represent a term of the polynomial, storing both its coefficient and exponent.

## Representing a Polynomial Term

In the linked list representation of a polynomial, each node corresponds to a term of the polynomial. The node structure usually contains three components:

• Coefficient: The numerical multiplier of the term.
• Exponent: The power to which the variable is raised in the term.
• Next: A pointer to the next term (node) in the polynomial.

This structure allows the polynomial to be stored as a linked list, where each node directly represents a term, and the entire list represents the polynomial in its entirety.

• Dynamic Size: The size of the polynomial isn’t fixed, allowing for easy addition or removal of terms.
• Efficient Storage: Especially beneficial for sparse polynomials where many coefficients are zero, as it only stores non-zero terms.
• Flexibility: Easier to implement operations like addition, multiplication, and differentiation compared to array-based representations.

## Example

To illustrate how a polynomial is represented using a linked list, let’s consider a specific example. Suppose we have a polynomial:

P(x)=7x^3+5x^2−2x+4

This polynomial will be represented as a linked list where each node represents a term of the polynomial.

### Node Structure

Each node in the linked list will typically have the following structure:

• Coefficient: The numerical coefficient of the term.
• Exponent: The exponent of the variable in the term.
• Next: A pointer to the next term (node) in the polynomial.

### Representation of the Polynomial as a Linked List

1. First Node (7x^3):
• Coefficient: 7
• Exponent: 3
• Next: Pointer to the second node
2. Second Node (5x^2):
• Coefficient: 5
• Exponent: 2
• Next: Pointer to the third node
3. Third Node (-2x):
• Coefficient: -2
• Exponent: 1
• Next: Pointer to the fourth node
4. Fourth Node (4):
• Coefficient: 4
• Exponent: 0 (since it’s a constant term)
• Next: NULL (as it is the last term)

### Visual Representation

The linked list for polynomial P(x) would visually look like this:

Each box represents a node, with the first number being the coefficient and the second number being the exponent. The arrows indicate the ‘next’ pointers linking each term of the polynomial.

Let’s break down the example of evaluating a polynomial using a linked list for the given polynomial:

P(x)=7x^3+5x^2−2x+4

and calculate its value for x=2.

### Step-by-Step Evaluation of Polynomial

1. Initial Setup:
• Polynomial: 7x^3+5x^2−2x+4
• Value to evaluate: x=2
• Initialize `Sum` to 0.
2. Evaluate First Term (7x^3):
• Calculation: 7×2^3
• Process: 7×8=56
• Update Sum=0+56=56
3. Evaluate Second Term (5x^2):
• Calculation: 5×2^2
• Process: 5×4=20
• Update Sum=56+20=76
4. Evaluate Third Term (-2x):
• Calculation: −2×2
• Process: −2×2=−4
• Update Sum=76−4=72
5. Evaluate Fourth Term (4):
• This is a constant term.
• Update Sum=72+4=76
6. Conclusion:
• The final value of P(2) is 76.
• So, when we substitute x=2 into the polynomial, the result is 76.

## C Program Program to Solve Polynomial

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Node {
int data;
struct Node *next;
struct Node *prev;
};

typedef struct Node Node;

// Create a node
Node* createNode(int coeff, int exp) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->coeff = coeff;
newNode->exp = exp;
newNode->next = NULL;
return newNode;
}

void appendNode(Node** head, int coeff, int exp) {
Node* newNode = createNode(coeff, exp);
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

// Function to evaluate the polynomial for a given value of x
int polynomialCalculation(Node* head, int x) {
int sum = 0;
while (temp != NULL) {
sum += temp->coeff * pow(x, temp->exp);
temp = temp->next;
}
return sum;
}

int main() {
Node* poly = NULL;
// Polynomial Construction 7x^3+5x^2−2x+4
appendNode(&poly, 7, 3);
appendNode(&poly, 5, 2);
appendNode(&poly, -2, 1);
appendNode(&poly, 4, 0);

int x = 2;
printf("Polynomial value for x = %d is: %d\n", x, polynomialCalculation(poly, x));

return 0;
}
``````

Output

`Polynomial value for x = 2 is: 76`

## Program Explanations

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>``````
• `stdio.h`: Standard input-output header for functions like `printf`.
• `stdlib.h`: Standard library header for functions like `malloc`.
• `math.h`: Math library header for mathematical functions like `pow`.

Node Structure Definition:

``````struct Node {
int data;
struct Node *next;
struct Node *prev;
};

typedef struct Node Node;``````
• A `struct Node` is defined to represent each term of the polynomial.
• It contains `coeff` (coefficient of the term), `exp` (exponent of the term), and `next` (pointer to the next term).

createNode Function:

``````// Create a node
Node* createNode(int coeff, int exp) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->coeff = coeff;
newNode->exp = exp;
newNode->next = NULL;
return newNode;
}``````
• This function creates a new node with given `coeff` and `exp`.
• It allocates memory for a new node, sets its coefficient and exponent, and initializes its `next` pointer to `NULL`.

appendNode Function:

``````void appendNode(Node** head, int coeff, int exp) {
Node* newNode = createNode(coeff, exp);
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}``````
• This function appends a new term/node to the end of the polynomial linked list.
• If the list is empty (`*head == NULL`), it sets the head to the new node.
• Otherwise, it traverses to the end of the list and appends the new node there.

polynomialCalculation Function:

``````// Function to evaluate the polynomial for a given value of x
int polynomialCalculation(Node* head, int x) {
int sum = 0;
while (temp != NULL) {
sum += temp->coeff * pow(x, temp->exp);
temp = temp->next;
}
return sum;
}``````
• This function evaluates the polynomial for a given value of `x`.
• It iterates through each term of the polynomial, calculates its value using `pow(x, exp)`, multiplies it by the coefficient, and adds it to `sum`.

main Function:

``````int main() {
Node* poly = NULL;
// Polynomial Construction 7x^3+5x^2−2x+4
appendNode(&poly, 7, 3);
appendNode(&poly, 5, 2);
appendNode(&poly, -2, 1);
appendNode(&poly, 4, 0);

int x = 2;
printf("Polynomial value for x = %d is: %d\n", x, polynomialCalculation(poly, x));

return 0;
}``````
• The `main` function is the entry point of the program.
• It first constructs the polynomial `7x^3 + 5x^2 - 2x + 4` by appending each term to the linked list.
• Then, it evaluates this polynomial for `x = 2` using the `polynomialCalculation` function.
• Finally, it prints the calculated value of the polynomial for the given `x`.

Hope this article helped you in understanding the writing Program and Algorithm to solve polynomial using linked list.