Delete all occurrences of a given key in a doubly linked list

Given doubly linked list are containing N nodes of integer values. Here some nodes are contains similar data element. Our goal is to delete each nodes of given linked list which are equal to given value X. Suppose given linked list are containing following nodes data (9,2,3,9,5,6,7,9).

Before delete 9 node occurrences in doubly linked list after delete 9 node occurrences in doubly linked list

Here given code implementation process.

//C Program
//Delete all occurrences of a given key in a doubly linked list
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
  int data;
  struct Node*next;
  struct Node*prev;
};

//function prototype
void insert(struct Node**,int);
void display(struct Node*);

//insert Node element of end of linked list
void insert(struct Node**head,int value){

  //Create a dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(*head==NULL){
      *head=node;
    }else{
        struct Node*temp=*head;
        //find last node
        while(temp!=NULL && temp->next!=NULL){
          temp=temp->next;
        }
        //add new node to last positions
        temp->next=node;
        node->prev=temp;
       
    }
  }
}
//display element of Node
void display(struct Node*temp){
  
  if(temp==NULL){
    printf("Empty linked list");
  }
  else{
    printf("\nLinked List Elements :");
  
    //Traverse doubly linked list from front to rear
    while(temp!=NULL){
      //print node value
      printf("  %d",temp->data);
      temp=temp->next;
    }
  }

}
//delete given occurrence in linked list
void delete_node(struct Node**head,int occurrence){
  if(*head==NULL){
     printf("Empty linked list\n");
  }else{
      struct Node*temp=*head,*hold=NULL;
      while(temp!=NULL){
        //check deleted node
        if(temp->data==occurrence){
            hold=temp;
            if(temp==*head){
              //delete head node of linked list
              *head=temp->next;

            }
            if(temp->next!=NULL){
              temp->next->prev=temp->prev;
            }
            if(temp->prev!=NULL){
              temp->prev->next=temp->next;
            }

            temp=temp->next;
            hold->next=NULL;
            hold->prev=NULL;

            free(hold);
            hold=NULL;


        }else{
          temp=temp->next;
        }
      }
  }
}

int main(){
  //set node pointer value
  struct Node*head=NULL;
  int remove=9;
  //Insert element of linked list
  insert(&head,9);
  insert(&head,2);
  insert(&head,3);
  insert(&head,9);
  insert(&head,5);
  insert(&head,6);
  insert(&head,9);
 
  printf("Before delete node occurrence %d",remove);
    //display all node
  display(head);
  printf("\nAfter delete node occurrence %d ",remove);
  delete_node(&head,remove);

  //display all node
  display(head);
  return 0;
}

Output

Before delete node occurrence 9
Linked List Elements :  9  2  3  9  5  6  9
After delete node occurrence 9 
Linked List Elements :  2  3  5  6
//C++ Program
//Delete all occurrences of a given key in a doubly linked list

#include<iostream> 
using namespace std;
//create structure
struct Node{
    int data;
    Node*next;
    Node*prev;
};
class DoublyList{
    struct Node*head;
    public:
    DoublyList();
    void insert(int);
    void display();
    void delete_node(int);
};
//set inital value
DoublyList::DoublyList(){
    head=NULL;
}

//insert a linked list Node element
void DoublyList:: insert(int value){
    //Create a dynamic node
    Node*node=new Node;
    if(node==NULL){
        cout<<"Memory overflow\n";
    }
    else{
        //set data value
        node->data=value;
        node->next=NULL;
        node->prev=NULL;
        if(head==NULL){
          head=node;
        }else{
            Node*temp=head;
            //find last node
            while(temp!=NULL && temp->next!=NULL){
              temp=temp->next;
            }
            //add new node to last positions
            temp->next=node;
            node->prev=temp;
           
        }
    }
}
//display all element of doubly linked list
void DoublyList::display(){

    if(head==NULL){
        //when linked list is empty
        cout<<"Empty linked list";
    }
    else{
        cout<<"Linked List Element :";
        Node*temp=head;
        while(temp!=NULL){
            //display node elemement
            cout<<" "<<temp->data;
            temp=temp->next;
        }
    }

}
//remove given occurrence
void  DoublyList:: delete_node(int occurrence){
  if(head==NULL){
     cout<<"Empty linked list\n";
  }else{
     
      Node*temp=head,*hold=NULL;
      while(temp!=NULL){
        //check deleted node
        if(temp->data==occurrence){
            hold=temp;
            if(temp==head){
              //delete head node of linked list
              head=temp->next;

            }
            if(temp->next!=NULL){
              temp->next->prev=temp->prev;
            }
            if(temp->prev!=NULL){
              temp->prev->next=temp->next;
            }

            temp=temp->next;
            hold->next=NULL;
            hold->prev=NULL;

            delete hold;
            hold=NULL;


        }else{
          temp=temp->next;
        }
      }

  }
}


