Delete a node at kth Position in Circular Linked List

Today we will discuss how to delete a node at kth position in circular linked list. But if you are unfamiliar with the concepts of circular linked list then please refer to this link . Suppose you have a circular linked list 1->2->3->4 and 4 pointing to 1. Let k=2 then we have to delete the second node. After deletion the list should be 1->3->4 and 4 pointing to 1. Now, let's discuss the procedure:

Procedure

1. First we will make a circular linked list.

2. Then we will traverse the list until we reach the node which is just previous to the kth node.

3. Now we will update the pointer of this previous node with the address of the node next to kth node.

Delete a node at kth Position in Circular Linked List

4. If the value of 'k' is 1 then we have to delete the first node. While doing so we will traverse till last node and then we will update the pointer of this node with the address of the node next to 1st node. But we will also have to update the head pointer because if the first node is deleted then second node will now be the first node.

Code

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* next;
};
struct node* head=NULL;

class linked
{

public:
    void insert(int x)
    {
        struct node* temp=new node();
        temp->data=x;
        temp->next=NULL;
        if(head==NULL)
        {
            head=temp;
        }
        else
        {
            struct node* temp1=head;
            while(temp1->next!=NULL)
            {
                temp1=temp1->next;
            }
            temp1->next=temp;

        }
    }

    void assignhead()
    {
        struct node* temp=head;
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }
        temp->next=head;
    }


    void Delete(int k)
    {
        if(k!=1)
        {
            struct node* temp=head;
            int c=1;
            while(c<k-1)
            {
                temp=temp->next;
                c++;
            }
            temp->next=temp->next->next;
        }
        else
        {
            struct node* temp=head;
            while(temp->next!=head)
            {
                temp=temp->next;
            }
            head=temp->next->next;
            temp->next=temp->next->next;
        }
    }

    void disp()
    {
        struct node* temp=head;
        cout<<temp->data<<" ";
        temp=temp->next;
        while(temp!=head)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        cout<<endl;
    }
};

int main()
{
    linked l;
    l.insert(3);
    l.insert(5);
    l.insert(8);
    l.insert(1);
    l.insert(-2);
    l.insert(7);
    l.insert(-3);
    l.insert(11);
    l.insert(0);
    l.insert(6);
    l.assignhead();
    l.disp();
    int k;
    cout<<"enter position you want to delete: "<<endl;
    cin>>k;
    l.Delete(k);
    l.disp();
    return 0;
}

Explanation of code

1. First we will write a simple code of circular linked list which will have 3 functions:

- insert() - which will insert elements in the circular linked list.
- assignhead() - to make a link between last and first node.
- disp() - which will display the circular linked list.

2. Insert some values in the circular linked list.

3. Now we have created a function named Delete() to delete a node at kth the circular linked list. It has a parameter 'k' which tells us about the position of the node to be deleted.

4. First we have checked if 'k' is not equals to 1 because if we have divided out problem into 2 parts. If the node which is to be deleted is the first node or any other node.

5. If 'k' is not equal to 1 then we have created a pointer to node variable 'temp' which is pointing to head. We have also created a variable 'c' which is a counter to traverse the list till the node which is just previous to kth node.

if(k!=1)
{
struct node* temp=head;
int c=1;

---

}

6. Then we have created a while loop which will iterate the list till we reach the node which is just previous to kth node.

while(c<k-1)
{
temp=temp->next;
c++;
}

7. Then we have updated the next pointer of temp with the next pointer of the kth node because the node just previous to kth node shall point to the node which is next to the kth node. (kth node is not physically deleted from the list, we have just changed the pointers so that it shall not come in the output screen ).

temp->next=temp->next->next;

8. Now we have reached the else part which will be executed if k is equal to 1 or if we want to delete the first node.

9. We have again created a pointer to node variable 'temp' which is pointing to head.

else
{
struct node* temp=head;

---

}

10. Then we have created a while loop which will iterate the list till we reach the last node whose next pointer is pointing to the first node again.

while(temp->next!=head)
{
temp=temp->next;
}

11. Then we have updated the head and assigned it the address of the node next to first node.

head=temp->next->next;

12. Then we have updated the next pointer of temp with the address of the node next to kth node . (kth node is not physically deleted from the list, we have just changed the pointers so that it shall not come in the output screen ).

temp->next=temp->next->next;

Delete a node at kth Position in Circular Linked List

Procedure

Code

Explanation of code

Contact Form