Deletion in Circular Linked List in C

In this topic we want to discuss about delete the any node in circular linked list So, In this scenario is also have three ways to delete the node in linked list like doubly or singly linked list.

  • Deletion at beginning
  • Deletion at middle
  • Deletion at end

1. It is not easy to reverse the linked list.
2. If proper care is not taken, then the problem of infinite loop can occur.

3. If we are at a node, then we can go to any node. But in linear linked list it is not possible to go to previous node. Easy implementation of some operations is possible

deletion

Deletion at beginning

When we delete the node at beginning then there are some condition as follows them:-

the first one is if the list have no element or node then( head=Null) will then we can’t delete the node because list is empty  and print the simply “underflow” and then exit.

the second case if we have one more node in the list then we will put the simple condition (head->next==head) and when we delete the node in entire list then free the head pointer.

the third case is  when we have more than one node in the list then we traverse the list by using ptr pointer. when the pointer will reach the last node ,then last node will also point to the head and then free the head by using free() method.

Algorithm

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

deletion at beginnng in circular

Deletion at middle

Firstly we create a circular linked list.

in deletion at middle or nth position we want to delete any node in the circular linked list so, if the list is empty then we are do same thing (head==Null). Else  the list have more than one node then,

we exchange the  address of previous node and next node where as delete the node.and the middle node will be delete,before the middle node and after the middle will be connected.

  1. First, find the length of the linked list. That is, the number of nodes in the list.
  2. Take two pointers previous and current to traverse the list. Such that previous is one position behind the current node.
  3. Take a variable count initialized to 0 to keep track of the number of nodes traversed.
  4. Traverse the list until the given index is reached.
  5. Once the given index is reached, do previous->next = current->next.
deletion at middle in circular

Deletion at end

There are three cases in of deleting a node in circular linked list.

Firstly we need  to create a  list,if we have empty list then simply the condition (head=null) is true then print the “underflow”.

Second case is when  we have only one node in list then we will put the simple condition (head->next==head) and when we delete the node in entire list then free the head pointer.

Third is when we contains more than one node in linked list then we keep track of second last node of the list,and second last pointer(preptr) to point the head(ptr),and then make pointer is free(ptr).

Algorithm


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

Code for Deletion in circular

    #include<stdio.h> 
   #include<stdlib.h>
   void create(int);
   void deletion_beginning(); //function declare for delete node at beginning
   struct node
{
   int data; //create node
   struct node *next; // next pointer
  struct node *prev; //previous pointer
};
  struct node *head;
  void main ()
{
  int choice,item,choice1;
 do
{
  printf("1.Append List\n2.Delete Node from beginning\n3.Exit\n4.Enter your choice?");
  scanf("%d",&choice);
  switch(choice)
{
   case 1: //switch case condition
   printf("\nEnter the item\n");
  scanf("%d",&item);
  create(item);
  break;
  case 2:
  deletion_beginning();
  break;
  case 3:
  exit(0);
  break;
  default:
  printf("\nPlease Enter valid choice\n");
}

}  while(choice != 3);
}
   void create(int item) //function declared for create the list
{
  struct node *ptr = (struct node *) malloc(sizeof(struct node)); // for dynamic memory allocation
  struct node *temp;
  if(ptr == NULL)
{
  printf("\nOVERFLOW\n");
}
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");
}
  void deletion_beginning() // funtion calling for delete the node at beginning
{
  struct node *temp;
  if(head == NULL)
{
  printf("\n UNDERFLOW\n");
}
  else if(head->next == head)
{
  head = NULL;
  free(head);
  printf("\nNode Deleted\n");
}
else
{
  temp = head;
  while(temp -> next != head)
{
  temp = temp -> next;
}
  temp -> next = head -> next;
  head -> next -> prev = temp;
  free(head);
  head = temp -> next;
  printf("\nNode Deleted\n");
}

}