Insertion in circular doubly linked list at beginning

There are two scenario of inserting a node in circular doubly linked list at beginning. Either the list is empty or it contains more than one element in the list.

Allocate the memory space for the new node ptr by using the following statement.

 ptr = (struct node *)malloc(sizeof(struct node));

In the first case, the condition head == NULL becomes true therefore, the node will be added as the first node in the list. The next and the previous pointer of this newly added node will point to itself only. This can be done by using the following statement.

head = ptr;
      ptr -> next = head; 
      ptr -> prev = head; 

In the second scenario, the condition head == NULL becomes false. In this case, we need to make a few pointer adjustments at the end of the list. For this purpose, we need to reach the last node of the list through traversing the list. Traversing the list can be done by using the following statements.

 temp = head; 
	while(temp -> next != head)
	{
		temp = temp -> next; 
	}

At the end of loop, the pointer temp would point to the last node of the list. Since the node which is to be inserted will be the first node of the list therefore, temp must contain the address of the new node ptr into its next part. All the pointer adjustments can be done by using the following statements.

temp -> next = ptr;
	ptr -> prev = temp;
	head -> prev = ptr;
	ptr -> next = head;
	head = ptr;

In this way, the new node is inserted into the list at the beginning. The algorithm and its C implementation is given as follows.

Algorithm

• Step 1: IF PTR = NULL

Write OVERFLOW
Go to Step 13
[END OF IF]

• Step 2: SET NEW_NODE = PTR
• Step 3: SET PTR = PTR -> NEXT
• Step 4: SET NEW_NODE -> DATA = VAL
• Step 5: SET TEMP = HEAD
• Step 6: Repeat Step 7 while TEMP -> NEXT != HEAD
• Step 7: SET TEMP = TEMP -> NEXT

[END OF LOOP]

• Step 8: SET TEMP -> NEXT = NEW_NODE
• Step 9: SET NEW_NODE -> PREV = TEMP
• Step 1 : SET NEW_NODE -> NEXT = HEAD
• Step 11: SET HEAD -> PREV = NEW_NODE
• Step 12: SET HEAD = NEW_NODE
• Step 13: EXIT

C Function

#include<stdio.h>
#include<stdlib.h>
void beg_insert(int);
struct node
{
	int data;
	struct node *next;
	struct node *prev;
};
struct node *head;
void main ()
{
	int choice,item;
	do 
	{
		printf("\nEnter the item which you want to insert?\n");
		scanf("%d",&item);
		beg_insert(item);
		printf("\nPress 0 to insert more ?\n");
		scanf("%d",&choice);
	}while(choice == 0);
}
void beg_insert(int item)
{
   struct node *ptr = (struct node *)malloc(sizeof(struct node));
   struct node *temp;
   if(ptr == NULL)
   {
       printf("\nOVERFLOW");
   }
   else
   {
    ptr->data=item;
    if(head==NULL)
   {
      head = ptr;
      ptr -> next = head; 
      ptr -> prev = head; 
   }
   else 
   {
       temp = head; 
	while(temp -> next != head)
	{
		temp = temp -> next; 
	}
	temp -> next = ptr;
	ptr -> prev = temp;
	head -> prev = ptr;
	ptr -> next = head;
	head = ptr;
   }
   printf("Node Inserted");
}  
}

Output

Enter the item which you want to insert?
12
Node Inserted
Press 0 to insert more ?
0

Enter the item which you want to insert?
23
Node Inserted
Press 0 to insert more ?
1