Delete Node in a Linked List

Delete Node in a Linked List

Problem Statement

Given the linked list. The task is to delete the node of the linked list and return the list.

Examples:

Input: 4 -> 5 -> 1 -> 9
Key = 5
Output: 4 -> 1 -> 9 -> NULL
Explanation:

Input: 10 -> 20 -> 30 -> NULL
Key = 20
Output: 10 -> 30 -> NULL

Approach: Iterative

The approach is based on a few observations.

Algorithm

  • If the node to be deleted is the head node, then simply point the head to the second node of the linked list.
  • For all other nodes:
    • Traverse the linked list and for the current node curr, check whether the next node contains the key that needs to be deleted.
      • If true, point curr -> next to curr -> next -> next.
      • Else, keep traversing the list until the end of the linked list.

The following illustration will make the approach more clear.

C++ Code

void deleteNode(struct node ** head, int key) {
  struct node * temp;
  if (( * head) -> data == key) {
    temp = * head;
    * head = ( * head) -> next;
    free(temp);
  } else {
    struct node * current = * head;
    while (current -> next != NULL) {
      if (current -> next -> data == key) {
        temp = current -> next;
        current -> next = current -> next -> next;
        free(temp);
        break;
      } else
        current = current -> next;
    }
  }
}

Java Code

 void deleteNode(int key) {
  Node temp = head, prev = null;
  if (temp != null && temp.data == key) {
    head = temp.next;
    return;
  }
  while (temp != null && temp.data != key) {
    prev = temp;
    temp = temp.next;
  }
  if (temp == null)
    return;
 
  prev.next = temp.next;
}

Python Code

def deleteNode(key):
    temp = head
    if temp is not None:
        if temp.data == key:
            self.head = temp.next
            temp = None
            return
 
    while temp is not None:
        if temp.data == key:
            break
        prev = temp
        temp = temp.next
 
    if temp == None:
        return
 
    prev.next = temp.next
 
    temp = None
  • Time Complexity: O(N), where N is the total nodes of the linked list.
  • Space Complexity: O(1) since no extra space is used.

Practice Question:

FAQs

Q.1: How to delete a node from the end of the linked list?

Ans: If the node to be deleted is at the end of the linked list, traverse till the second last node, say curr, and mark curr -> next = NULL and free the memory.

Q.2: What is the time complexity and space complexity of the iterative approach?

Ans: The time complexity is O(N) and the space complexity is O(1), where N is the total node of the linked list.

Additional Resources

Previous Post

N-ary Tree – Tree Data Structures

Next Post

Difference Between IoT and M2M

Exit mobile version