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

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

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

  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.
struct node {
    int num;
    struct node * next;
}
Deletion in circular linked list in C++ – 1

Algorithm in CPP programming to delete 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

Run
#include<iostream>
using namespace std;

struct Node
{
  int num;
  struct Node *next;
};

void insertStart (struct Node **head, int data)	//function to create linked list
{
  struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
  newNode->num = data;

  // if its the first node being entered
  if (*head == NULL)
    {
      *head = newNode;		// assigning itself as head
      (*head)->next = *head;	// assigning itself as next node

      cout << newNode->num << " Inserted\n"; return; 
        
    } // if CLL already as >=1 node
  struct Node *curr = *head;

  // traverse till last node in CLL
  while (curr->next != *head)
    {
      curr = curr->next;
    }

  curr->next = newNode;		// last node's next as this new node
  newNode->next = *head;	// new node's next as current head node

  *head = newNode;		// changing head node to this new node
  cout << newNode->num << " Inserted\n"; // previous head node becomes 2nd node 
  }
  void deleteBegin (struct Node **head) //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;
  p->next = (*head)->next;
  *head = (*head)->next;

  free (temp);
}

void deleteSpecific (struct Node **head, int pos)	//function to delete any node from the list
{
  if (pos < 1)
    {
      cout << "Invalid position entered";
      }
      else if (pos == 1) { 
          deleteBegin (head); 
          
      } 
      else { 
          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
    }				//deleting specific node
}

void display (struct Node *head)
{

  cout << "\nCircular Linked List : " << endl;

  // if circular linked list is empty currently
  if (head == NULL)
    return;

  struct Node *temp = head;

  // since we need to take care of circular nature of linked list
  do
    {
      cout << temp->num << " "; temp = temp->next;

    }
  while (temp != head);
  cout << endl;
}

int main ()				//main function
{
  // first node will be null at creation    
  struct Node *head = NULL;

  insertStart (&head, 1);
  insertStart (&head, 2);
  insertStart (&head, 3);
  insertStart (&head, 4);
  insertStart (&head, 5);
  cout << "Before deletion ";
  display (head);
  deleteSpecific (&head, 5);
  cout << "After deletion ";
  display (head);
  return 0;
}
Output:
1 Inserted
2 Inserted
3 Inserted
4 Inserted
5 Inserted
Before deletion 
Circular Linked List : 
5 4 3 2 1 
After deletion 
Circular Linked List : 
5 4 3 2

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Circular Linked List

  • Introduction to Circular Linked List
    Click Here
  • Circular Linked List Applications
    Click Here
  • Circular Linked List in –
    C | C++ | Java
  • Insertion in Circular Linked List –
    C | C++ | Java
  • Insertion at the beginning–
    C | C++ | Java
  • Insertion at the end –
    C | C++ | Java
  • Insertion at nth position –
    C | C++ | Java
  • Deletion in Circular Linked List –
    C | C++ | Java
  • Deletion from beginning in Circular Linked List –
    C | C++ | Java
  • Deletion from nth position in Circular Linked List –
  • Deletion from end in Circular Linked List –
    C | C++ | Java
  • Insertion and Deletion in Circular Linked List – C | C++ | Java
  • Split a Circular Linked List in two halves –
    C | C++ | Java
  • Count nodes in Circular Linked List –
    C | C++ | Java
  • Sorted Insert In Circular Linked List –
    C | C++ | Java
  • Insertion in the middle in Circular Linked List –
    C | C++ | Java

Circular Linked List