int main(){
  DoublyList obj=DoublyList();

  int remove=9;
  //Insert element of linked list
  obj.insert(9);
  obj.insert(2);
  obj.insert(3);
  obj.insert(9);
  obj.insert(5);
  obj.insert(6);
  obj.insert(9);
 
  cout<<"Before delete node occurrence "<<remove<<endl;
    //display all node
  obj.display();
  cout<<"\nAfter delete node occurrence "<<remove<<endl;
  obj.delete_node(remove);
  //display all node
  obj.display();
}

Output

Before delete node occurrence 9
Linked List Element : 9 2 3 9 5 6 9
After delete node occurrence 9
Linked List Element : 2 3 5 6
//java program
//Delete all occurrences of a given key in a doubly linked list
public class LinkedList{

    static class Node{
        int data;
        Node next;
        Node prev;
    }
    //head of linked list
    static Node head;
    //Class constructors
    LinkedList(){
        head=null;
    } 
    //add newly created node at End of linked list
    static void insert(int value){
        //Create a dynamic node
        Node node=new Node();
        //add node value and pointer value
        node.data=value;
        node.next=null;
        node.prev=null;
        //when no element
        if(head==null) head=node;
        else{
          Node temp=head;
          //find last node
          while(temp.next!=null) temp=temp.next;
          //add node
          node.prev=temp;
          temp.next=node;
        }
    }
    //display all Linked List node value
    static void display(){
        if(head!=null){
            System.out.print(" Linked List Element :");
            Node temp=head;
            while(temp!=null){
                //display node value
                System.out.print("  "+temp.data);
                temp=temp.next;
            }
        }else{
            System.out.println("Empty Linked list"); 
        }
    }
  //delete a given occurrence
  public static void  deleteNode(int occurrence){
       if(head==null){
          //when linked list is empty
            System.out.print("Empty linked list");
       }else{
        Node temp=head, hold=null;
        while(temp!=null){
          //check deleted node
          if(temp.data==occurrence){
              hold=temp;
              if(temp==head){
                //delete head node of linked list
                head=temp.next;

              }
              if(temp.next!=null){
                temp.next.prev=temp.prev;
              }
              if(temp.prev!=null){
                temp.prev.next=temp.next;
              }

              temp=temp.next;
              hold.next=null;
              hold.prev=null;

              
              hold=null;


          }else{
            temp=temp.next;
          }
        }

      }
    }



    public static void main(String[] args) {

        LinkedList obj=new LinkedList();
    
          int remove=9;
          //Insert element of linked list
          obj.insert(9);
          obj.insert(2);
          obj.insert(3);
          obj.insert(9);
          obj.insert(5);
          obj.insert(6);
          obj.insert(9);
 
          System.out.println("Before delete node occurrence "+remove);
            //display all node
          obj.display();
          System.out.println("\nAfter delete node occurrence "+remove);
          obj.deleteNode(remove);
          //display all node
          obj.display();
    }
}

Output

Before delete node occurrence 9
 Linked List Element :  9  2  3  9  5  6  9
After delete node occurrence 9
 Linked List Element :  2  3  5  6
#Python Program
#Delete all occurrences of a given key in a doubly linked list
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
        self.prev=None

