Wednesday, 6 December 2017

Circular Double Linked List:

A circular double linked list has both successor pointer and predecessor pointer in circular manner. The objective behind considering circular double linked list is to simplify
the insertion and deletion operations performed on double linked list. In circular double linked list the right link of the right most node points back to the start node and left link of the first node points to the last node.

The basic operations in a circular double linked list are:
a. Creation.
b. Insertion.
c. Deletion.
d. Traversing.

Creating a Circular Double Linked List with ‘n’ number of nodes: 
The following steps are to be followed to create "n" number of nodes:
a. Get the new node using getnode().
newnode = getnode();

b. If the list is empty, then do the following
start = newnode;
newnode -> left = start;
newnode ->right = start;

c. If the list is not empty, follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left->right = newnode;
start -> left = newnode;

Inserting a node at the beginning:
The following steps are to be followed to insert a new node at the beginning of the list:
a. Get the new node using getnode(). 
newnode=getnode();

b. If the list is empty, then
start = newnode;
newnode -> left = start;
newnode -> right = start;

c. If the list is not empty, follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left -> right = newnode;
start -> left = newnode;
start = newnode;

Inserting a node at the end:
The following steps are followed to insert a new node at the end of the list:
a. Get the new node using getnode()
newnode=getnode();

b. If the list is empty, then
start = newnode;
newnode -> left = start;
newnode -> right = start;

c. If the list is not empty follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left -> right = newnode;
start -> left = newnode;

Inserting a node at an intermediate position:
The following steps are followed, to insert a new node in an intermediate position in the list:
a. Get the new node using getnode().
newnode=getnode();

b. Ensure that the specified position is in between first node and last node. If not,
specified position is invalid. This is done by countnode() function.

c. Store the starting address (which is in start pointer) in temp. Then traverse the temp pointer upto the specified position.

d. After reaching the specified position, follow the steps given below: 
newnode -> left = temp;
newnode -> right = temp -> right;
temp -> right -> left = newnode;
temp -> right = newnode;
nodectr++;

Deleting a node at the beginning:
The following steps are followed, to delete a node at the beginning of the list:
a. If list is empty then display "Empty List" message.
b. If the list is not empty, follow the steps given below:
temp = start;
start = start -> right;
temp -> left -> right = start;
start -> left = temp -> left;

Deleting a node at the end:
The following steps are followed to delete a node at the end of the list:
a. If list is empty then display  "Empty List" message.
b. If the list is not empty, follow the steps given below:
temp = start;
while(temp -> right != start)
{
temp = temp -> right;
}
temp -> left -> right = temp -> right;
temp -> right -> left = temp -> left;

Deleting a node at Intermediate position:
The following steps are followed, to delete a node from an intermediate position in the list (List must contain more than two node).
a. If list is empty then display  "Empty List" message.
b. If the list is not empty, follow the steps given below:
c. Get the position of the node to delete.
d. Ensure that the specified position is in between first node and last node. If not, specified position is invalid.
e. Then perform the following steps:
if(pos > 1 && pos < nodectr)
{
temp = start; i = 1;
while(i < pos)
{
temp = temp -> right ;
i++;
}
temp -> right -> left = temp -> left;
temp -> left -> right = temp -> right;
free(temp);
printf("\n node deleted..");
nodectr--;
}


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput