Delete a Node without head pointer from the linked list

Delete a Node without head pointer from the linked list

This article will explain how to delete a node without a head pointer from the linked list. We have given a singly linked list and the node's reference, which needs to be deleted. We do not have any information about the starting address or head pointer. We need to write a function to delete that node from the linked list, and it should not be the first node of the linked list.

Method

It is easy to solve this problem if we have given the head pointer of the linked list. Because for deletion of the node, we must know the previous node pointer, and we can reach to desire node, which needs to be deleted by traversing from the head pointer, but this is not possible in this case.

So, for the deletion of that node, we need to copy the data of the next node to the data field of the current node that we are going to delete. Then, the next node has become the current node, and the current node has become the previous node. Now, we will delete the current node by our traditional delete method.

Algorithm for deleting the node without head pointer from the linked list:

 void delete(struct node * curr)
 {
     struct node * temp = curr;
     curr -> info = curr -> next -> info;
     curr -> next = curr -> next -> next;
 } 

Defination of structure of a node is as follows:

 struct node {
     int info;
     struct Node* next;
 }; 

C program to delete a node without head pointer from the linked list.

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node *next;
 };
 struct node *start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
  struct node *t, *p;
  t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
  start = t;
  start -> info = item;
  start -> next = NULL;
  return;
 }
 else
 {
 struct node *p = start;
 while(p -> next != NULL)
 {
  p = p -> next;
 }
  p -> next = t;
  p = p -> next;
  p -> info = item;
  p -> next = NULL;
  }
 }
 // For deleting the node without head pointer from the linked list
 void delete(struct node * curr)
 {
     struct node * temp = curr;
     curr -> info = curr -> next -> info;
     curr -> next = curr -> next -> next;
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d -> ", t -> info);
                         t = t -> next;
                         }
                         printf("%d\n", t -> info);
 }
 // Driver Function
 int main()
 {
     int i;
     for (i = 2; i < 12; i+=2)
     {
         add(i);
     }
     printf("Before deletion:");
     traverse(start);
     delete(start -> next -> next -> next);
     printf("After deletion:");
     traverse(start);
     return 0;
 } 

Output

Time complexity: The time complexity of this method is O(1), which is constant time.