Circular Linked List Insertion and Deletion in C++
February 18, 2023
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.
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.
ImportantUnlike a singly linked list where the last node points to null, the circular linked list's last node points to the head nmode.
Structure
Following are two possible ways of structure of circular linked list –
#include<iostream>
#include<stdlib.h>
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
Method 2
This method uses class to create linked list structure and internal class methods to operator on circular linked list. Since these are internal class members thus private variables can be used. Thus need not pass head explicitly.
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class LinkedList
{
private:
Node * head;
public:
LinkedList ()
{ // constructor
head = NULL;
}
int getCurrSize ();
void insertStart (int data);
void insertLast (int data);
void insertAfterPos (int pos, int data);
void display ();
};
void LinkedList::insertStart (int data)
{
Node *newNode = new Node ();
newNode->data = data;
// if first node is being inserted
if (head == NULL)
{
head = newNode;
head->next = head;
return;
}
// if had more than 1 node do below
Node *curr = head;
// traverse till last node in cirular Linked List
while (curr->next != head)
{
curr = curr->next;
}
curr->next = newNode;
newNode->next = head;
head = newNode;
}
void LinkedList::insertLast (int data)
{
Node *newNode = new Node ();
newNode->data = data;
// if first node is being inserted
if (head == NULL)
{
head = newNode;
head->next = head;
return;
}
// if cirular Linked List already as >=1 node
Node *curr = head;
// traverse till last node in cirular Linked List
while (curr->next != head)
{
curr = curr->next;
}
// assign cirular Linked List's current last node's next as this new node
curr->next = newNode;
// assign this new node's next as current head of cirular Linked List
newNode->next = head;
}
void LinkedList::insertAfterPos (int pos, int data)
{
int size = getCurrSize ();
if (pos < 0 || size < pos)
{
cout << "Insertion not possible" << pos << " position invalid" << endl;
}
else if (pos == 0)
insertStart (data);
else
{
Node *newNode = new Node ();
newNode->data = data;
Node *temp = head;
// traverse till the node after which you need to
// insert this new node
while (--pos)
temp = temp->next;
// since we need to insert after 3rd node
// this newNode's next will be 3rd node's next i.e. 4th node
newNode->next = temp->next;
// 3rd node's next = this newNode
temp->next = newNode;
}
}
int LinkedList::getCurrSize ()
{
int size = 0;
Node *temp = head;
if (temp == NULL)
return size;
do
{
size++;
temp = temp->next;
}
while (temp != head);
return size;
}
void LinkedList::display ()
{
// if circular linked list is empty currently
if (head == NULL)
return;
Node *temp = head;
// since we need to take care of circular nature of linked list
do
{
cout << temp->data << " ";
temp = temp->next;
}
while (temp != head);
cout << endl;
}
int main ()
{
// first node will be null at creation
LinkedList *list = new LinkedList ();
list->insertStart (18);
list->insertStart (9);
list->display ();
list->insertLast (27);
list->insertLast (45);
list->display ();
//Inserts after 3rd position
list->insertAfterPos (3, 36);
list->display ();
return 0;
}
Output
9 18
9 18 27 45
9 18 27 36 45
Deletion in a Circular Linked List in C++
The below code does Deletion at the following positions –
#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
Method 2
This method uses a class to create a linked list structure and internal class methods to operate on a circular linked list. Since these are internal class members thus private variables can be used. Thus need not pass head explicitly.
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class LinkedList
{
private:
Node * head;
public:
LinkedList ()
{ // constructor
head = NULL;
}
int calcSize ();
void deleteStart ();
void deleteLast ();
void deletePos (int pos);
void display ();
void insert (int data);
};
void LinkedList::deleteStart ()
{
Node *temp = head;
// if there are no nodes in Linked List can't delete
if (head == NULL)
{
cout << "Circular Linked List Empty, deletion not possible\n";
return;
}
// if only 1 node in CLL
if (temp->next == head)
{
head = NULL;
return;
}
Node *curr = head;
// traverse till last node in CLL
while (curr->next != head)
curr = curr->next;
// assign last node's next to 2nd node in CLL
curr->next = head->next;
// move head to next node
head = head->next;
free (temp);
}
void LinkedList::deleteLast ()
{
Node *temp = head;
Node *previous;
// if there are no nodes in Linked List can't delete
if (head == NULL)
{
cout << "Circular Linked List Empty, deletion not possible\n";
return;
}
// if Linked List has only 1 node
if (temp->next == head)
{
head = NULL;
return;
}
// else traverse to the last node
while (temp->next != head)
{
// store previous link node as we need to change its next val
previous = temp;
temp = temp->next;
}
// Curr assign 2nd last node's next to head
previous->next = head;
// delete the last node
free (temp);
// 2nd last now becomes the last node
}
void LinkedList::deletePos (int n)
{
int size = calcSize ();
if (n < 1 || size < n)
{
cout << "Insertion not possible" << n << " position invalid" << endl;
}
else if (n == 1)
deleteStart ();
else if (n == size)
deleteLast ();
else
{
Node *temp = head;
Node *previous;
// traverse to the nth node
while (--n)
{
// store previous link node as we need to change its next val
previous = temp;
temp = temp->next;
}
// change previous node's next node to nth node's next node
previous->next = temp->next;
// delete this nth node
free (temp);
}
}
void LinkedList::insert (int data)
{
Node *newNode = new Node ();
newNode->data = data;
if (head == NULL)
{
head = newNode;
head->next = head;
return;
}
Node *curr = head;
while (curr->next != head)
{
curr = curr->next;
}
curr->next = newNode;
newNode->next = head;
head = newNode;
}
int LinkedList::calcSize ()
{
int size = 0;
Node *temp = head;
if (temp == NULL)
return size;
do
{
size++;
temp = temp->next;
}
while (temp != head);
return size;
}
void LinkedList::display ()
{
// if circular linked list is empty currently
if (head == NULL)
return;
Node *temp = head;
// since we need to take care of circular nature of linked list
do
{
cout << temp->data << " ";
temp = temp->next;
}
while (temp != head);
cout << endl;
}
int main ()
{
// first node will be null at creation
LinkedList *list = new LinkedList ();
list->insert (45);
list->insert (36);
list->insert (27);
list->insert (18);
list->insert (9);
list->insert (0);
list->display ();
list->deleteStart ();
list->display ();
list->deleteLast ();
list->display ();
list->deletePos (3);
list->display ();
return 0;
}
Output
0 9 18 27 36 45
9 18 27 36 45
9 18 27 36
9 18 36
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Login/Signup to comment