Circular doubly linked list
Doubly linked lists within NULL pointers are fairly obvious extension of the singly linked list. And the circular doubly linked lists are the variation of doubly linked lists.
A circular doubly linked list is one which has both the successor pointer and predecessor pointer in circular manner. The objective behind considering circular doubly linked lists is to simplify the insertion and deletion operations performed on doubly linked list. Consider the situation of an empty list. This situation can be dispensed with by never allowing a list to be empty. It can be accomplished by providing a special node called head node that always remains in realizing a same degree of symmetry in the linked list structure by making the list circular.
APPLICATION: ADDITION OF TWO POLYNOMIALS
Linked lists are widely used to represent and manipulate polynomials. Polynomials are the expressions containing number of terms with nonzero coefficients and exponents. Consider the following polynomial.
P (x) = an xne + an- 1 xne – 1 + … + a1 x1e + a
Where ai a nonzero coefficients
ei a exponents such that
In the linked representation of polynomials each term is considered as anode. And such a node contains three fields.
1. Coefficient
2. Exponent field.
3. Link field.
The coefficient field holds the value of the coefficient of a term and the exponent field contains the exponent value of that term. And the link field contains the address of the next term in the polynomial.
The logical representation of the node is given is below;
Sturct polynode
{
Int coeff;
Int expo;
Struct polynode *ptr
}
Typedef struct polynode PHODE;
Example:
Two polynomial P and Q and their corresponding linked list representations are as follows;
P = 5x3+2x2+10x+6+
And the second polynomial Q is
Q = 21 x4 + 16x3 + 4x2 + 5x + 10
Two polynomials can be added and the steps involved in adding two polynomials are given below.
1. Read the number of terms in the first polynomial, p.
2. Read the coefficient and exponents of the first polynomial.
3. Read the number of terms in the second polynomial Q.
4. Read the coefficients and exponents of the second polynomial.
5. Set the temporary pointers p and q to traverse the two polynomial respectively.
6. Compare the exponents of two polynomials starting from the first nodes.
(1) If both exponents are equal then add the coefficients and store it in the resultant linked list
(2) If the exponent of the current term in the first polynomial p is less than the exponent of the current term of the second polynomial is added to the resultant linked list. And move the pointer q to point to the next node in the second polynomial Q.
(3) If the exponent of the current term in the first polynomial p is greater than the exponent of the current term in the second polynomial Q then the current term of the first polynomial is added to the resultant linked list. And move the pointer p to the next node.
(4) Append the remaining nodes of either of the polynomials to the resultant linked list.
Data Structure & Algorithms Assignment Help, Live Experts
Struggling with data structure problems? Data structure subject is quite tough to learn? Need quick assistance in data structure questions? ExpertsMind.com is right place for you where your search ends, We at ExpertsMind offer online data structure assignment help, data structure homework help and data structure and algorithms question's answers by best online support by qualified tutors.
ExpertsMind.com - Circular Doubly Linked List Assignment Help, Circular Doubly Linked List Homework Help, Circular Doubly Linked List Assignment Tutors, Circular Doubly Linked List Solutions, Circular Doubly Linked List Answers, Linked Lists Assignment Tutors