Circular Double Linked List:

A circular double linked list has both successor pointer and predecessor pointer in a circular manner. The objective behind considering circular double linked list is to simplify
the insertion and deletion operations performed on double linked list. In the circular double linked list, the right link of the rightmost node points back to the start node and left the 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
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:

0 comments:

Thanks
Mukesh Rajput