Delete a Node from linked list without head pointer

Problem Statement

The problem “Delete a Node from linked list without head pointer” states that you have a linked list with some nodes. Now you want to delete a node but you don’t have its parent node address. So delete this node.

Example

2->3->4->5->6->7
Node to be deleted: 4

2->3->5->6->7

Explanation: Since we wanted to delete the node with value 4. We removed it from the linked list and are left with a list that is mentioned in the output.

Approach to delete node without head pointer

Linked List is a linear data structure that has a huge advantage over an array is that it can vary in size. If you want to add an element in a linked list, you can add it in O(1) time. Considering that you are inserting the element in the first place. But if you had to do the same in a normal array. It will cost you O(N) time to do so. Thus it is favorable to use a linked list over an array in real-world applications. And linked list achieves all of this because it does not store the data as a contiguous chunk. It stores each element at some random location. But then how does it maintain order? The answer to this question is, the linked list takes the usage of the pointer. Each node points to another node in the linked list and this way we do not have to allocate a single chunk changing which in turn would have required many computations.

If head pointer was given

Now the problem asks us to delete a node. Generally, we are given a node’s address and are required to delete the next node in the linked list. But here we are required to delete a node whose address is given to us. One way to solve this problem is to first traverse the whole linked list. Then store the parent of each node and break the loop when you are at a node that is provided as input. This way in the end we have the parent of the node to be deleted. So now the problem is changed to the simple deletion of a node in the linked list whose parent’s address is given. But doing this will cost us O(N) operations. But this way can be used only when you have the head pointer.

Solution

The approach for the problem “Delete a Node from linked list without head pointer” would be to swap the data of the node to be deleted and the next node in the linked list. Each node in the linked list stores which node is next. So this operation has only O(1) time complexity. Now when the data has been swapped. Once again, we have changed the problem to the deletion of the node whose parent’s address is given. So now it’s easier for us to solve the problem. But there is one edge case when we have to delete the end node but we won’t be able to delete that. Because there is no next node.

Code

C++ code to delete a node without head pointer

#include <bits/stdc++.h>
using namespace std;

struct node{
  int data;
  node* next;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

void deletedNode(node* &head, node* toBeDeleted){
  if(toBeDeleted == NULL)
    return;
  else{
    if(toBeDeleted->next == NULL){
      cout<<"Last node can't be freed";
    }
    // store or swap but ( the data of current node will be deleted)
    toBeDeleted->data = toBeDeleted->next->data;
    toBeDeleted->next = toBeDeleted->next->next;
  }
}

int main(){
  // create a linked list
  node* head = new node();
  head = create(2);
  head->next = create(3);
  node* toBeDeleted = create(4);
  head->next->next = toBeDeleted;
  head->next->next->next = create(5);
  head->next->next->next->next = create(6);
  head->next->next->next->next->next = create(7);

  cout<<"Old Linked List: ";
  node* tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
  deletedNode(head, toBeDeleted);

  cout<<endl<<"New Linked List: ";
  tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
}

Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 5 6 7

Java code to delete a node without head pointer

import java.util.*;
class node{
  int data;
  node next;
}
 
class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.next = null;
    return tmp;
  }
 
  static node deletedNode(node head, node toBeDeleted){
    if(toBeDeleted == null)
      return null;
    else{
      if(toBeDeleted.next == null){
        System.out.print("Last node can't be freed");
        return null;
      }
      // store or swap but ( the data of current node will be deleted)
      toBeDeleted.data = toBeDeleted.next.data;
      toBeDeleted.next = toBeDeleted.next.next;
      return head;
    }
  }
 
  public static void main(String[] args){
    // create a linked list
    node head = new node();
    head = create(2);
    head.next = create(3);
    node toBeDeleted = create(4);
    head.next.next = toBeDeleted;
    head.next.next.next = create(5);
    head.next.next.next.next = create(6);
    head.next.next.next.next.next = create(7);
 
    System.out.print("Old Linked List: ");
    node tmp = head;
    while(tmp != null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
    head = deletedNode(head, toBeDeleted);
 
    System.out.print("\n"+"New Linked List: ");
    tmp = head;
    while(tmp!=null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
  }
}

Old Linked List: 2 3 4 5 6 7 
New Linked List: 2 3 5 6 7

Complexity Analysis

Time Complexity

O(1), because swapping can be down in constant time. And then we just change some pointers which is again a constant time operation.

Space Complexity

O(1), because the variables which we have used do not depend on the number of nodes in the linked list. Thus space complexity is also constant.