Circular Linked list in Data Structure
In a circular Sinly linked list, The last node of a singly linked list carries a pointer to the list's first node. Circular singly-linked lists and circular doubly linked lists are also possible.
We traverse a circular singly linked list until we reach the starting node. There is no beginning or conclusion to the circular list of singly liked items. In the following part of any of the nodes, there is no null value.
A circular singly linked list is depicted in the image below.
- Circular linked lists are commonly used in operating systems for task maintenance.
- Circular linked lists are used in a variety of ways in computer science, including browser surfing, where a record of pages seen previously by the user is kept in the form of circular linked lists and can be accessed again by clicking the previous button.
Circular linked list memory representation.
- A memory representation of a circular linked list comprising a student's marks in four disciplines is shown in the image below.
- The graphic, on the other hand, depicts how the circular list is stored in memory.
- The list's beginning, or head, points to the element with index 1 and 13 marks in the data part and 4 in the following section.
- That is, it is linked to the node that is recorded at the fourth index in the list.
- However, because we are dealing with a circular linked list in memory, the last node of the list contains the address of the first node of the list.
- We may also have many linked lists in memory, each with its own set of start pointers corresponding to the list's various start nodes.
- The next section of the last node, which holds the address of the list's start node, is used to identify it.
- Any linked list's last node must be identified in order to determine the number of iterations that must be done when traversing the list.
All operations on a circular singly linked list are implemented using a menu-driven C programme.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void beginsert ();
void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 7)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search for an element\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
begin_delete();
break;
case 4:
last_delete();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter the node data?");
scanf("%d",&item);
ptr -> data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nnode inserted\n");
}
}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter Data?");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}
printf("\nnode inserted\n");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{ ptr = head;
while(ptr -> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nnode deleted\n");
}
}
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nnode deleted\n");
}
}
void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
flag=0;
}
else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found\n");
}
}
}
void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");
while(ptr -> next != head)
{
printf("%d\n", ptr -> data);
ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}
}
Expected Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
1
Enter the node data?10
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
2
Enter Data? 20
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
2
Enter Data?30
node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
3
node deleted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
4
node deleted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
5
Enter item which you want to search?
20
item found at location 1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
6
printing values ...
20
*********Main Menu*********
Choose one option from the following list ...
===============================================
1. Insert in beginning
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice?
7
