Unite -3

Linear

Data

Structure
Linked list based
polynomial
addition
• Presented by :

Surya Prakash

Naveen

Thalapathi

Santhosh

Kamalesh
Topics :
• Polynomial
• Linked list
• Polynomial addition
• Special case handling
• Time and space complexity
• Advantage and disadvantage of linked lis
• Real world application
Introduction
 Polynomial operations are fundamental in various
domains including mathematics, physics, and computer
science.

 Addition of polynomials may seem simple algebraically,

but implementing it efficiently in programming
requires a structured approach.

 Traditional methods like arrays fall short when

dealing with sparse or large-degree polynomials.

 Linked lists offer a flexible and memory-efficient

alternative.
What is a Polynomial?
• A polynomial is a mathematical expression made up of
terms involving variables raised to non-negative
integer powers.

• General structure
P(x)=anxn+an−1xn−1+…+a1x+a0

• Each term consists of:

• A coefficient (e.g., 5 in 5x²)
• An exponent (e.g., 2 in 5x²)

• Degree of the polynomial = highest exponent with a non-

zero coefficient.
The Problem with Traditional Methods
 Arrays require pre-defined sizes, making them
inefficient when the number of non-zero terms is
unknown.

 Sparse polynomials lead to wasted space in arrays, as

many coefficients might be zero.

 Inserting or removing terms from arrays can be costly

due to shifting elements.

 Linked lists solve these problems by allowing dynamic

storage and simplified manipulation.
Sparse vs Dense Polynomials
 Dense Polynomial:

o All terms from highest to lowest degree are stored.

o Even terms with zero coefficients are included.
o Suitable for small polynomials or when most terms
are non-zero.

 Sparse Polynomial:

o Only non-zero coefficient terms are stored.

o Saves memory and improves efficiency for high-degree
polynomials.
o Linked lists are ideal for sparse representation due
Why Use Linked Lists for Polynomials?

 Dynamic Memory Allocation: Allocate memory only as

needed.
 Efficient Insertion/Deletion: Easy to insert
/deletion terms in the correct order.
 No Predefined Size: Suitable for unknown-length or
variable-size polynomials.
 Efficient Traversal: Can process terms sequentially
for addition and other operations.
 Avoids zero-coefficient storage.
Linked List Basics

 A linked list consists of nodes connected via

pointers.

 Each node contains:

o Data (coefficient and exponent in this case)
o Pointer to the next node.

 Types: Singly Linked List (used here), Doubly Linked

List, Circular List.

 Easy to traverse and grow/shrink dynamically.

Representing Polynomials Using Linked
List
Each polynomial can be represented as a linked list of nodes,
where each node stores a term of the polynomial.
• The terms are arranged in descending order of exponents.

• Each node contains:

• Coefficient (Coeff) – the number in front of the variable

• Exponent (Exp) – the power of the variable

 Example: Polynomial 6x⁴ + 3x² + 2 would be:

o Node1 → Coeff: 6, Exp: 4
o Node2 → Coeff: 3, Exp: 2
o Node3 → Coeff: 2, Exp: 0

 Nodes are linked: Node1 → Node2 → Node3 → NULL

Simple program // Printing the polynomial
Term* poly = t1;
#include <iostream>
using namespace std; while (poly != nullptr) {
cout << poly->coeff <<
struct Term { "x^" << poly->exp;
int coeff; if (poly->next !=
int exp; nullptr)
Term* next; cout << " + ";
}; poly = poly->next;
}
int main() {
// Manually creating 3 terms: 5x^2 cout << endl;
+ 3x + 1
return 0;
Term* t1 = new Term{5, 2,
nullptr}; }
Term* t2 = new Term{3, 1,
nullptr};
Term* t3 = new Term{1, 0, Output :
nullptr}; 5x²+3x¹+1x⁰
}
Taking Polynomial Input

 Input format:
o Number of terms
o Each term entered as a pair: (coefficient,
exponent)

 Terms must be stored in descending order of

exponents to simplify addition.

 If not sorted, sorting must be done before the

addition process.

 Duplicate exponents should be handled by

What is Polynomial
Addition?

 The process of adding two

polynomials involves combining
like terms.
 Like terms = same exponent
