Deletion a node from Circular Linked List

Suppose we are inserted the following (1,2,3,4,5,6) node in a sequence.

Before delete node After delete node value 4

Here given code implementation process.

//C Program 
//delete a given node in Circular Linked List Nodes
#include<stdio.h>
#include <stdlib.h> //for malloc function

//Create structure
struct Node{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
void delete_node(struct Node**,int);
//insert Node element at end of linked list
void insert(struct Node**head,int value){
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    node->data=value;
    node->next=*head;
    if(*head==NULL){
      *head=node;
      node->next=*head;
    }else{
      struct Node*temp=*head;
      while(temp->next!=*head){
        temp=temp->next;
      }
      //Add node at last position
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*head){
  
  if(head==NULL){
    printf("Empty linked list");
  }
  else{
    printf("\n Linked List Element :");
    struct Node*temp=head;
    while(temp){
      printf("  %d",temp->data);
      temp=temp->next;
      if(temp==head){
        break; //terminate loop
      }
    }

  }
}
//delete a given node from circular linked list
void delete_node(struct Node**head,int node_value){
  if(*head==NULL){
    printf("Empty linked list");
  }
  else{
     struct Node*temp=*head,*prev=NULL;

    if(temp->data==node_value){
      //delete head of circular list
      if(temp->next==temp){
        //only one element of circular list
        *head=NULL;
        free(temp);
        temp=NULL;
      }else{
        
        //find last node
        while(temp->next!=*head){
          temp=temp->next;
        }
        temp->next=(*head)->next;
        prev=*head;
        *head=prev->next;
        free(prev); //remove first node
        prev=NULL;

      }
    }
    else{
      //find deleted node
      while(temp->next!=*head){
        if(temp->data==node_value){
          //if deleted node found
          prev->next=temp->next;
          free(temp);
          temp=NULL;
          prev=NULL;
          break;
        }
        prev=temp;
        temp=temp->next;
      }
      if(temp!=NULL){
        printf("\nNot Found Deleted Node ");
      }
    }
  }
}
int main(){

  //create node pointer
  struct Node*head=NULL;
  int node_data=4;
  //insert element of linked list
  insert(&head,1);
  insert(&head,2);
  insert(&head,3);
  insert(&head,4);
  insert(&head,5);
  insert(&head,6);

  printf("\n Before delete node : %d",node_data);
  //display all node
  display(head);

  printf("\n After delete  node : %d",node_data);
  delete_node(&head,node_data);
  //display all node
  display(head);
}

Output

 Before delete node : 4
 Linked List Element :  1  2  3  4  5  6
 After delete  node : 4
 Linked List Element :  1  2  3  5  6
//C++ Program 
//delete a given node in Circular Linked List Nodes
#include<iostream>
using namespace std;

//create structure
struct Node{
    int data;
    struct Node*next;
};
class CircularList{
    Node *head;
public:
    CircularList();
    void insert(int);
    void display();
    void delete_node(int);
};
CircularList::CircularList(){
    head=NULL;
}

//insert Node at end of linked list 
void CircularList:: insert(int value){
  //Create dynamic node
  struct Node*node=new Node;
  if(node==NULL){
    cout<<"Memory overflow"<<endl;
  }else{
    node->data=value;
    node->next=head;
    if(head==NULL){
      //when linked list empty
      head=node;
      node->next=head;
    }else{
      Node*temp=head;
      //find last node
      while(temp->next!=head){
        temp=temp->next;
      }
      //Add node at last
      temp->next=node;
    }
  }
}
//display element of Node
void CircularList:: display(){

    if(head==NULL){
        cout<<"Empty linked list";
    }
    else{
        cout<<"Element of linked list :";
        struct Node*temp=head;
        while(temp){
            cout<<"  "<<temp->data;
            temp=temp->next;
            if(temp==head){
                break; //terminate loop
            }
        }

    }
}
//delete a given node from circular linked list
void  CircularList:: delete_node(int node_value){
  if(head==NULL){
    cout<<"Empty linked list";
  }
  else{
    Node*temp=head,*prev=NULL;

    if(temp->data==node_value){
      //delete head of circular list
      if(temp->next==temp){
        //only one element of circular list
        head=NULL;
        delete temp;
        temp=NULL;
      }else{
        
        //find last node
        while(temp->next!=head){
          temp=temp->next;
        }
        temp->next=(head)->next;
        prev=head;
        head=prev->next;
        delete prev; //remove first node
        prev=NULL;

      }
    }
    else{
      //find deleted node
      while(temp->next!=head){
        if(temp->data==node_value){
          //if deleted node found
          prev->next=temp->next;
          delete temp;
          temp=NULL;
          prev=NULL;
          break;
        }
        prev=temp;
        temp=temp->next;
      }
      if(prev!=NULL){
        cout<<"Delete node not found"<<endl;
      }
    }
  }
}
int main(){
  CircularList obj=CircularList();
  int node_value=4;
  //insert element of linked list
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(4);
  obj.insert(5);
  obj.insert(6);
  cout<<"Before delete node :"<<node_value<<endl;
  //display all node
  obj.display();
  cout<<"\nAfter delete node :"<<node_value<<endl;
  obj.delete_node(node_value);
  obj.display();
}

Output

Before delete node :4
Element of linked list :  1  2  3  4  5  6
After delete node :4
Element of linked list :  1  2  3  5  6n
//Java Program to 
//Delete a given node in Circular Linked List Nodes
public class LinkedList{
  static class Node{
    int data;
    Node next;
  }
  static Node head;
  //Class constructors
  LinkedList(){
    head=null;
  } 
  //insert node at last of linke list
   void insert(int value){
    //Create a node
    Node node=new Node();
    node.data=value;
    node.next=head;
    if(head==null){
      head=node;
      node.next=head;
    }
    else{
      Node temp=head;
      //find lase node
      while(temp.next!=head){
        temp=temp.next;
      }
      //add node
      temp.next=node;
    }
    
  }
  //Display node element of circular linked list
  public void display(){
    if(head==null){
      System.out.println("Empty Linked List");
    }else{
      System.out.print("Circular Linked List Element :");
      Node temp=head;
      while(temp!=null){
        System.out.print("  "+temp.data);
        temp=temp.next;
        if(temp==head) break;
      }
    }
  }
//delete a given node from circular linked list
public void deleteNode(int node_value){
  if(head==null){
     System.out.print("Empty linked list");
  }
  else{
    Node temp=head, prev=null;

    if(temp.data==node_value){
      //delete head of circular list
      if(temp.next==temp){
        //only one element of circular list
        head=null;
        temp=null;
      }else{
        
        //find last node
        while(temp.next!=head){
          temp=temp.next;
        }
        temp.next=(head).next;
        prev=head;
        head=prev.next;
        prev=null;

      }
    }
    else{
      //find deleted node
      while(temp.next!=head){
        if(temp.data==node_value){
          //if deleted node found
          prev.next=temp.next;
          temp=null;
          prev=null;
          break;
        }
        prev=temp;
        temp=temp.next;
      }
      if(prev!=null){
         System.out.print("Delete node not found");
      }
    }
  }
}

  
  public static void main(String[] args) {
    LinkedList obj=new LinkedList();
    //insert linked list nodes
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    System.out.println("Before Delete");
    obj.display();
    System.out.println("\nAfter Delete");
    obj.deleteNode(4);
    obj.display();
    
  }
}

Output

Before Delete
Circular Linked List Element :  1  2  3  4  5  6
After Delete
Circular Linked List Element :  1  2  3  5  6
#Python Program
#delete a given node in Circular Linked List Nodes
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

#create class CircularList    
class CircularList:
    def __init__(self):
        #Assign default value
        self.head=None

    #Insert new node to End of Linked list  
    def insert(self,data):
        node=Node(data)
        node.next=self.head
        if(self.head==None):
            #when no element of linked list
            self.head=node
            node.next=node
        else:
            temp=self.head
            while(temp.next!=self.head):
                temp=temp.next
            #add node    
            temp.next=node    
    #display all element of circular linked list      
    def display(self):
        if(self.head==None):
            print("Empty Linked List")
            return

        temp=self.head
        print("Linked list Elements : ")
        while(temp!=None):
            print(temp.data,end=" ")
            temp=temp.next
            #when find first node
            if(temp==self.head):
                break

        print("\n")

    #delete a given node
    def deleteNode(self,node_value):
        if(self.head==None):
            print("Empty Linked List")
        else:
            temp=self.head
            prev=None

            if(temp.data==node_value):
              #delete head of circular list
              if(temp.next==temp):
                #only one element of circular list
                head=None
                temp=None

              else:
                #find last node
                while(temp.next!=self.head):
                  temp=temp.next
               
                temp.next=(self.head).next
                prev=self.head
                self.head=prev.next
                prev=None

            else:
              #find deleted node
              while(temp.next!=self.head):
                if(temp.data==node_value):
                  #if deleted node found
                  prev.next=temp.next
                  temp=None
                  prev=None
                  break
               
                prev=temp
                temp=temp.next
             
              if(prev!=None):
                 print("Delete node not found")
             
     


def main():
    #Create Object of class CircularList
    obj=CircularList()
    node_value=4
    #Insert element
    obj.insert(1)
    obj.insert(2)
    obj.insert(3)
    obj.insert(4)
    obj.insert(5)
    obj.insert(6)
    print("Before Delete node ",node_value)
    obj.display()
    print("After Delete node ",node_value)
    obj.deleteNode(node_value)
    obj.display()
if __name__ == '__main__':
    main()

Output

Before Delete node  4
Linked list Elements : 
1 2 3 4 5 6 

After Delete node  4
Linked list Elements : 
1 2 3 5 6 

Python - delete node from circular linked list
//C# program 
//delete a given node in Circular Linked List Nodes
using System;
//node class
public class Node{
  public  int data;
  public  Node next;
}
class Program
{
  public Node head;
  public Program(){
    head=null;
  }
  //insert node of linked list
  public void insert(int data){
    Node newNode=new Node();
    newNode.data=data;
    newNode.next=head;
    if(head==null){
      //when no element of linked list
      head=newNode;
      newNode.next=head;
    }
    else{
      Node temp=head;
      //get last node
      while(temp.next!=head ){
        temp=temp.next;
      }
      //add new node
      temp.next=newNode;
    }
  }
  //Display element of linked list
  public void display(){
    if(head==null){
      Console.Write("Empty Linked List");
    }else{
      Console.Write(" Circular Linked List : ");
      Node temp=head;
      while(temp!=null){
        Console.Write(" {0}",temp.data);
        temp=temp.next;
        //End of Loop iteration 
        if(temp==head) break;
      }
    }
  }
  //delete a given node from circular linked list
public void deleteNode(int node_value){
  if(head==null){
     Console.Write("Empty linked list");
  }
  else{
    Node temp=head, prev=null;

    if(temp.data==node_value){
      //delete head of circular list
      if(temp.next==temp){
        //only one element of circular list
        head=null;
        temp=null;
      }else{
        
        //find last node
        while(temp.next!=head){
          temp=temp.next;
        }
        temp.next=(head).next;
        prev=head;
        head=prev.next;
        prev=null;

      }
    }
    else{
      //find deleted node
      while(temp.next!=head){
        if(temp.data==node_value){
          //if deleted node found
          prev.next=temp.next;
          temp=null;
          prev=null;
          break;
        }
        prev=temp;
        temp=temp.next;
      }
      if(prev!=null){
         Console.Write("Delete node not found");
      }
    }
  }
}

  static void Main(){

    Program obj=new Program();
    int remove_node=4;
   //insert element of linked list
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    Console.Write("Before Delete {0}",remove_node);
    obj.display();
    Console.Write("\nAfter Delete {0}",remove_node);
    obj.deleteNode(remove_node);
    obj.display();
  }
}

Output

Before Delete 4 Circular Linked List :  1 2 3 4 5 6
After Delete 4 Circular Linked List :  1 2 3 5 6


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved