Java program for deletion in doubly linked list

Java Program for Deletion in Doubly Linked List

Now Since we’ve already learnt enough about the Insertion Operation in a Doubly Linked List, let’s learn about the Deletion operation. We have three kinds of deletion in singly linked list in the same way we have three kinds of deletion in doubly linked list are as follows:

  • Deletion at the beginning of the linked list.
  • Deletion at Nth node/in middle of the linked list.
  • Deletion at the end of the linked list.

 

Deletion in Doubly linked List in Java

Deletion from the Beginning of a Doubly Linked List

For deletion at the beginning first we have to create a linked list and have to check if the list is empty or not. If it is empty then both head and tail points towards the new node . if it is not empty then we can delete our first node very easily.

Algorithm

  • if (head == null) // if ended loop closed
  • make ptr = head
  • make head = head->next
  • make head->prev = NULL
  • free the pointer node
  • END.
Deletion of a node from beggining in a doubly linked list

Deletion from the Specific Position of a Doubly Linked List

Deleting the nth node is as simple as it was in singly linked list. For deleting the node on nth node we have to go through the same process of deletion in beginning but there is a slight change this time we have to delete the nth node. So when you insert a function of deletion it should be for nth node.

Algorithm

  • if (head == null) // if ended
  • make temp = head so we can freely move our pointer
  • temp->data= node
  • make temp = temp->next  // loop ended
  • Make pointer ptr = temp->next
  • temp->next = ptr->next
  • make ptr->next->prev = temp
  • free temp node
  • END
Deletion of specific node in doubly Linked List

Deletion from the End of a Doubly Linked List

Here we have to delete the node from the end. It requires the traversing of list in order to reach the last node of the doubly linked list and after that we can run loop to delete a node from the end of the doubly linked list.

Algorithm.

  • (head == null)  then return.
  • make temp = head
  • while temp ->next != NULL
  • make temp = temp->next // [loop ended]
  • make temp->previous->next = NULL
  • Free temp node
  • Return
Deletion of end node in Doubly linked list

Java code for deletion in a doubly linked list

   public class PrepInsta
    {  
        //Constitiute a node of the doubly linked list  
        class Node{  
            int data;  
            Node prev;  
            Node next;  
            public Node(int data) {  
                this.data = data;  
            }  
        }  
    // Function to traverse and print the linked list
    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + "–>");
            // Set temp to point to the next node
            temp = temp.next;
        }
        System.out.println("END");
    }
    //Constitiute the head and tail of the doubly linked list  
    Node head, tail = null;  
    //appendAtEnd function will add a node to the end of the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
        //Check if the list is empty  
        if(head == null) {  
            //Both head and tail will point towards the newNode  
            head = tail = newNode;  
            //head's previous will point towards null  
            head.prev = null;  
            //tail's next will point towards null, as it is the last node of the list  
            tail.next = null;  
        }  
        //Append newNode as new tail of the list  
        else {  
            //newNode will be added after tail such that tail's next will point to newNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.prev = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
    }
    public void deleteInitial() {  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        else {  
            //testing for the presence of a single node in the list, If not, Then head and tail will be re-directed
            if(head != tail) {  
                head = head.next;  
            }  
            //if only one node exist both head and tail will be redirected to null
            else {  
                head = tail = null;  
            }  
        }  
    }  
    
    public void deleteLast() {  
        if(head == null) {  
            return;  
        }  
        else {  
            if(head != tail) {  
                tail = tail.prev;  
                tail.next = null;  
            }  
            else {  
                head = tail = null;  
            }  
        }
    }
    public void deletenth(int n) { 
        if(head == null) {  
            return;  
        }  
        else { 
            Node current = head;  
            int pos =n;   
            for(int i = 1; i < pos; i++){  
                current = current.next;  
            }  
            if(current == head) {  
                head = current.next;  
            }  
            else if(current == tail) {  
                tail = tail.prev;  
            }  
            else {  
                current.prev.next = current.next;  
                current.next.prev = current.prev;  
            }  
            //Delete the middle node  
            current = null;  
        }  
    }  
    //print() will print the nodes of the doubly linked list 
      void print() {  
        //Node current will point to head  
        Node curr = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }
        while(curr != null) 
           {  
            //Prints each node by increasing order of the pointer   
            System.out.print(curr.data + " ");  
            curr = curr.next;  
            }  
        System.out.println();  
        }  
    public static void main(String[] args) {  
        PrepInsta dList = new PrepInsta(); 
        dList.addNode(10);  
        dList.addNode(20);  
        dList.addNode(30);
        dList.addNode(40);
        dList.addNode(50);
        System.out.println("Initial Doubly Linked List: "); 
        dList.print();
        dList.deleteInitial();
        System.out.println("Doubly Linked List after Deletion from Beginning: "); 
        dList.print();  
        dList.deleteLast();
        System.out.println("Doubly Linked List after Deletion from End: "); 
        dList.print();  
        dList.deletenth(2);
        System.out.println("Doubly Linked List after Deletion from Nth Position: "); 
        dList.print();          
    }  
}
Initial Doubly Linked List: 
10 20 30 40 50 
Doubly Linked List after Deletion from Beginning: 
20 30 40 50 
Doubly Linked List after Deletion from End: 
20 30 40 
Doubly Linked List after Deletion from Beginning: 
20 40

Queue using Array

Here we have already learned implementation of Queues using Stack in C , click the button below to learn the implementation of queue using array