Deletion from Linked List

#c #linkedlist #array

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

Delete from beginning.
Delete from end.
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.

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

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.