Deletion from Linked List
Tags: c, linkedlist, array
Published: 2022-05-30 14:10:59

There are three possibilities of deleting a node from a linked list :

1. Delete from beginning.
2. Delete from end.
3. Delete from specified  position.

To understand the process of deleting a node from a linked list, you must have the knowledge of creating and displaying the linked list. To know the implementation of linked list [click here](https://www.coderlogs.com/post/627a4309752339739aa908d9/implementation-of-Linked-List-in-C--).

Lets assume that the linked list is already created as shown in fig below,

![image](https://i.ibb.co/CJ9x736/IMG-20220512-150607.jpg)

**Fig.1 Linked list**

## 1. Deleting a node from beginning :

* To delete a first node from the list, make the pointer `temp` to point to the first node by copying the `head` pointer to the pointer `temp`.

* Copy the address part of the first node to which `temp` is pointing  into the `head` by accessing the structure member `next`. This creates a link from `head` to the second node in the list.

* Now the link for the first node to which `temp` is pointing is broken so free that memory space using function `free(temp)`.

* Display the linked list after deletion.

```
void deleteFromBeg(struct node ** head)
{
    struct node *temp;
    temp = *head;
    *head = temp->next;
    free(temp);
}
```

##  2. Deleting a  node from end :

* Make `temp` to point first node in the list.

* Take one pointer `prevnode` of type `struct node` to point previous node in the list.

* Move `temp` till last node using while loop and each time copy the `temp` into `prevnode`. When `temp` points last node, `prevnode` points last but one node.

* Now, break the link of the last node from the list to which `temp` is pointing by updating  the address part of the node to which pointer `prevnode` is pointing to `zero` as it has to be the last node in the list.

* Free the node pointing to by the `temp` using `free(temp)` and display the linked list.

```
void deleteFromEnd(struct node **head, struct node *temp)
{
    struct node *prevnode;
    temp = *head;
    while(temp->next != 0)
    {
        prevnode = temp;
        temp = temp->next;
    }
    if(temp == *head)
        *head = 0;
    else
         prevnode->next = 0;
         free(temp);     
}
```

## 3. Deleting a node from specified position :

* Enter the position after which a node is to be inserted in the list and store that position value into any variable of type `int`.  Here, position variable is taken as `pos`. 

* If  `pos` (entered position) is greater than the number of nodes in the linked list, then print `invalid position`. 

* If  `pos` (entered position) is less than the number of nodes in the linked list then, make `temp` to point first node.

* Move `temp` from first node to that node whose position is `pos-1` using while loop.

* Take one pointer `nextnode` of type `struct node` and make it to point to the node(which you want to delete) by copying the address part of the node pointing to by `temp`.

**Note : `temp` is pointing to the node  just before the node you want to delete.**

* To delete a node from the list, create a link from the node just before the node you want to delete to the node immediate after that specified position's (`pos`)node. The link is created as,      


```
temp->next = nextnode->next;
```

* Free the `nextnode` which is pointing to the node you want to delete and display the linked list.
 

```
void deleteFromPos(struct node *head, struct node *temp, int count)
{
    struct node *nextnode;
    int pos, i=1;
    printf("Enter the position : ");
    scanf("%d", &pos);
    if(pos>count)
    {
        printf("Invalid position.");
        exit(0);
    }
    else
    {
      temp = head;
      while(i < pos-1)
      {
        temp=temp->next;
        i++;
      }
      nextnode = temp->next;
      temp->next = nextnode->next;
      free(nextnode);
    } 
}
```

## C code that demonstrates the deletion from linked list :

```
#include <stdio.h>
#include <stdlib.h> 
 
struct node
{
    int data;
    struct node * next;
};
 
int displayLL(struct node * head)
{
    int num = 0;
    struct node * temp;
    temp = head;
    temp=head;
    while(temp!=0)
    {
       printf("%d ",temp->data);
       temp = temp->next;
       num++;
    }
return num;
}
 
void deleteFromBeg(struct node * * head)
{
    struct node * temp;
    temp = * head;
    * head = temp->next;
    free(temp);
}
 
void deleteFromEnd(struct node **head, struct node *temp)
{
    struct node *prevnode;
    temp = *head;
    while(temp->next != 0)
    {
        prevnode = temp;
        temp = temp->next;
    }
    if(temp == *head)
        *head = 0;
    else
         prevnode->next = 0;
      free(temp);     
}
 
void deleteFromPos(struct node *head, struct node *temp, int count)
{
    struct node *nextnode;
    int pos, i=1;
    printf("Enter the position : ");
    scanf("%d", &pos);
    if(pos>count)
    {
        printf("Invalid position.");
        exit(0);
    }
    else
    {
       temp = head;
       while(i < pos-1)
       {
          temp=temp->next;
          i++;
       }
       nextnode = temp->next;
       temp->next = nextnode->next;
       free(nextnode);
    } 
}
 
int main()
{
   struct node *head = 0, *newnode, *temp; 
   int n, choice, newdata;
 
// Create Linked List // 
 
   printf("Enter the number of nodes in the list : ");
   scanf("%d", &n);
   for(int i = 1; i<=n; i++)
   {
     newnode = (struct node *)malloc(sizeof(struct node));
     printf("Enter the data%d : ", i);
     scanf("%d", &newnode->data);
     newnode->next = 0;
     if(head == 0)
     {
        head = temp = newnode;
     } 
     else
       { 
        temp->next = newnode;
        temp = newnode;
       }
    }
   printf("--------------------------------\n");
   printf("Linked list : ");
   int count = displayLL(head);
   printf("\nCount = %d", count);
 
   printf("\nEnter '1' for deleting node from beginning.\nEnter '2' for deleting node from end.\nEnter '3' for deleting after given position.\n");
   scanf("%d", &choice);
 
   switch(choice)
   {
      case 1:
      {
         deleteFromBeg(&head);
         printf("\nLinked list after deleting a node from beginning : ");
         int count = displayLL(head);
                 break;
      }
      case 2:
      {
         deleteFromEnd(&head, temp);
         printf("\nLinked list after deleting a node from end : ");
         int count = displayLL(head);
                 break;
      }
      case 3:
      {
         deleteFromPos(head, temp, count);
         printf("\nLinked list after deleting a node from specified pos : ");
         int count = displayLL(head);
                 break;
      }
   }
}
```

I own a website www.coderlogs.com where in I write similar blogs so do visit this website for more such blog posts.