Delete a given node from linked list

Delete a node from linked list

Write a program to delete a node from a linked list. For example, in the linked list shown below, if we were asked to delete node 5, the result will be the linked list as shown.

delete node from linked list

delete a node in linked list

To delete a node from the linked list, first, we need to find the node with the given value. We compare given value with the value of each node of the list; if the values match, we found the node to delete. To delete a node in a singly linked list, next pointer of the previous node of current node will point to next node of the current node. previous->next = current->next

However, if we are matching the value of the node with the given value as mentioned above, we don’t have access to the previous node of the current node.

So what shall we do? There are two ways we can solve this problem: First, we compare the value of next of the current node instead of the current node, that way we are at the previous node of the node to be deleted when the match happens. Second, keep track of the previous node while traversing the linked list forward.

The node to be deleted can be anywhere in the linked list, there are three possibilities:

  • Node to be deleted is the head node of linked list.
  • Node to be deleted is any of the middle nodes.
  • Node to be deleted is last node of linked list.
  • In the first case, we should also update head pointer of the linked list. For second and third cases, we can just change the pointers: next of the previous node points to the next of the current node).

    package com.company;
    
    /**
     * Created by sangar on 14.10.18.
     */
    public class LinkedList<T> {
        private Node<T> head;
    
        public LinkedList(){
            head = null;
        }
    
        public void insert(T data){
            //If this is the first node to insert
            if(this.head == null){
                this.head = new Node<>(data);
            }
            else{
                Node current = this.head;
                /* Defensive programming, just in case current is null
                * As we check null condition for head earlier, it should
                * not be null in this while loop ever though
                * */
                while(current != null && current.getNext() != null){
                    current = current.getNext();
                }
                //We are at the last node.
                current.setNext(new Node(data));
            }
        }
    
        public Node<T> get(T data){
            /*
                Base condition if there is no nodes,
                return null
             */
            if(this.head == null){
                return null;
            }
            else{
                Node current = this.head;
                /* Defensive programming, just in case current is null
                * As we check null condition for head earlier, it should
                * not be null in this while loop ever though
                * */
                while(current != null && current.getData() != data){
                    current = current.getNext();
                }
    
                return current;
            }
        }
    
        public void deleteNode(int val){
            Node current = this.head;
            Node prev = null;
    
            while(current != null && (int)current.getData() != val){
                prev = current;
                current = current.getNext();
            }
    
            //Case where node to be deleted is head
            if(current == this.head){
                this.head = this.head.getNext();
                 return;
            }
    
            if(current != null){
                prev.setNext(current.getNext());
            }
            //let the gc free the memory
        }
    
        public void printList(){
            Node current = this.head;
    
            while(current != null){
                System.out.print(" " + current.getData());
                current = current.getNext();
            }
        }
    }
    

    Delete a node from a linked list with a reference

    Above implementation will not work if there are duplicate values in a linked list, we will delete the first node with the given value and it may not be always the node intended to be deleted. What if we were given the pointer or address to the node to be deleted?

    One way is to scan through the linked list and find the node matching the pointer. We can do that by comparing current->next to the pointer given. If they are equal, we can link the current->next = givenNode->next.

    Can we avoid the traversing of the linked list? Yes, we can. We know the pointer to the node, let’s say it is givenNode. If we copy value of givenNode->next node into givenNode->value, we can delete the givenNode->next node. Before deleting the node, we will link givenNode->next = givenNode->next->next.

    delete a node from linked list

    This method will not work if the node to be deleted is the last node of the linked list. In that case, even if we avoid accessing the null node after the last node, we may not be able to touch previous node’s next pointer, which will point to a freed node once we delete the last node.

        public void deleteNode(Node nodeToDelete){
            Node current = this.head;
    
            if(nodeToDelete == null) return;
    
            if(nodeToDelete.getNext() != null){
                //Copy data
                nodeToDelete.setData(nodeToDelete.getNext().getData());
                //Change pointer
                nodeToDelete.setNext(nodeToDelete.getNext().getNext());
            }
            //let the gc free the memory
        }
    

    The complexity of both of the above algorithms to delete a node in a linked list is O(N) where N is the number of nodes in the linked list.

    Please share if there is anything wrong or missing. If you are preparing for an interview, and want to have personalized coaching to guide you through it, please signup here for free interview preparation session.