Deletion of node at specific position N in singly link list

Deletion of node at specific position N requires traversing the link list to find the N-1 th node so that we can make it's next pointer points to N+1 th node.
In the process of deletion of node at specific position, first we check whether the list has some nodes and the position N should be less than number of nodes in the list. It would be error to delete the node which doesn't exist in the list.
When deleting the node we come up with the conditions when we will not able to access the N-1 th and N+1 th node for first and last node respectively. These conditions will be handled seperately. So let us see the algorithm to implement deletion of node at specific position below:

Algorithm to delete node at position N:

The alrorithm presented here uses START as pointer to first node and N is the specific position of node that is to be deleted. TEMPs are temporary pointers that is used in deletion process.

Set TEMP = START
If START == NULL or N < 1
- There is no node or invalid position
Else
- if ( N == 1)
  - Set START = START->NEXT
- Else
  - Traverse the list for (N-1)th node using TEMP
  - Set TEMP2 = TEMP->NEXT
  - Set TEMP->NEXT = TEMP->NEXT->NEXT
  - Free (TEMP2)
- End If
End If

Function to delete node at position N:


int deleteAtPosition(NODE **start, int pos){
 NODE *temp = *start, *temp2;
 int info = -1, i;
 if(*start == NULL || pos < 1){
  printf("\nError : List have no node or invalid position");
 }
 else{
  if(pos == 1){
   info = (*start)->info;
   *start = (*start)->next;
   free(temp);
  }
  else if ((*start)->next != NULL){ //node has atleast 2 nodes
   for(i = 2; i < pos; i++){
    temp = temp->next;
    if(temp->next == NULL){
     printf("\nError: Position is greater than node count\n");
     return -1;
    }
   }
   info = temp->next->info;
   temp2 = temp->next;
   temp->next = temp->next->next;
   free(temp2);
  }
  else{
   printf("\nInvalid deletion");
  }
 }
 return info;
}

Program to delete node at position N in the singly link list:


#include <stdio.h>
#include <malloc.h>

struct node{
 int info;
 struct node *next;
};
typedef struct node NODE;

void insertAtFirst(NODE **, int);
int deleteAtPosition(NODE **, int);
void traverse(NODE **);

int main(){
 
 NODE *start = NULL;
 
 insertAtFirst(&start, 4); //4
 insertAtFirst(&start, 5); //5  4
 insertAtFirst(&start, 3); //3  5  4
 traverse(&start);// 3  5  4
 deleteAtPosition(&start,2); //3  4
 printf("\n");
 traverse(&start);// 3  4
 deleteAtPosition(&start,2);// 3
 printf("\n");
 traverse(&start);// 3
 return 0;
}


int deleteAtPosition(NODE **start, int pos){
 NODE *temp = *start, *temp2;
 int info = -1, i;
 if(*start == NULL || pos < 1){
  printf("\nError : List have no node or invalid position");
 }
 else{
  if(pos == 1){
   info = (*start)->info;
   *start = (*start)->next;
   free(temp);
  }
  else if ((*start)->next != NULL){ //node has atleast 2 nodes
   for(i = 2; i < pos; i++){
    temp = temp->next;
    if(temp->next == NULL){
     printf("\nError: Position is greater than node count\n");
     return -1;
    }
   }
   info = temp->next->info;
   temp2 = temp->next;
   temp->next = temp->next->next;
   free(temp2);
  }
  else{
   printf("\nInvalid deletion");
  }
 }
 return info;
}
void insertAtFirst(NODE **start, int info){
 NODE *ptr = (NODE*) malloc(sizeof(NODE));
 ptr->info = info;
 ptr->next = *start;
 *start = ptr;
}

void traverse(NODE **start){
 NODE *temp;
 temp = *start;
 while(temp != NULL){
  printf("%d  ", temp->info);
  temp = temp->next;
 }
}

Output:

3  5  4
3  4
3

The CS Point

Search This Blog