Deletion from beginning in circular linked list in C++

July 7, 2020

How to delete from beginning in circular linked list?

In this article, we will learn how to write a program for deletion from beginning in circular linked list in C++. So to delete node from circular linked list we first need to create a circular linked list and then we can delete the node from beginning. And after deleting the first node we will make second node as head of the list and will link the pointer of last node with the new head node.

We will discuss the steps and algorithm to do the same here.

Steps to delete from beginning in circular linked list in CPP

These steps are followed in C++ programming for deletion from beginning in circular linked list

If the circular linked list is empty, terminate function.
Else define two node pointers(p and temp).
Initialize p with head.
Now traverse until pointer of p points to the head
Now store head in the second node pointer i.e temp.
Make second node as new head of the list.
Link the pointer of last node with new head.
Free temp i.e the node pointer storing the previous head of the list.

How to construct a in C++?

class Node  
{  
    int data;  
    Node *next;  
};

Circular Linked List A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element.Thus it forms like loop like structure, hence known as circular linked list

Algorithm to write a CPP program to delete from beginning in Circular Linked List

Below is the algorithm for C++ program for deletion from beginning in circular linked list

STRUCT P &TEMP
P=HEAD
WHILE(P->NEXT!=HEAD)
P=P->NEXT
END WHILE
TEMP=HEAD
HEAD=HEAD->NEXT
P->NEXT=HEAD
FREE(TEMP)

C++ program for deletion from beginning in circular linked list

#include <iostream>
using namespace std;

struct node {
    int num;
    struct node * next;
}*head;
void build(int n)//function to build nodes of circular linked list
{
    int i, num;
    struct node *preptr, *newnode;

    if(n >= 1)
    {
        head = (struct node *)malloc(sizeof(struct node));

        cout<<"Enter data of the list:\n";
        cin>>num;
        head->num = num;
        head->next = NULL;
        preptr = head;
        for(i=2; i<=n; i++) { newnode = (struct node *)malloc(sizeof(struct node)); cin>>num;
            newnode->num = num;
            newnode->next = NULL;	
            preptr->next = newnode;	
            preptr = newnode;   		
        }
        preptr->next = head; 		//linking last node with head node
    }
}
void display()//function to display list
{
    struct node *tmp;
    int n = 1;
    
    if(head == NULL)
    {
        cout<<"List is empty";
    }
    else
    {
        tmp = head;
        
        cout<<"\nCircular linked list data:\n";
        do {
            cout<num<<" "; tmp = tmp->next;
            n++;
        }while(tmp != head);
    }
}
void deleteBegin()//function to delete beginning node from the circular linked list
{
		struct node *p,*temp;
		p=head;
		while(p->next!=head)
		{
			p=p->next;
		}
		temp=head;
		head=head->next; 
		p->next=head;
		free (temp);
}

int main()//main function
{
    int n,pos;
    head = NULL;
    cout<<"Enter the size of circular linked list: ";
    cin>>n;
    build(n); 
    display();
    cout<<"\nAfter deleting node from beginning, new list is:";  
    deleteBegin();
    display();	
    return 0;
}

Output:
Enter the size of circular linked list: 6
Enter data of the list:
11
12
13
14
15
16

Circular linked list data:
11 12 13 14 15 16 
After deleting node from beginning, new list is:
Circular linked list data:
12 13 14 15 16