Overview:
Polynomial: It is a mathematical expression consisting of variables and constants.
Linked list: It is a linear data structure that consists of nodes where each node consists of a data storage part and a pointer (or reference) to the next node in the linked list.
Polynomial addition using linked list:
We store each polynomial as a singly linked list where each node stores the exponent and coefficient in the data part and a reference to the next node as shown in the figure below. Their sum is then stored in another linked list.
Procedure:
Consider two polynomial where Polynomial
They are stored in a linked list as shown below.
Which is stored in the resultant linked list as shown below.
Input:
1.Read two polynomials.
Output:
1.Displays the sum of the two polynomials given.
Algo:
Step 1: Start.
Step 2: Define user defined datatype node consisting of int coefficient and exponent and a pointer next of type node.
Step 3: Defining create function
struct node* create(struct node* head, int co, int exp)
Check if(head == Null)
temp <- GetNode(node)
temp.co <- co
temp.exp <- exp
temp.next <- Null
Set head <- temp
otherwise
Set temp <- head
while(temp.next ≠ Null) do
temp <- temp.next
flag <- GetNode(node)
flag.co <- co
flag.exp <- exp
flag.next <- Null
temp.next <- flag
return head
Step 4: Defining Addition function
struct node* polyAdd(struct node *p1, struct node *p2, struct node *sum)
Set poly1 <- p1
Set poly2 <- p2
Set result <- Null
check if(poly1 ≠ Null AND poly2 == Null)
Set sum <- poly1
Return sum
else if(poly1 == Null AND poly2 ≠ Null)
Set sum <- poly2
Return sum
while(poly1 ≠ Null AND poly2 ≠ Null) do
Check if(sum == Null)
sum <- GetNode(node)
Set result <- sum
Otherwise
result.next <- GetNode(node)
Set result <- result.next
Check if(poly1.exp > poly2.exp)
Set result.co <- poly1.co
Set result.exp <- poly1.exp
Set poly1 <- poly1.next
Check if(poly1.exp < poly2.exp)
Set result.co <- poly2.co
Set result.exp <- poly2.exp
Set poly2 <- poly2.next
Otherwise
Set result.co <- poly1.co + poly2.co
Set result.exp <- poly1.exp
Set poly1 <- poly1.next
Set poly2 <- poly2.next
while(poly1 ≠ Null) do
Set result.next <- GetNode(node)
Set result <- result.next
Set result.co <- poly1.co
Set result.exp <- poly1.exp
Set poly1 <- poly1.next
while(poly2 ≠ Null) do
Set result.next <- GetNode(node)
Set result <- result.next
Set result.co <- poly2.co
Set result.exp <- poly2.exp
Set poly2 <- poly2.next
Set result.next <- Null
Return sum
Step 5: Defining Display function
void display(struct node* head)
Set temp <- head
while(temp ≠ Null) do
Display temp.co, temp.exp
Set temp <- temp.next
Step 6: Defining Main function
Set p1 <- Null
Set p2 <- Null
Set sum <- Null
Set flag <- 1
while(flag == 1) do
Display “1: Create Polynomial 1”
Display “2: Create Polynomial 2”
Display “3: Perform Addition”
Display “4: Exit”
Read choice
switch(choice)
Case 1:
Display “Enter coefficient for polynomial 1”
Read co
Display “Enter exponent for polynomial 1”
Read exp
Call create(p1, co, exp)
Case 2:
Display “Enter coefficient for polynomial 2”
Read co
Display “Enter exponent for polynomial 2”
Read exp
Call create(p2, co, exp)
Case 3:
Set sum <- call polyAdd(p1, p2, sum)
Call display(sum)
Case 4:
Set flag <- 0
End switch
Step 7: Stop
Characteristics of Polynomial Addition Using Linked List
1. Since it uses a linked list, extra pointer handling is required to store and add the polynomial
2. It requires an extra linked list for storing the resultant polynomial and hence, its space complexity is O(n) where n is the size of the linked list.
APPLICATION:
Addition of polynomial mathematical expressions.
ADVANTAGE:
1. Since the algorithm uses a linked list, it is dynamic and hence has efficient memory utilization.
DISADVANTAGE:
1. The pointer in the linked requires extra memory space.
2. Handling of the pointers while storing and adding increases overhead.
TIME COMPLEXITY
Let n be the number of nodes in Polynomial 1’s linked list and m be the number of nodes in Polynomial 2’s linked list.
For Polynomial 1, the create() and display function takes O(n) time and for polynomial 2 it takes O(m) time.
The polyAdd()function iterates over the two polynomials at the same time and hence, takes O(n + m) time, and comparing the two polynomials takes constant O(1) time.
Hence, the time complexity of the algorithm is O(n + m).
SPACE COMPLEXITY
The sum of the two polynomials is stored in a separate linked list.
The number of nodes in the resultant sum linked list is s ≥ n + m.
Hence, the space complexity is O(s) = O(n + m).
Related
Contributed by