Delete a Node from Linked List

A linked list is a linear data structure that consists of nodes where each node has two fields. The first field is the data field, and the second field is the address field, which is a reference(link) to the next node. We can perform various functions in a linked list, like insertion, deletion, searching, sorting, and many more. But in this article, we will talk about how we can delete a node from the linked list.

Introduction

Deletion of a linked list is an easy operation. In a linked list, we can delete a node in three ways:

• Delete from the beginning: For this, just point the node to the second node, i.e., head=head->next.
• Delete from the middle: To delete a node from the middle, just traverse to the node before the node that is to be deleted (called the prev node). And after that, link the next pointer of the prev node to the next pointer of the node to be deleted.
• Delete from the end: In the deletion of a node from the end, just traverse to the second last node and make the next pointer of this last node NULL, and free the node.

Now, let’s understand the above three operations in much more detail.

Delete from a Linked List

As we have discussed in the introduction section, we can delete a node from the linked list in three ways. Let’s discuss them one by one in detail.

Beginning:

Deleting a node from the beginning of the linked list is the simplest operation that we can perform in the linked list. Let’s suppose we have a linked list and the head pointer is pointing to the first node of the linked list.

In this case, we want to delete the first node, so we have created a pointer (in our case, it’s a temp pointer) that will point to the first node of the linked list. Now, we’ll move our head pointer to the right so it can point to the next node, which is the linked list’s second node.

But, why is this step required? Because we have to delete a node from the linked list where the temp pointer is pointing, i.e., the first node.

Let’s understand it with some visualization given below.

• As you can see in the below image, the head pointer is pointing to the first node i.e., the node to be deleted. 
  

• Now, we will create a new pointer temp, and it will also point to the first node of the linked list.

• At last, we will move our head pointer to the next node i.e., the second node of the linked list, and our temp pointer will stay at the first node so
  
  that we can delete the first node easily using the temp pointer.
  
  

• At last, delete the node pointed by temp

End:

For deleting the end node of the linked list, we could have two scenarios:

1. If the linked list has only one node and that node has to be deleted.
2. Or, there are more than one node in the linked list and the last node has to be deleted.

Let’s discuss both the scenarios one by one:

In the first scenario:

Initially, the head will be pointing to the first node of the linked list, and since we have only one node, we have NULL in the head->next. We’ll make a new pointer (in our case it is temp) that will also point to the head of the linked list, and finally, we will free this pointer. See the below statement to delete the node from the linked list.

temp=head
head=NULL
free(temp)

In the second scenario:

Now, in this scenario, we have more than one node in a linked list. So first we have to traverse the linked list and reach the last node. We will also keep track of the previous node, i.e., the second last node of the linked list. For this, we will use two pointers, say temp1 and temp2. temp1 will point to the last node, whereas temp2 will point to the second last node of the linked list.

See the below statement to delete the node from the linked list.

temp1=head
while temp1->next is not equal to NULL
	do 
	 temp2=temp1
	 temp1=temp1->next

After the above statement executes, temp1 will point to the last node whereas temp2 will point to the second last node of the linked list. Now, we want, the next of temp2 to point to the NULL and the last node of the linked list that is pointed by the pointer temp1 to become free.

temp2->next=NULL
free(temp1)

Let’s understand it with some visualization given below.

• In the below image, the head and temp1 pointers are pointing to the first node of the linked list.

• Now, we will traverse the linked list using the temp1 pointer and also keep track of the previous node, as we have already discussed above.
• You can see that pointer temp1 is pointing to the last node of the linked list, while the temp2 pointer is pointing to the second last node of the linked list.

• Using this statement: temp2->next = NULL, the next of the temp2 pointer becomes NULL, and this will become the last node of the linked list. And finally, we will free the temp1 pointer.

Middle

• Firstly, check whether the given position is in the range [1, size of the linked list].
• Traverse till the (pos-1)th node.
• Change the next pointer of the (pos-1)th node to the (pos+1)th node.
• Lastly, free the pos’th node.

Let’s have a look at the proper visualization:

In the below image, you can see that two new pointers, previous and current, are pointing to the head of the linked list. The previous pointer will point to the node just before the node is deleted. And the current pointer will point to the node to be deleted.

Now, we will move our current pointer so that it can point to the node that is to be deleted. See the below image.

When our current pointer and previous pointer move to their positions. We will only have to link the next of the previous node with the next of the current node and at last free the current pointer.

previous->next  = current->next
free(current)

Problem statement

You are given a singly linked list. Your task is to delete a node from the linked list and return the list.

Example

Input: head = [2, 6, 4, 5], node = 6
Output: [2, 4, 5]
Explanation: Since, you have to delete the 2nd node i.e., node with value 6. So, when we delete this node, 
the final linked list will be 2->4->5. 

Approach 1 – Iterative

Algorithm

