Circular Linked List Insertion and Deletion in C++

C++ Program for Ciruclar Linked List Insertion and Deletion

We will look at different ways to do insertion or deletion in a circular linked list in C++ at different possible positions.

circular C++

A circular Linked List is a collection of connected nodes, where each node has the following –

  • Data value
  • Next Pointer

Important pointers

  • Each node is connected to the next node in the chain as the next pointer of each node has the address to the next node in the chain.
  • The first node in the chain is called the head node and the last node has the address of the first (head) node thus the linked list becomes circular in nature.

Structure

Following are two possible ways of structure of circular linked list –

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

Possible places to insert/delete in a Circular Linked List in C++

We will write the code for all the following –

  • At Start
  • At End
  • After a position/At a position
Circular Linked List insertion and deletion in c++

Insertion in a Circular Linked List in C++

The below code does insertion at the following positions –

  • At start
  • At end
  • After a certain node
This method uses class to create Node and external functions to operate on Circular Linked List
Run
#include<iostream>
using namespace std;

// structure for Circular Linked List
struct Node
{
  int data;
  struct Node *next;
};

int calcSize (struct Node *head);

void insertStart (struct Node **head, int data)
{
  struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
  newNode->data = 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->data << " 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->data << " Inserted\n";

  // previous head node becomes 2nd node
}
void insertSpecific(struct Node **head,int num, int pos)//function to insert element at specific position
{
    struct Node *newnode, *curNode;
    int i;

    if(*head == NULL)
    {
        cout<<"List is empty"; } else { newnode = (struct Node *)malloc(sizeof(struct Node)); newnode->data = num;
        curNode = *head;
        for(i=0; i<=pos-3; i++) { curNode = curNode->next;
        }
        newnode->next = curNode->next;
        curNode->next = newnode;
    }
} 
void insertEnd (struct Node **head, int num1)	//function to insert element at end 
{
  struct Node *p;
  struct Node *temp = (struct Node *) malloc (sizeof (struct Node));
  temp->data = num1;
  p = *head;
  while (p->next != *head)
    {
      p = p->next;
    }
  p->next = temp;
  temp->next = *head;
}

void display (struct Node *head)
{
  // if there are no node in CLL
  if (head == NULL)
    return;

  struct Node *temp = head;
  cout << "\nLinked List : ";

  //need to take care of circular structure of CLL
  do
    {
      cout << temp->data << " "; temp = temp->next;

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

int main ()
{

  // 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);

  display (head);
  cout<<"After insertion at end";
  insertEnd(&head,7);
  display(head);
  cout<<"After insertion at position 2:";
  insertSpecific(&head,4,2);
  display(head);

  return 0;
}

Output

1 Inserted
2 Inserted
3 Inserted
4 Inserted
5 Inserted

Linked List : 5 4 3 2 1 
After insertion at end
Linked List : 5 4 3 2 1 7 
After insertion at position 2:
Linked List : 5 4 4 3 2 1 7 

Deletion in a Circular Linked List in C++

The below code does Deletion at the following positions –

  • At start
  • At end
  • Deletion of nth node
This method uses class to create Node and external functions to operate on 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 deleteEnd (struct Node **head)	//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 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);

  display (head);
  deleteBegin(&head);

  cout<<"After deletion from beginning";
  display(head);

  deleteSpecific (&head, 3);
  cout << "After deletion from position 3";
  display (head);

  deleteEnd(&head);
  cout<<"After deletion from the end";
  display(head);

  return 0;
}

Output

1 Inserted
2 Inserted
3 Inserted
4 Inserted
5 Inserted

Circular Linked List : 
5 4 3 2 1 
After deletion from beginning
Circular Linked List : 
4 3 2 1 
After deletion from position 3
Circular Linked List : 
4 3 1 
After deletion from the end
Circular Linked List : 
4 3

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