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;
};
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
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;

class Node
{
    public:
    int data;
    Node *next;
};

int getCurrSize(Node* head);

void insertStart(Node** head, 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 insertLast(Node** head, 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 insertAfterPos(int pos, int data, Node** head){
    int size = getCurrSize(*head);
    
    if(pos < 0 || size < pos) { 
        cout << "Insertion not possible" << pos << " position invalid" << endl; 
    } 

    else if(pos == 0) 
        insertStart(head, 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 getCurrSize(Node* head){
    int size = 0;
    Node* temp = head;

    if(temp == NULL)
        return size;

    do{
        size++;
        temp = temp->next;
        
    }while(temp!=head);
    
    return size;
}

void display(Node* head){
    // 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    
    Node* head = NULL;
    
    insertStart(&head,18);
    insertStart(&head,9);

    display(head);
    
    insertLast(&head, 27);
    insertLast(&head, 45);
    
    display(head);
    
    //Inserts after 3rd position
    insertAfterPos(3,36,&head);
    
    display(head);
  
    return 0;
}

Output

9 18 
9 18 27 45 
9 18 27 36 45
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

This method uses class to create Node and external functions to operate on Circular Linked List

Run
#include<iostream>
using namespace std;

class Node
{
    public:
    int data;
    Node *next;
};

int calcSize(Node* head);

void deleteStart(Node** head){
    
    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 deleteLast(Node** head){ 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 deletePos(Node** head, int n){ int size = calcSize(*head); if(n < 1 || size < n) { cout << "Insertion not possible" << n << " position invalid" << endl;
}

else if(n == 1)
deleteStart(head);

else if(n == size)
deleteLast(head);

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 insert(Node** head, 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 calcSize(Node* head){ int size = 0; Node* temp = head; if(temp == NULL) return size; do{ size++; temp = temp->next; }while(temp!=head); return size; } void display(Node* head){ // 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 Node* head = NULL; insert(&head,45); insert(&head,36); insert(&head,27); insert(&head,18); insert(&head,9); insert(&head,0); display(head); deleteStart(&head); display(head); deleteLast(&head); display(head); deletePos(&head, 3); display(head); return 0; }

Output

0 9 18 27 36 45 
9 18 27 36 45 
9 18 27 36 
9 18 36 
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