values → their coefficients
are summed.
 Terms with unique exponents
are simply added to the
result.
 Output is a new polynomial in
simplified form.
Addition Logic (Step-by-Step)

 Traverse both polynomials simultaneously.

 Compare exponents at current nodes of both lists:

o If exponents are equal → add coefficients → insert
into result.
o If one exponent is greater → copy that term into
result.

 Move forward in respective lists based on comparison.

 Continue until both lists are fully traversed.

 Example of Addition
#include <iostream> // Printing the result
using namespace std; cout << "Resultant Polynomial:
int main() { ";
for (int i = 0; i < size; i++)
const int size = 3; // Number {
of terms in the polynomial
cout << result[i] << "x^"
<< (size - i - 1);
// Polynomial 1: 5x^2 + 4x + 2
if (i != size - 1) cout <<
int poly1[size] = {5, 4, " + ";
2};
}
// Polynomial 2: 0x^2 + 5x + 5 cout << endl;
int poly2[size] = {0, 5, 5}; return 0;
}
// Resultant polynomial
int result[size];

// Adding corresponding
coefficients Output:
for (int i = 0; i < size; i++) Resultant
{ Polynomial: 5x^2 + 9x^1 + 7x^0
Future Scope &
Enhancements
•Imagine two grocery lists, each created by different people
•List A: 2 Milk, 3 Eggs, 1 Bread
•List B: 1 Milk, 2 Bread, 4 Apples
•🧠 When combining both lists:

•Like items are added:

•Milk → 2 + 1 = 3
•Bread → 1 + 2 = 3
•Unique items are kept:
•Eggs → 3 (only in List A)
•Apples → 4 (only in List B)
•✅ Final Combined List:
•3 Milk, 3 Bread, 3 Eggs, 4 Apples

•🔄 Just like in polynomial addition:

•Same exponents = combine coefficients
•Different exponents = keep both terms
•Result = a clean, merged, optimized structure — just like
your groceries list!
Properties of the Result

 The result is stored in a new linked

list.
 It will also be in descending order of
exponents.
 Each exponent appears only once (no
duplicates).
Zero coefficients are excluded from the
final list.
Special Case Handling
 If both polynomials have no matching exponents, all
terms are simply copied.

 If resulting coefficient is zero after addition → that

term is excluded.

 Edge case: Adding a polynomial to a zero polynomial →

returns the original polynomial.

. Ensure memory is allocated properly to avoid leaks or

errors.
Time and Space Complexity
 Time Complexity:
o O(m + n), where m and n are the number of terms in
the two polynomials.
o Each term is visited once.

 Space Complexity:
o O(m + n) in the worst case (if no common terms).

 Highly efficient for sparse polynomials compared to

array-based methods.
Advantages of
Using Linked
Lists
 ✅ Saves memory by only storing
non-zero terms.

 ✅ No need to predefine size or

handle resizing.

 ✅ Easy to add, delete or update

terms.

 ✅ Best for sparse and high-degree

polynomials.

 ✅ Simplifies polynomial
arithmetic operations like
subtraction and multiplication.
 Limitations of
Linked List
Representation
 ❌ No direct (random)
access to specific
elements.
 ❌ Slightly higher memory
overhead due to storing
pointers.
 ❌ More complex logic
needed for sorting and
merging.
 ❌ Traversal is
sequential — can be
slower for very long
polynomials.
Real-World Applications

 ✅ Computer Algebra Systems: Used for symbolic

computation.

 ✅ Digital Signal Processing: Polynomials represent

filters and systems.

 ✅ Cryptographic Algorithms: Certain encryption

techniques use polynomial rings.

 ✅ Control Systems Engineering: Transfer functions

often represented as polynomials.

 ✅ Mathematical Simulations: Complex models use

polynomial representations for behaviors.
Arrays vs Linked Lists

Comparison with Other Data

Structures

Feature Arrays Linked Lists

Dynamic, only
Fixed size, can waste
Memory Usage stores non-zero
space for zeros
terms
Costly due to Efficient with
Insertion/Deletion
shifting pointer changes
Flexibility Rigid structure Highly flexible
Suitable for
Sparse ❌ No ✅ Yes
Polynomials?