Delete all the even nodes of a Circular Linked List

Assume that given linked list are exist integer node value, and we are removing all nodes of this Circular linked list which are contains the values of Even key values.

Suppose we are inserted the following (12, 21, 30, 41, 53, 60, 79, 88) node in a sequence.

Before Remove even key nodes after Remove even key nodes

Before solve this problem consider following test cases.

1) When no element of linked list then display proper message like Empty linked list.

2) When only one element of linked list and this node value are even data. then delete this node and set to head pointer of linked list is NULL.

3) When head node of linked list value is even data. so linked list last node is assigned to new upcoming head node. that means when deleting any of node there are always satisfied the properties of circular linked list.

4) When intermediate node are linked list is Even value node. In this case modified the link of previous nodes next pointer value to upcoming next node.

loop termination condition is important factor of this problem. because linked list are circular so terminate condition is main factor. so terminate loop when next upcoming node are already iterates.

Here given code implementation process.

//C Program 
//Delete Even key nodes of Circular Linked List
#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*);
//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
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*head){

  if(head==NULL){
    printf("\nEmpty 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
      }
    }

  }
}
void del_even(struct Node**head){

  if(*head!=NULL){
    struct Node*temp=*head,
    *prev=NULL,
    *hold=NULL,
    *modifier=NULL;
         

    while(*head!=NULL&& temp!=NULL){
      if(temp->data%2==0){
        //even node
        hold=temp;
      }else{
        //hold address of current node
        prev=temp;
      }
      temp=temp->next;

      if(temp==*head) temp=NULL;
      if(hold!=NULL){
        //delete node found
        if(hold==*head){
          //delete head  node
          if(modifier==NULL){
            modifier=hold->next;
            if(modifier!=NULL){
              //find last node and change last node
              //next pointer
              while(modifier->next!=*head){
                modifier=modifier->next;
              }
              if(*head != (*head)->next){
                *head=(*head)->next;
                 //add last node to new head
                modifier->next=(*head);
              }
              else{
                //single element
                *head=NULL;
              }

            }
          }else{
            *head=(*head)->next;
            modifier->next=(*head);
          }
          
        }
        if(prev!=NULL){
          //delete intermediates nodes
          prev->next=hold->next;
          if(prev->next==*head){
              temp=NULL; //no other element
            }
          }
          hold->next=NULL;
          free(hold);
          hold=NULL;
        }

      }
    }else{
      printf("\n Empty Linked List");
    }
  }
  int main(){
  //create node pointer
    struct Node*head=NULL;
  //insert element of linked list
    insert(&head,12);
    insert(&head,21);
    insert(&head,30);
    insert(&head,41);
    insert(&head,53);
    insert(&head,60);
    insert(&head,79);
    insert(&head,88);

    printf("\n Before Delete Even Nodes");
    //display all node
    display(head);
    printf("\n After Delete Even Nodes");
    del_even(&head);
    display(head);
    return 0;
  }

Output

 Before Delete Even Nodes
 Linked List Element :  12  21  30  41  53  60  79  88
 After Delete Even Nodes
 Linked List Element :  21  41  53  79
//C++ Program 
//Delete Even key nodes of Circular Linked List
#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 del_even();
};
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
      }
    }

  }
}
void CircularList:: del_even(){

  if(head!=NULL){
     Node*temp=head,
    *prev=NULL,
    *hold=NULL,
    *modifier=NULL;
         

    while(head!=NULL&& temp!=NULL){
      if(temp->data%2==0){
        //even node
        hold=temp;
      }else{
        //hold address of current node
        prev=temp;
      }
      temp=temp->next;

      if(temp==head) temp=NULL;
      if(hold!=NULL){
        //delete node found
        if(hold==head){
          //delete head  node
          if(modifier==NULL){
            modifier=hold->next;
            if(modifier!=NULL){
              //find last node and change last node
              //next pointer
              while(modifier->next!=head){
                modifier=modifier->next;
              }
              if(head !=head->next){
                head=head->next;
                 //add last node to new head
                modifier->next=(head);
              }
              else{
                //single element
                head=NULL;
              }

            }
          }else{
            head=head->next;
            modifier->next=head;
          }
          
        }
        if(prev!=NULL){
          //delete intermediates nodes
          prev->next=hold->next;
          if(prev->next==head){
              temp=NULL; //no other element
            }
          }
          hold->next=NULL;
          delete hold;
          hold=NULL;
        }

      }
    }else{
      cout<<"\n Empty Linked List"<<endl;
    }
  }
int main(){
  CircularList obj=CircularList();
  //insert element of linked list
    obj.insert(12);
    obj.insert(21);
    obj.insert(30);
    obj.insert(41);
    obj.insert(53);
    obj.insert(60);
    obj.insert(79);
    obj.insert(88);
    cout<<"Before Delete Even Nodes"<<endl;
    //display all node
    obj.display();
    cout<<"\nAfter Delete Even Nodes"<<endl;
    obj.del_even();
    //display all node
    obj.display();
}

Output