1. If the head of the linked list is the node to be deleted, then simply make the head node point to the next node, i.e., the second node of the linked list.
2. Otherwise, for the current node, check whether the next node is the node to be deleted. And if it is yes, then make the current->next=current->next->next and free the memory of the deleted node. Else update the current node to the next and do this process till the last node hits.

Code Implementation

C++

void deleteNode(Node **head_ref, int key){

    // Store the head node in the current variable
    Node *current = *head_ref;
    Node *prev = NULL;

    // If the head node is itself the key to be deleted
    if (current != NULL && current->data == key){
        *head_ref = current->next; // Changed the head to the current->next
        delete current;            // free the old head
        return;
    }

    // Search for the key to be deleted and also keep track of the previous node
    else{
        while (current != NULL && current->data != key){
            prev = current;
            current = current->next;
        }

        // If the key to be deleted is not present in the linked list
        if (current == NULL)
            return;

        // Key is found, so unlink the current node
        prev->next = current->next;

        // Delete the current node
        delete current;
    }
}

Java

void deleteNode(int key) {
    // Store the head node in the current variable
    Node current = head, previous = null;

    // If the head node is itself the key to be deleted
    if (current != null && current.data == key) {
      head = current.next;
      return;
    }
    // Search for the key to be deleted and also keep track of the previous node
    while (current != null && current.data != key) {
      previous = current;
      current = current.next;
    }
    // If the key to be deleted is not present in the linked list
    if (current == null)
      return;
    
    // Key is found, so unlink the current node
    previous.next = current.next;
  }

Python

def deleteNode(self, key):
    # Store head node in the current variable
    current = self.head

    # If the head node is itself the key to be deleted
    if current is not None:
        if current.data == key:
            self.head = current.next
            current = None
            return
    # Search for the key to be deleted and also keep track of the previous node
    while current is not None:
        if current.data == key:
            break
        prev = current
        current = current.next

    # If the key to be deleted is not present in the linked list
    if current == None:
        return

    # Key is found, so unlink the current node
    prev.next = current.next
    current = None

Output:

Given Linked List: 2 6 4 5
Linked List after Deletion of 6: 2 4 5

Time Complexity:

O(N), where N is the total nodes in the linked list. We need to go through the linked list, so the time complexity will be linear.

Space Complexity:

O(1), only a head and some additional pointers are used for the implementation, so the space will be constant.

Approach 2 – Recursive Method

Algorithm

1. First, we will find the position of the node in the linked list.
2. We recursively reduce the value of k (k is the node to be deleted).
3. When k reaches 1, we delete the current node and return the next current node as a new node.
4. When the function returns, we link the returned node to the next previous node.

Code Implementation

C++

// Deletes k-th node and returns new header.
Node *deleteNode(Node *head, int k){
    if (k < 1)
        return head;

    // If a linked list is empty
    if (head == NULL)
        return NULL;

    // Base case
    if (k == 1){
        Node *res = head->next;
        delete (head);
        return res;
    }
    // Decreases k and call the function for the next node
    head->next = deleteNode(head->next, k - 1);
    return head;
}

Java

static Node deleteNode(Node head, int k) 
{ 
    if (k < 1) 
    return head; 
  
    // If a linked list is empty 
    if (head == null) 
    return null; 
  
    // Base case
    if (k == 1) 
    { 
        Node res = head.next; 
        return res; 
    } 
    // Decreases k and call the function for the next node
    head.next = deleteNode(head.next, k-1); 
    return head; 
}

Python

# Deletes k-th node and returns new header.
def deleteNode(head, k):

    if (k < 1):
        return head

    # If a linked list is empty
    if (head == None):
        return None

    # Base case
    if (k == 1):
        res = head.next
        return res
        
    # Decreases k and call the function for the next node
    head.next = deleteNode(head.next, k - 1)
    return head

Output:

Given Linked List: 2 6 4 5
Linked List after Deletion of 6: 2 4 5

Time Complexity:

O(n), same as the iterative solution, because we have to go through the linked list once.

Space Complexity:

O(n), we have to call the function recursively for every next node, so for each node, the cost of call stacks is linear.

Conclusion

So, it’s time to conclude our topic “delete a node from a linked list” by discussing some of the important points. So, let’s see them one by one.

• We can perform various functions in a linked list, like insertion, deletion, searching, sorting, and many more.
• In a linked list, we can delete a node from the list in three ways: delete from the beginning, delete from the middle, and delete from the end.
• If we want to delete the first node of the linked list, then we will move the current head from the 1st node to the next node and delete the first node using the free method.
• If we want to delete the middle node of the linked list, first check whether the given position is in the range [1, size of the linked list], then continue until you reach the (pos-1)th node, and now change the next pointer from the (pos-1)th node to the (pos+1)th node. Lastly, free the pos’th node.
• If we want to delete the last node of the linked list, then first we have to traverse the linked list and reach the last node. We will also keep track of the previous node, i.e., the second last node of the linked list.