Insertion in circular doubly linked list at end

There are two scenario of inserting a node in circular doubly linked list at the end. 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 become false, therefore node will be added as the last node in the list. For this purpose, we need to make a few pointer adjustments in the list at the end. Since, the new node will contain the address of the first node of the list therefore we need to make the next pointer of the last node point to the head node of the list. Similarly, the previous pointer of the head node will also point to the new last node of the list.

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

Now, we also need to make the next pointer of the existing last node of the list (temp) point to the new last node of the list, similarly, the new last node will also contain the previous pointer to the temp. this will be done by using the following statements.

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

In this way, the new node ptr has been inserted as the last node of the list. The algorithm and its C implementation has been described as follows.

Algorithm

• Step 1: IF PTR = NULL

Write OVERFLOW
Go to Step 12
[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 NEW_NODE -> NEXT = HEAD
• Step 6: SET TEMP = HEAD
• Step 7: Repeat Step 8 while TEMP -> NEXT != HEAD
• Step 8: SET TEMP = TEMP -> NEXT

[END OF LOOP]

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

C Function

#include<stdio.h>
#include<stdlib.h>
void insertion_last(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);
		insertion_last(item);
		printf("\nPress 0 to insert more ?\n");
		scanf("%d",&choice);
	}while(choice == 0);
}
void insertion_last(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;
        }
   }
     printf("\nNode Inserted\n");
}

Output

Enter the item which you want to insert?
123

Node Inserted

Press 0 to insert more ?
12