Circular Linked List

As we have seen in the previous article, the last node contain NULL value. But in a Circular linked list the last node contains a pointer to the first node of the list. It does not contain null pointer. With this we can easily go from the last node to the first node. It has no end.

A circular linked list can be either singly or doubly linked list.

Circular Linked List Insertion

Insertion is a process of inserting an element in an existing linked list either at the following position.

Insert at the first position
Insert at the last position
Insert into ordered list

Algorithm

Insert at the first position

Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 11
[END OF IF]
Step 2: SET = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 while PTR NEXT != START
Step 7: PTR = PTR NEXT
[END OF LOOP]
Step 8: SET NEXT = START
Step 9: SET PTR NEXT =
Step 1 : SET START =
Step 11: EXIT

In the above algorithm, we first check the available memory. If it has no free memory, then print OVERFLOW, else we allocate free space for new node. Here, NEXT part is initialized with address of the first node and START pointer hold address of the new node.

Circular Linked List Deletion

Algorithm

Delete first node from circular list

Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR NEXT != START
Step 4: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: SET PTR NEXT = START NEXT
Step 6: FREE START
Step 7: SET START = PTR NEXT
Step 8: EXIT

Algorithm

Delete last node from circular list

Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR NEXT != START
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR NEXT
[END OF LOOP]
Step 6: SET PREPTR NEXT = START
Step 7: FREE PTR
Step 8: EXIT

Single Circular Linked List Program

#include<stdio.h>
#include<stdlib.h>
 
typedef struct Node
 
{
	int info;
	struct Node *next;
}node;
 
node *front=NULL,*rear=NULL,*temp;
 
void create_list();
void delete_list();
void display_list();
 
int main()
{
	int chc;
	do
	{
 	printf("\nChoice Options\n\t Enter 1 to create new element : ");
	printf("\n\t Enter 2 to delete the element : ");
	printf("\n\t Enter 3 to display the list : ");
	printf("\n\t Enter 4 to exit from main : ");
	printf("\nPlease Enter your choice : ");
	scanf("%d",&chc);
	
		switch(chc)
		{
			case 1:
	 		create_list();
			break;
	 	
		 	case 2:
	 		delete_list();
	 		break;
	 
	 		case 3:
	 		display_list();
	 		break;
	 
	 		case 4:
	 		return 1;
	 		
			default:
	 			printf("\nPlease Enter Valid Choice:");
	 	}
	}while(1);
 
	return 0;
}
 
void create_list()
{
	node *newnode;
	newnode=(node*)malloc(sizeof(node));
	printf("\nEnter the new node value : ");
	scanf("%d",&newnode->info);
	newnode->next=NULL;
	if(rear==NULL)
	front=rear=newnode;
	else
	{
		rear->next=newnode;
		rear=newnode;
	}
	
	rear->next=front;
}
 
void delete_list()
{
	temp=front;
	if(front==NULL)
		printf("\nList Underflow :");
	else
	{
		if(front==rear)
		{
			printf("\n%d",front->info);
			front=rear=NULL;
		}
		else
		{
			printf("\n%d",front->info);
			front=front->next;
			rear->next=front;
		}
 
	temp->next=NULL;
	free(temp);
	}
}
 
void display_list()
{
	temp=front;
	if(front==NULL)
		printf("\nEmpty List");
	else
	{
		printf("\n");
		for(;temp!=rear;temp=temp->next)
			printf("\n%d address=%u next=%u\t",temp->info,temp,temp->next);
			printf("\n%d address=%u next=%u\t",temp->info,temp,temp->next);
	}
}

Output of the above program


Choice Options
	 Enter 1 to create new element : 
	 Enter 2 to delete the element : 
	 Enter 3 to display the list : 
	 Enter 4 to exit from main : 
Please Enter your choice : 1

Enter the new node value : 34

Choice Options
	 Enter 1 to create new element : 
	 Enter 2 to delete the element : 
	 Enter 3 to display the list : 
	 Enter 4 to exit from main : 
Please Enter your choice : 1

Enter the new node value : 65

Choice Options
	 Enter 1 to create new element : 
	 Enter 2 to delete the element : 
	 Enter 3 to display the list : 
	 Enter 4 to exit from main : 
Please Enter your choice : 1

Enter the new node value : 73

Choice Options
	 Enter 1 to create new element : 
	 Enter 2 to delete the element : 
	 Enter 3 to display the list : 
	 Enter 4 to exit from main : 
Please Enter your choice : 3


34 address=10051600 next=10051632	
65 address=10051632 next=10051664	
73 address=10051664 next=10051600	
Choice Options
	 Enter 1 to create new element : 
	 Enter 2 to delete the element : 
	 Enter 3 to display the list : 
	 Enter 4 to exit from main : 
Please Enter your choice : 2

34
Choice Options
	 Enter 1 to create new element : 
	 Enter 2 to delete the element : 
	 Enter 3 to display the list : 
	 Enter 4 to exit from main : 
Please Enter your choice : 3


65 address=10051632 next=10051664	
73 address=10051664 next=10051632	
Choice Options
	 Enter 1 to create new element : 
	 Enter 2 to delete the element : 
	 Enter 3 to display the list : 
	 Enter 4 to exit from main : 
Please Enter your choice :