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.
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.
Important
Unlike 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 –
With Struct
With Class
With Struct
struct Node{
int data;
struct Node *next;
};With Class
class Node{
public:
int data;
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
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
Method 1
Method 2
Method 1
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
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.
Run
#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 –
- At start
- At end
- Deletion of nth node
Method 1
Method 2
Method 1
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
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.
Run
#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
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
Circular Linked List
- Introduction to Circular Linked List
Click Here - Circular Linked List Applications
Click Here - Circular Linked List in –
- Insertion in Circular Linked List –
- Insertion at the beginning–
- Insertion at the end –
- Insertion at nth position –
- Deletion in Circular Linked List –
- Deletion from beginning in Circular Linked List –
- Deletion from nth position in Circular Linked List –
- Deletion from end in Circular Linked List –
- Insertion and Deletion in Circular Linked List – C | C++ | Java
- Split a Circular Linked List in two halves –
- Count nodes in Circular Linked List –
- Sorted Insert In Circular Linked List –
- Insertion in the middle in Circular Linked List –
Circular Linked List
- Introduction to Circular Linked List
- Circular Linked List Applications
- Circular Linked List in – C | C++ | Java
- Insertion in Circular Linked List – C | C++ | Java
- Deletion in Circular Linked List – C | C++ | Java
- Insertion and Deletion in a 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
Login/Signup to comment