Deletion from specific position in circular linked list in C++

C++ program for deletion from specific position

How to delete from specific position in circular linked list?

Deletion from nth position in a circular linked list is one of the variation of deletion operation that we usually perform on Circular Linked List. For performing deletion from a specific location we make use of pointers for traversing the circular linked list. Let’s see a C++ Program for deletion from nth position in a circular linked list

Steps to delete from specific position in circular linked list in CPP

 

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

  1. Initialize two node pointers p and q
  2. Initialize a variable k that will act as counter variable.
  3. Initialize del with pos-1.
  4. Now run a loop until k does not equal to del.
  5. In this loop make q=p and p=p->next
  6. Increase value of k by one on every successful iteration.
  7. Now make next of q equal to next of p.
  8. Delete node pointed by node pointer p.
Constuct circular linked list

How to construct a in C++?

class Node  

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

Algorithm in CPP programming to delete from specific position in Circular Linked List

Below is the algorithm in C++ programming for deletion from specific position in circular linked list

  • STRUCT NODE P & Q
  • K = 0
  • DEL = POS-1
  • P = HEAD
  • WHILE (K != DEL)
  • Q = P
  • P = P -> NEXT
  • K++
  • Q -> NEXT = P -> NEXT
  • FREE P

C++ program for deletion from specific position in circular linked list

#include <iostream>
using namespace std;

struct node {
    int num;
    struct node * next;
}*head;
void deleteSpecific(int pos)//function to delete any node from the list
{             
        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
}
void build(int n)//function to build 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<<"\nEnter position from where you want to delete the node: ";
    cin>>pos;
    cout<<"\nAfter deleting node from specific position, new list is:";  
    deleteSpecific( pos);
    display();	
    return 0;
}
Output:
Enter the size of circular linked list: 6
Enter data of the list:
21
22
33
24
25
26

Circular linked list data:
21 22 23 24 25 26 
Enter position from where you want to delete the node: 3

After deleting node from specific position, new list is:
Circular linked list data:
21 22 24 25 26

Want to learn more Data Structure?