Deletion in Circular Linked List in C++

Deletion in Circular Linked List

What is deletion in circular linked in CPP programming?

Deletion in circular linked in C++ in general words can be understood as deleting a node from a predefined circular linked list. We can perform three different types of deletion in circular linked list, these different types of deletion are:-

  • Deletion from beginning of the circular linked list.
  • Deletion from specific position in circular linked list.
  • Deletion from end in circular linked list.

In this article, we will discuss what is the difference between these different types of deletion and how to perform them on a circular linked list in C++.

Types of deletion in circular linked list

1.) Deletion from beginning:

In this type of deletion in circular linked list delete the head of the list and the second node of the list act as new head.

2.) Deletion from specific position:

If we want to delete a node from specific position then we need to traverse till that position and delete that node. After deleting the node we will decrease the position of nodes after that node by one.

3.) Deletion from end:

In this of deletion in circular linked list we delete the tail of the list and after deleting the tail we will make last second node as the the new tail of the list

Types of deletion in circular linked list

Deletion from beginning

Deletion from beginning

How to perform deletion from beginning in circular linked list?

To perform deletion from beginning in circular linked list we will use the following steps:-

  1.  We will create a circular linked list with some data in it.
  2. We will define a node pointer and this node pointer as head of the list.
  3. Now we will traverse this node pointer till the end of the list and follow the algorithm for deletion from beginning in circular linked list below.
void deleteBegin()
{
	struct node *p,*temp;
	p=head;
	while(p->next!=head)
	{
		p=p->next;
	}
	temp=head;
	head=head->next; 
	p->next=head;
	free (temp);
}
Deletion from beginning in circular linked list in C++

Deletion from specific position

Deletion from specific position

How to perform deletion from specific position in circular linked list?

To perform deletion from specific position in circular linked list we will use the following steps:-

  1. We will create a circular linked list.
  2. We will use a node pointer to traverse till the specific node.
  3. Using a second pointer we will store the node there temporary and will link the previous node to the next of this node.
  4. At last we will free the temporary pointer.
void deleteSpecific(int pos)
{             
        struct node *p,*q;
        int del,k=0;
        del=pos-1;
        p=head;
        while(k!=del)
        {
            q=p;
            p=p->next;
            k++;
        }
        q->next=p->next;
        free(p);//deleting specific node
}
deletion from specific position in circular linked list in C++

Deletion from end

Deletion from end

How to perform deletion from end in circular linked list?

To perform deletion from end in circular linked list we will use the following steps:-

After creating a linked list with some data in it we will define:-

  1. We will define a node pointer this will initially point the head of the list and later will be used for traversing till the end of the list
  2. After traversing till the end of list we will store the last node in a temporary node.
  3. Now we will link the pointer of last second node to the head node.
  4. And at last we will free the node stored in a temporary node.
void deleteEnd()
{
       struct node *cur,*prev;
	cur=head;
	while(cur->next!=head)
	{
		prev=cur;
		cur=cur->next;
	}
	prev->next=head;
	free(cur);
}
deletion from end in circular linked list in C++