Data structure tutorial 5: Circular Singly Linked List

In this chapter we shall learn about below topics:

In the first chapter of Linked List we learnt about Singly Linked List. In this chapter we shall learn about circular singly linked list.

The only addition is, the last node next pointer will point to the head node, hence making it circular Linked List.

For a single node

For multiple Nodes

To insert a node at end, we do following steps:

1. Take a new node and copy the data.

2. If there are no elements, then this node will be the head node and make next pointer point to the same node

3. Else, traverse till the end of the node, then link the next pointer of the last node, to the new node, and next pointer of the new node to the head node.

To delete the node at the end, we perform the below steps:

1. If there is only 1 node, then delete the node.

2. Else traverse till the end of the list, make the “next” pointer of previous node point to the head node.

3. Free the temp node.

To display all the elements, take a temp pointer, so that we don’t lose the head node.

Then traverse the list till the end of the list.

#include<stdio.h>
#include<stdlib.h>
 
 
struct Node
{
	int data;
	struct Node *next;
	
};
 
struct Node *head=NULL;
 
 
void insert_end(int data)
{
	//create a temp node, allocate memory and copy the data.
   struct Node *temp;
   temp = (struct Node*)malloc(sizeof(struct Node));
   temp -> data = data;
 
   //if this is the first node,
   if(head == NULL)
   {
   	//then assign the temp node as head and
   	// point the 
      head = temp;
      temp -> next = head;
   }
   else
   {
   	  //take a current node, traverse till the end of the list
      struct Node *current = head;
      while(current -> next != head)
         current = current -> next;
 
     //assign the next of current node to temp node
     //assign the next of temp node to head
     //thus making circular linked list
      current -> next = temp;
      temp -> next = head;
   }
}
 
 
// delete TAIL node of a circular singly linked list
void delete_tail()
{
   if(head == NULL)
      printf("List is empty \n");
   else
   {
      struct Node *temp1 = head;
      struct Node *temp2 = head;
      if(temp1 -> next == head)
      {
         head = NULL;
         free(temp1);
      }
      else
      {
        //as this is a circular list,
        // hence we check if the next pointer points to the head node
         while(temp1 -> next != head)
         {
            temp2 = temp1;
            temp1 = temp1 -> next;
         }
         temp2 -> next = head;
         free(temp1);
      }
      printf("\nElement deleted");
   }
}
 
void display()
{
   if(head == NULL)
      printf("\n Empty List");
   else
   {
   	 	struct Node *temp = head;
   	 	printf("Printing values\n");
       	while(temp -> next != head)  
        {  
          
            printf("%d\n", temp -> data);  
            temp = temp -> next;  
        }  
        printf("%d\n", temp -> data);  
    }  
}
 
int main()
{
	int value;
	int logout = 0;
	while(logout == 0)
	{
		printf("Choose any option:\n\n");
		printf("1)Insert end\n");
		printf("2)Delete tail\n");
		printf("3)Display List\n");
		printf("4)Exit\n");
 
		int choice;
		scanf("%d",&choice);
		switch(choice)
		{
			case 1:
				printf("Enter value:\n");
				scanf("%d",&value);
				insert_end(value);
			break;
 
			case 2:
				delete_tail();
			break;	
 
			case 3:
				display();
			break;
 
			case 4:
				logout = 1;
			break;
		}
	}
}

Choose any option:
 
1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
1
Choose any option:
 
1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
2
Choose any option:
 
1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
3
Choose any option:
 
1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
4
Choose any option:
 
1)Insert end
2)Delete tail
3)Display List
4)Exit
3
Printing values
1
2
3
4
Choose any option:
 
1)Insert end
2)Delete tail
3)Display List
4)Exit
2
 
Element deleted Choose any option:
 
1)Insert end
2)Delete tail
3)Display List
4)Exit
3
Printing values
1
2
3
Choose any option:
 
1)Insert end
2)Delete tail
3)Display List
4)Exit
4