Delete alternate nodes of a Doubly Linked List

Given a doubly linked list which is contain N nodes. Delete every alternative nodes in this linked list which are exist in Even position. Suppose linked list contain following (1,2,3,6,7,8,9,10) node in a sequence.

Before Delete alternate nodes of a Doubly Linked List After Delete alternate nodes of a Doubly Linked List

Hint In this problem head node are not delete. So the idea are, visit first node of linked list and delete next upcoming nodes. In next time iteration visits of next node and remove upcoming next nodes. Repeating this process until last node of linked list.

Here given code implementation process.

//C Program
//Delete alternate nodes of 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*);
void delete_node(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 all alternate nodes 
void delete_node(struct Node*head){
  if(head==NULL){
      printf("Empty linked list\n");
  }else{

      struct Node*temp=head,*hold=NULL;
      signed int flag=0;
      while(temp!=NULL){

        //check deleted node
        if(flag== 1){
            hold=temp;
            //modified pointer values
            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;

            flag=0;
        }else{
          temp=temp->next;
          flag=1;
        }
      }
  }
}

int main(){
  //set node pointer value
  struct Node*head=NULL;

  //Insert element of linked list
  insert(&head,1);
  insert(&head,2);
  insert(&head,3);
  insert(&head,6);
  insert(&head,7);
  insert(&head,8);
  insert(&head,9);
  insert(&head,10);
  printf("Before Delete alternate nodes : ");
  //display all node
  display(head);
  printf("\nAfter Delete alternate nodes :");
  delete_node(head);

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

Output

Before Delete alternate nodes : 
Linked List Elements :  1  2  3  6  7  8  9  10
After Delete alternate nodes :
Linked List Elements :  1  3  7  9
//C++ Program
//Delete alternate nodes of 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();
    
};
//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;
        }
    }

}

//Delete all alternate nodes 
void  DoublyList:: delete_node(){
  if(head==NULL){
     cout<<"Empty linked list\n";
  }else{
     
      Node*temp=head,*hold=NULL;
      signed int flag=0;
      while(temp!=NULL){
        //check deleted node
        if(flag==1){
            hold=temp;
            //modified pointer values
            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;
            flag=0;

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

  }
}


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

  //Insert element of linked list
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(6);
  obj.insert(7);
  obj.insert(8);
  obj.insert(9);
  obj.insert(10);
  cout<<"Before Delete alternate nodes  "<<endl;
    //display all node
  obj.display();
  cout<<"\nAfter Delete alternate nodes "<<endl;
  obj.delete_node();
  //display all node
  obj.display();
  return 0;
}

Output

Before Delete alternate nodes  
Linked List Element : 1 2 3 6 7 8 9 10
After Delete alternate nodes 
Linked List Element : 1 3 7 9
//Java program
//Delete alternate nodes of 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 all alternate nodes 
    public static void  deleteNode(){
       if(head==null){
          //when linked list is empty
          System.out.print("Empty linked list");
       }else{
        Node temp=head, hold=null;
        boolean flag=false;
        while(temp!=null){
          //check deleted node
          if(flag==true){
              hold=temp;
              //modified pointer 
              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;
              flag=false;

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

      }
    }

    public static void main(String[] args) {

        LinkedList obj=new LinkedList();
    
         
          //Insert element of linked list
          obj.insert(1);
          obj.insert(2);
          obj.insert(3);
          obj.insert(6);
          obj.insert(7);
          obj.insert(8);
          obj.insert(9);
          obj.insert(10);
          System.out.println("Before Delete alternate nodes ");
            //display all node
          obj.display();
          System.out.println("\nAfter Delete alternate nodes ");
          obj.deleteNode();
          //display all node
          obj.display();
    }
}

Output

Before Delete alternate nodes 
 Linked List Element :  1  2  3  6  7  8  9  10
After Delete alternate nodes 
 Linked List Element :  1  3  7  9
#Python Program
#Delete alternate nodes of 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 all alternate nodes 
    def deleteNode(self):
        if self.head==None:
            print("Linked List Empty : ")
        else:
            temp=self.head
            flag=False
            while(temp!=None):
                #check deleted node
                if(flag==True):
                    hold=temp 
                    
                    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 
                    flag=False

                else:
                    temp=temp.next 
                    flag=True
            

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

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

    #Create Object of class LinkedList
    obj=LinkedList()
    
    #Insert element of linked list
    obj.insert(1)
    obj.insert(2)
    obj.insert(3)
    obj.insert(6) 
    obj.insert(7) 
    obj.insert(8) 
    obj.insert(9) 
    obj.insert(10) 
    print("Before Delete alternate nodes ") 
    #display all node
    obj.display() 
    print("\nAfter Delete alternate nodes ") 
    obj.deleteNode() 
    #display all node
    obj.display() 

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

Output

Before Delete alternate nodes 
Linked List Elements :  1 2 3 6 7 8 9 10 
After Delete alternate nodes 
Linked List Elements :  1 3 7 9
//C# Program
//Delete alternate nodes of 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 all alternate nodes 
    public void  deleteNode(){
       if(head==null){
          //when linked list is empty
             Console.Write("Empty linked list");
       }else{
         
         
        Node temp=head, hold=null;
        bool flag=false; 
        while(temp!=null){
          //check deleted node
          if(flag==true){
              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;
              flag=false;

          }else{
            flag=true;
            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();
       
        //Insert element of linked list
        obj.insert(1);
        obj.insert(2);
        obj.insert(3);
        obj.insert(6);
        obj.insert(7);
        obj.insert(8);
        obj.insert(9);
        obj.insert(10);
        Console.Write("Before Delete alternate nodes ");
          //display all node
        obj.display();
        Console.Write("\nAfter Delete alternate nodes ");
        obj.deleteNode();
        //display all node
        obj.display();

        
    }
}

Output

Before Delete alternate nodes 
Linked List : 1 2 3 6 7 8 9 10
After Delete alternate nodes 
Linked List : 1 3 7 9

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