Deletion from end in circular linked list in C++

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

How to delete from end in circular linked list?

Deletion from end in circular linked list in C++ is one of the deletion operation that we can perform on the circular sequenced list. The other deletion operations that we can perform are:-

  • Deletion from beginning i.e. to delete the head node of the list.
  • Deletion from any specific position i.e. to delete any node from the list.

In this article, we will learn how we can code a program in CPP to delete from end in  circular linked list using the given steps and algorithm.

Steps to delete from end in circular linked list in CPP

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

  1. Print deletion not possible if list is empty.
  2. Else define two node pointers cur and prev
  3. Initialize cur pointer with head
  4. Change prev pointer to current and cur to cur->next until next of the current does not equal to head.
  5. Now link last second node that is the node pointed by prev node pointer to head.
  6. Free cur as it stores the last node of the list.
Constuct circular linked list

How to construct a in C++?

class Node  

    int data; 
    Node *next; 
}; 
deletion from end in circular linked list in C++

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

Below is the algorithm to write C++ program for deletion from end in circular linked list

  • STRUCT  CUR & PREV
  • CUR=HEAD
  • WHILE(CUR->NEXT!=HEAD)
  • PREV=CUR
  • CUR=CUR->NEXT
  • END WHILE
  • PREV->NEXT=HEAD
  • FREE(CUR)

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

#include <iostream>
using namespace std;

struct node {
    int num;
    struct node * next;
}*head;
void deleteEnd()//fuction to delete last node from the circular linked list
{
       struct node *cur,*prev;
		cur=head;
		while(cur->next!=head)
		{
			prev=cur;
			cur=cur->next;
		}
		prev->next=head;
		free(cur);
}
void build(int n)//function to build 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<<tmp->num<<" ";
            tmp = tmp->next;
            n++;
        }while(tmp != head);
    }
}
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 last node, new list is:";  
    deleteEnd();
    display();	
    return 0;
}
Output:
Enter the size of circular linked list: 6
Enter data of the list:
11
21
31
41
51
61

Circular linked list data:
11 21 31 41 51 61 
After deleting last node, new list is:
Circular linked list data:
11 21 31 41 51

Want to learn more Data Structure?