Deletion of a Node from the Linked List

86
Advertisement

 

As discussed in an earlier post, Linked List Implementation using Java, Insertion and deletion operation takes O(1) time to execute in the Linked List.

We had already discussed Linked List Insertion Operation in the previous post, You can learn about it here. In this post, we learn about the deletion operation which is followed in the Linked List.

Deletion in Linked List:

Linked List elements are not stored in contiguous memory, and each element(node) points to the next node using a pointer variable so it’s easy to delete any node from the Linked List, we just need to manipulate the Linked List to point the next node which is deleted with the previous node.

There are 3 positions where we can delete the node from the Linked List:

Deleting a Node from the Linked List has 3 cases, we first check if Linked List empty or not is Linked List is empty then we print the Linked List is empty otherwise we delete the specified Node and return the Linked List.

we have the below Dummy Linked List in all the 3 cases:

Dummy Linked List for deletion

Deletion of Node at the beginning of Linked List:
public Node deleteStart(Node head){

        Node temp = head;

        // first we check Linked list is empty or not.
        if (temp == null){
            System.out.println("Linked List is Empty.");
        }else{
            head = temp.next;
        }
        return head;
    }

Demonstration:

This is very easy to delete the node at the beginning. we just only need to manipulate the head node to point the next of the head. but here we are using a temporary temp, we just need to change head = temp.next;

Deletation of the Node at the beginning

 

Deletion of Node at the End of the Linked List:
public Node deleteEnd(Node head){

        Node temp = head;
        Node temp2  = temp;

        // first we check Linked list is empty or not.
        if (temp == null){
            System.out.println("Linked List is Empty.");
        }else{
            
            // first need to travers over the Linked list and reach at the end of the Lonked List.
            while(temp.next!=null){
                temp2 = temp;
                temp = temp.next;
            }
            temp2.next = null;
        }
        return head;
    }

Demonstration:

While deleting the Node at the end we first traverse over the Linked List and reach the end. here we are using another variable that points the previous node of the temp Node. When we reach at the End then we simply use temp2.next = null;

Deletion of the Node at the End

Deletion of the Specified Node from the Linked List:
public Node deleteSpecified(Node head,int ele){

        Node temp = head;
        Node temp2 = temp;

        if(temp == null){
            System.out.println("Linked List is Empty.");
        }else{
            while(temp.next !=null){
                if (temp.data == ele){
                    temp2.next = temp.next;
                    break;
                }else{
                    temp2 = temp;
                    temp = temp.next;
                }
            }
        }
        return head;
    }

Demonstration:

Here also we are using a temporary variable temp2  which points the previous Node of the temp Node.

User Input: 40

Using while loop we traverse over the Linked List and check if temp node has the data is equal to user Input value if it matches with user input then we manipulate the temp2  variable that now points the next Node of the temp.  Here using  temp2.next = temp.next;

Deletion of the Specified Node

Find the below the Whole java code to delete the Node into the Linked List.

Linked list Deletion Operation:

LinkedList.java

public class LinkedList {

    // Node class creates The Linked List Node
    static class Node{
        int data;
        Node next;

        //Constructor creates New Node and store value into data part and
        // set pointer as Null in starting.
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    //Insert Node at the end of the Linked List
    public Node insert(Node head, int ele){
        Node temp = head;

        //Check if Linked List is empty then add node.
        if (temp == null){
            head = new Node(ele);
        }else{
            while(temp.next!=null){
                temp = temp.next;
            }
            temp.next = new Node(ele);
        }

        return head;
    }

    public Node deleteStart(Node head){

        Node temp = head;

        // first we check Linked list is empty or not.
        if (temp == null){
            System.out.println("Linked List is Empty.");
        }else{
            head = temp.next;
        }
        return head;
    }

    public Node deleteEnd(Node head){

        Node temp = head;
        Node temp2  = temp;

        // first we check Linked list is empty or not.
        if (temp == null){
            System.out.println("Linked List is Empty.");
        }else{

            // first need to travers over the Linked list and reach at the end of the Linked List.
            while(temp.next!=null){
                temp2 = temp;
                temp = temp.next;
            }
            temp2.next = null;
        }
        return head;
    }

    public Node deleteSpecified(Node head,int ele){

        Node temp = head;
        Node temp2 = temp;

        if(temp == null){
            System.out.println("Linked List is Empty.");
        }else{
            while(temp.next !=null){
                if (temp.data == ele){
                    temp2.next = temp.next;
                    break;
                }else{
                    temp2 = temp;
                    temp = temp.next;
                }
            }
        }
        return head;
    }

    //Display method to perform display operation
    public void display(Node head){
        Node temp = head;

        if (temp == null){
            System.out.println("Linked List is Empty.");
        }else{
            while(temp.next!=null){
                System.out.print(String.format("%d--->",temp.data));
                temp = temp.next;
            }
            System.out.print(String.format("%d--->NULL",temp.data));
        }
        System.out.println();
    }

}

LinkedListImplementation.java:

import java.util.Scanner;

public class LinkedListImplementation {

    public static void main(String[] args) {

        Scanner scanner  = new Scanner(System.in);

        System.out.println("=================================");

        LinkedList list = new LinkedList();
        LinkedList.Node head = null;

        head = list.insert(head,10);
        head = list.insert(head,20);
        head = list.insert(head,30);
        head = list.insert(head,40);
        head = list.insert(head,50);
        head = list.insert(head,60);

        System.out.println("Dummy Linked List : ");

        list.display(head);

        System.out.println("=================================");

        System.out.println("Deletion of the First Node from the Linked List : ");

        head = list.deleteStart(head);

        list.display(head);

        System.out.println("=================================");

        System.out.println("Deletion of the Last Node from the Linked List : ");

        head = list.deleteEnd(head);

        list.display(head);

        System.out.println("=================================");

        System.out.println("Enter the Number you want to delete : ");
        int deleteEle = scanner.nextInt();

        head = list.deleteSpecified(head,deleteEle);

        System.out.println("Linked List after deleting the Specified Node : ");
        list.display(head);
        System.out.println("=================================");
    }
}

 

Output 1:

=================================
Dummy Linked List : 
10--->20--->30--->40--->50--->60--->NULL
=================================
Deletion of the First Node from the Linked List : 
20--->30--->40--->50--->60--->NULL
=================================
Deletion of the Last Node from the Linked List : 
20--->30--->40--->50--->NULL
=================================
Enter the Number you want to delete : 
40
Linked List after deleting the Specified Node : 
20--->30--->50--->NULL
=================================

 

Hope you like this post.

If you have any doubt please feel free to comment below.

Learn Linked List Implementation using Java

Learn Linked List Insertion Operation

Learn Stack Implementation using LinkedList

Learn Stack implementation using Array

 

You may also learn these to build the Knowledge: