Linked List Implementation(to delete a head node, tail node & node in middle of linked list)

The nodes of a linked list can be deleted by using the following functions depending on the element in the list to be deleted.


1. To delete a head node
2. To delete a tail node
3. To search & delete a node somewhere between head and tail

Consider the following Linked list

4->3->2->1

Here, I've used Insertion function to insert nodes in the head node.

Function to delete a head node:

Step 1: Check for empty list

Step 2: If the list is non-empty, store the head node address in temp

Step 3: Make the head pointer to point to next node

Step 4: free the temp node, which is head node

Implementation:

void deletehead(struct node **head) { if((*head)!=NULL) { struct node *temp=(*head); (*head)=(*head)->next; free(temp); } }

Output:

3->2->1  

Function to delete a tail node:

Step 1: If the list has only one element, free that node and make the head pointer to point to NULL

Step 2: Else, Traverse the list until we reach the tail node besides keep track of previous node

Step 3: If we reach the tail node, make the previous node to point to NULL

Step 4: free the tail node

Implementation:

void deletetail(struct node **head) { struct node *temp=*head; struct node *current=*head; if((*head)->next==NULL) { free(*head); (*head)=NULL; } else { while(current->next!=NULL) { temp=current; current=current->next; } temp->next=NULL; free(current); } }

Function to delete a node somewhere between head and tail node:

Step 1: Check for Empty list

Step 2: Traverse the non-empty list and keep previous pointer and current pointer

Step 3: Compare the data with the values in the list, If any of the node's data matches, make the previous pointer to point to current's next node

Step 4: Copy the current pointer

Step 5: Move the current pointer to point to next node or NULL

Step 6: free the copied current node, which is the node to be deleted

Step 7: Else, if the value of the list doesn't matches with the data to be deleted, store the previous node and move the current pointer to next node

Implementation:

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

See the following code for Complete Implementation to delete the nodes in head, tail and in middle of the linked list:

#include <stdio.h> #include <malloc.h> #include <stdlib.h> struct node { int data; struct node *next; }; struct node* newnode(int data) { struct node *temp=(struct node*)malloc(sizeof(struct node)); temp->data=data; return temp; } void insert(struct node **head,int data) { if((*head)==NULL) { (*head)=newnode(data); (*head)->next=NULL; } else { struct node *temp; temp=newnode(data); temp->next=(*head); (*head)=temp; } } void printlist(struct node *head) { while(head!=NULL) { printf("%d ",head->data); head=head->next; } } void deletehead(struct node **head) { if((*head)!=NULL) { struct node *temp=(*head); (*head)=(*head)->next; free(temp); } } void deletetail(struct node **head) { struct node *temp=*head; struct node *current=*head; if((*head)->next==NULL) { free(*head); (*head)=NULL; } else { while(current->next!=NULL) { temp=current; current=current->next; } temp->next=NULL; free(current); } } void deletevalue(struct node **head,int data) { struct node *current=*head; struct node *prev=*head; struct node *temp; if((*head)!=NULL) { while(current!=NULL) { if(current->data==data) { prev->next=current->next; temp=current; current=current->next; free(temp); } else { prev=current; current=current->next; } } } else return; } int main(void) { struct node *head=NULL; insert(&head,1); insert(&head,2); deletehead(&head); insert(&head,3); insert(&head,4); deletetail(&head); deletevalue(&head,3); printlist(head); return 0; }