Before Delete Even Nodes
Element of linked list :  12  21  30  41  53  60  79  88
After Delete Even Nodes
Element of linked list :  21  41  53  79
//Java Program to 
//Delete Even key nodes of Circular Linked List
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
  static 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
  static 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;
      }
    }
  }
  static void deleteEven(){

  if(head!=null){
     Node temp=head,
     prev=null,
     hold=null,
     modifier=null;
         

    while(head!=null&& temp!=null){
      if(temp.data%2==0){
        //even node
        hold=temp;
      }else{
        //hold address of current node
        prev=temp;
      }
      temp=temp.next;

      if(temp==head) temp=null;
      if(hold!=null){
        //delete node found
        if(hold==head){
          //delete head  node
          if(modifier==null){
            modifier=hold.next;
            if(modifier!=null){
              //find last node and change last node
              //next pointer
              while(modifier.next!=head){
                modifier=modifier.next;
              }
              if(head !=head.next){
                head=head.next;
                 //add last node to new head
                modifier.next=(head);
              }
              else{
                //single element
                head=null;
              }

            }
          }else{
            head=head.next;
            modifier.next=head;
          }
          
        }
        if(prev!=null){
          //delete intermediates nodes
          prev.next=hold.next;
          if(prev.next==head){
              temp=null; //no other element
            }
          }
          hold.next=null;
          hold=null;
        }

      }
    }else{
      System.out.println("\n Empty Linked List");
    }
  }


  
  public static void main(String[] args) {
    LinkedList obj=new LinkedList();
    //insert element of linked list
    obj.insert(12);
    obj.insert(21);
    obj.insert(30);
    obj.insert(41);
    obj.insert(53);
    obj.insert(60);
    obj.insert(79);
    obj.insert(88);
    System.out.println("Before Delete Even Nodes");
    //display all node
    obj.display();
    System.out.println("\nAfter Delete Even Nodes");
    obj. deleteEven();
    //display all node
    obj.display();
    
  }
}

Output

Before Delete Even Nodes
Circular Linked List Element :  12  21  30  41  53  60  79  88
After Delete Even Nodes
Circular Linked List Element :  21  41  53  79
#Python Insert  linked list node at
#Delete Even key nodes of Circular Linked List
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):
        temp=self.head
        print("Linked list Elements : "),
        while(temp!=None):
            print(temp.data),
            temp=temp.next
            #when find first node
            if(temp==self.head):
                print("\n")
                break

        

    def deleteEven(self):

        if(self.head==None):
            print("Empty Linked List")
        else:
            temp=self.head
            prev=None
            hold=None
            modifier=None
            while(self.head!=None and temp!=None):
                if(temp.data%2==0):
                    #even node
                    hold=temp
                else:
                    #hold address of current node
                    prev=temp

                temp=temp.next

                if(temp==self.head):
                    temp=None
                if(hold!=None):

                    if(hold==self.head):

                        if(modifier==None):

                            modifier=hold.next
                            
                            if(modifier!=None):
                                
                                while(modifier.next!=self.head):
                                    modifier=modifier.next

                                if(self.head !=self.head.next):
                                    self.head=self.head.next
                                    #add last node to new head
                                    modifier.next=self.head
                                  
                                else:
                                    #single element
                                    self.head=None
                                  
                        else:
                            self.head=self.head.next
                            modifier.next=self.head
                    if(prev!=None):
                        #delete intermediates nodes
                        prev.next=hold.next
                        if(prev.next==self.head):
                            temp=None #no other element
                    
                    hold.next=None
                    hold=None

                


def main():
    #Create Object of class CircularList
    obj=CircularList()
    #Insert element
    obj.insert(12)
    obj.insert(21)
    obj.insert(30)
    obj.insert(41)
    obj.insert(53)
    obj.insert(60)
    obj.insert(79)
    obj.insert(88)  
    print("Before Delete Even Nodes")
    #display all node
    obj.display()
    print("After Delete Even Nodes")
    obj.deleteEven()
    #display all node
    obj.display()
if __name__ == '__main__':
    main()

Output

Before Delete Even Nodes
Linked list Elements :  12 21 30 41 53 60 79 88 

After Delete Even Nodes
Linked list Elements :  21 41 53 79 

//C# program to 
//Delete Even key nodes of Circular Linked List
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("\nCircular Linked List : ");
      Node temp=head;
      while(temp!=null){
        Console.Write(" {0}",temp.data);
        temp=temp.next;
        //End of Loop iteration 
        if(temp==head) break;
      }
    }
  }
  public void deleteEven(){

  if(head!=null){
     Node temp=head,
     prev=null,
     hold=null,
     modifier=null;
         

    while(head!=null&& temp!=null){
      if(temp.data%2==0){
        //even node
        hold=temp;
      }else{
        //hold address of current node
        prev=temp;
      }
      temp=temp.next;

      if(temp==head) temp=null;
      if(hold!=null){
        //delete node found
        if(hold==head){
          //delete head  node
          if(modifier==null){
            modifier=hold.next;
            if(modifier!=null){
              //find last node and change last node
              //next pointer
              while(modifier.next!=head){
                modifier=modifier.next;
              }
              if(head !=head.next){
                head=head.next;
                 //add last node to new head
                modifier.next=(head);
              }
              else{
                //single element
                head=null;
              }

            }
          }else{
            head=head.next;
            modifier.next=head;
          }
          
        }
        if(prev!=null){
          //delete intermediates nodes
          prev.next=hold.next;
          if(prev.next==head){
              temp=null; //no other element
            }
          }
          hold.next=null;
          hold=null;
        }

      }
    }else{
      Console.Write("\n Empty Linked List");
    }
  }

  
  static void Main(){

    Program obj=new Program();
    //insert element of linked list
    obj.insert(12);
    obj.insert(21);
    obj.insert(30);
    obj.insert(41);
    obj.insert(53);
    obj.insert(60);
    obj.insert(79);
    obj.insert(88);
    Console.Write("Before Delete Even Nodes");
    //display all node
    obj.display();
    Console.Write("\nAfter Delete Even Nodes");
    obj. deleteEven();
    //display all node
    obj.display();
  }
}

Output

Before Delete Even Nodes
 Circular Linked List :  12 21 30 41 53 60 79 88
After Delete Even Nodes
 Circular Linked List :  21 41 53 79

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