#create class LinkedList    
class LinkedList:
    def __init__(self):
        #set initial head value
        self.head=None


    #insert new node to end of Linked List  
    def insert(self,data):
        #make a new node
        node=Node(data)

        if(self.head==None):
            #when empty list
            self.head=node
        else:
            temp=self.head
            #find last node
            while temp.next!=None:
                temp=temp.next
            #add node    
            temp.next=node
            node.prev=temp
    #delete a given occurrence        
    def deleteNode(self,occurrence):
        if self.head==None:
            print("Linked List Empty : ")
        else:
            temp=self.head

            while(temp!=None):
                #check deleted node
                if(temp.data==occurrence):
                    hold=temp;
                    if(temp==self.head):
                        #delete head node of linked list
                        self.head=temp.next;

                    
                    if(temp.next!=None):
                        temp.next.prev=temp.prev;
                    
                    if(temp.prev!=None):
                        temp.prev.next=temp.next;
                    

                    temp=temp.next;
                    hold.next=None;
                    hold.prev=None;
                    hold=None;

                else:
                    temp=temp.next;
              
            

    #view all node values    
    def display(self):
        if self.head==None:
            print("Linked List Empty : ")
            return
        temp=self.head
        print("Linked List Elements : ")

        while(temp!=None):
            #print node value
            print(temp.data,end=" ")
            temp=temp.next
        
def main():

    #Create Object of class LinkedList
    obj=LinkedList()
    remove=9;
    #Insert element of linked list
    obj.insert(9);
    obj.insert(2);
    obj.insert(3);
    obj.insert(9);
    obj.insert(5);
    obj.insert(6);
    obj.insert(9);

    print("Before delete node occurrence ",remove);
    #display all node
    obj.display();
    print("\nAfter delete node occurrence ",remove);
    obj.deleteNode(remove);
    #display all node
    obj.display();

if(__name__=="__main__"):
    main()

Output

Before delete node occurrence  9
Linked List Elements : 
9 2 3 9 5 6 9 
After delete node occurrence  9
Linked List Elements : 
2 3 5 6
//C# Program
//Delete all occurrences of a given key in a doubly linked list
using System;
public class Node{
   public  int data;
   public  Node next;
   public Node prev;
}
class Program
{
    public Node head;
    public Program(){
        head=null;
    }
    public void insert(int data){
        //Create a dynamic node
        Node node=new Node();
        //add node value and pointer value
        node.data=data;
        node.next=null;
        node.prev=null;
        //when no element
        if(head==null) head=node;
        else{
          Node temp=head;
          //find last node
          while(temp.next!=null) temp=temp.next;
          //add node
          node.prev=temp;
          temp.next=node;
        }
    }
    //delete a given occurrence
    public void  deleteNode(int occurrence){
       if(head==null){
          //when linked list is empty
             Console.Write("Empty linked list");
       }else{
         
         
        Node temp=head, hold=null;
        while(temp!=null){
          //check deleted node
          if(temp.data==occurrence){
              hold=temp;
              if(temp==head){
                //delete head node of linked list
                head=temp.next;

              }
              if(temp.next!=null){
                temp.next.prev=temp.prev;
              }
              if(temp.prev!=null){
                temp.prev.next=temp.next;
              }

              temp=temp.next;
              hold.next=null;
              hold.prev=null;

              
              hold=null;


          }else{
            temp=temp.next;
          }
        }
      }
    }

    //display linked list node value
    public void display(){
        if(head==null){
            Console.Write("Empty List");
        }else{
            Console.Write("\nLinked List :");
            Node temp=head;
            while(temp!=null){
                //display node value
                Console.Write("  {0}",temp.data);
                temp=temp.next;
            }
            
        }
    }
    
    static void Main()
    {
        Program obj=new Program();
    
        int remove=9;
        //Insert element of linked list
        obj.insert(9);
        obj.insert(2);
        obj.insert(3);
        obj.insert(9);
        obj.insert(5);
        obj.insert(6);
        obj.insert(9);
       
        Console.Write("Before delete node occurrence {0}",remove);
          //display all node
        obj.display();
        Console.Write("\nAfter delete node occurrence {0}",remove);
        obj.deleteNode(remove);
        //display all node
        obj.display();

        
    }
}

Output

Before delete node occurrence 9
Linked List : 9 2 3 9 5 6 9
After delete node occurrence 9
Linked List : 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