Deletion in a Linked List | C Program

Singly linked list Deletion

In the singly linked list we can delete the node in the following ways –

Deletion Time Complexity (AVG) Θ(1)
Deletion Time Complexity (Worst) O(1)
Space Complexity O(1)

When we delete the node in the linked list then there are three ways to delete the node as follows.

Deletion operation is easier in the singly linked list.

Efficient memory utilization,i.e no need to pre-allocate memory.

Linear data like a stack, a queue can be easily executed using linked list.

Singly linked list deletion in C++

Deletion at beginning

So in this diagram Node, A  had been deleted, and after delete, the node will be shown in the diagram.

Algorithm

  • Assign next node in a linked list as the new head
  • free previous head
Singly linked list deletion in C++ 1

Deletion at middle

Algorithm

  • Search the Node to be deleted and call it temp
  • Store previous node call is as previous
  • Assign previous->next to temp->next
  • Free(temp)
Singly linked list deletion in C++ 3

Deletion at last

  • Search the Node to be deleted and call it temp
  • Store previous node call is as previous
  • Assign previous->next to temp->next
  • In this case, the temp->next will be Null so no difference from deletion at middle
  • Free(temp)
Singly linked list deletion in C++ 4

Code of deletion in a linked list (For a Value)

Following code takes care of all the 3 cases above i.e. deletion at the start, mid and end for a value in a linked list
Run
#include<stdio.h>
#include<stdlib.h>

struct Node
{
  int data;
  struct Node *next;
};

void delete (struct Node **head, int delVal)
{
  struct Node *temp = *head;
  struct Node *previous;

  //Case when there is only 1 node in the list
  if (temp->next == NULL)
    {
      *head = NULL;
      free (temp);
      printf ("Value %d, deleted \n", delVal);
      return;
    }
  //if the head node itself needs to be deleted
  if (temp != NULL && temp->data == delVal)
    {
      //Case 1 head becomes 30
      *head = temp->next;	//changing head to next in the list

      printf ("Value %d, deleted \n", delVal);
      //case 1: 22 deleted and freed
      free (temp);
      return;
    }

  //run until we find the value to be deleted in the list
  while (temp != NULL && temp->data != delVal)
    {
      //store previous link node as we need to change its next val
      previous = temp;
      temp = temp->next;
    }

  //if value is not present then
  //temp will have traversed to last node NULL
  if (temp == NULL)
    {
      printf ("Value not found\n");
      return;
    }

  // Case 2: (24)->next = 16 (as 20->next = 16) 
  // Case 3: (16)->next = NULL (as 12->next = NULL)
  previous->next = temp->next;
  free (temp);

  //case 2: 20 deleted and freed
  //case 3: 12 deleted and freed
  printf ("Value %d, deleted \n", delVal);
}

void display (struct Node *node)
{

  //as linked list will end when Node is Null
  while (node != NULL)
    {
      printf ("%d ", node->data);
      node = node->next;
    }
  printf ("\n");
}

int main ()
{
  //creating 4 pointers of type struct Node
  //So these can point to address of struct type variable
  struct Node *head = NULL;
  struct Node *node2 = NULL;
  struct Node *node3 = NULL;
  struct Node *node4 = NULL;
  struct Node *node5 = NULL;
  struct Node *node6 = NULL;

  // allocate 3 nodes in the heap 
  head = (struct Node *) malloc (sizeof (struct Node));
  node2 = (struct Node *) malloc (sizeof (struct Node));
  node3 = (struct Node *) malloc (sizeof (struct Node));
  node4 = (struct Node *) malloc (sizeof (struct Node));
  node5 = (struct Node *) malloc (sizeof (struct Node));
  node6 = (struct Node *) malloc (sizeof (struct Node));


  head->data = 22;		// data set for head node 
  head->next = node2;		// next pointer assigned to address of node2 

  node2->data = 30;
  node2->next = node3;

  node3->data = 24;
  node3->next = node4;

  node4->data = 20;
  node4->next = node5;

  node5->data = 16;
  node5->next = node6;

  node6->data = 12;
  node6->next = NULL;

  /*No need for & i.e. address as we do not
     need to change head address
   */
  printf ("Linked List Before Operations : ");
  display (head);

  //deleting first occurance of a value in linked list
  delete (&head, 22);
  delete (&head, 20);
  delete (&head, 12);

  printf ("Linked List After Operations : ");

  display (head);

  return 0;
}

Output

Linked List Before Operations : 22 30 24 20 16 12 
Value 22, deleted
Value 20, deleted
Value 12, deleted
Linked List After Operations : 30 24 16

Code for deletion in a linked list (At Position)

Run
#include<stdio.h>
#include<stdlib.h>

struct Node
{
  int data;
  struct Node *next;
};

int calcSize (struct Node *node)
{
  int size = 0;

  while (node != NULL)
    {
      node = node->next;
      size++;
    }
  return size;
}

void delete (struct Node **head, int pos)
{
  struct Node *temp = *head;
  struct Node *previous;

  //if the head node itself needs to be deleted
  int size = calcSize (*head);

  if (pos < 1 || pos > size)
    {
      printf ("Enter valid position\n");

      return;
    }

  if (pos == 1)
    {
      //Case 1 head becomes 30
      *head = temp->next;	//changing head to next in the list
      printf ("Value %d, deleted \n", temp->data);

      //case 1: 22 deleted and freed
      free (temp);
      return;
    }

  //run until we find the value to be deleted in the list
  while (--pos)
    {
      //store previous link node as we need to change its next val
      previous = temp;
      temp = temp->next;
    }


  // Case 2: (24)->next = 16 (as 20->next = 16) 
  // Case 3: (16)->next = NULL (as 12->next = NULL)
  previous->next = temp->next;
  printf ("Value %d, deleted \n", temp->data);

  free (temp);
  //case 2: 20 deleted and freed
  //case 3: 12 deleted and freed
}

void display (struct Node *node)
{

  //as linked list will end when Node is Null
  while (node != NULL)
    {
      printf ("%d ", node->data);
      node = node->next;
    }
  printf ("\n\n");
}

int main ()
{
  //creating 4 pointers of type struct Node
  //So these can point to address of struct type variable
  struct Node *head = NULL;
  struct Node *node2 = NULL;
  struct Node *node3 = NULL;
  struct Node *node4 = NULL;
  struct Node *node5 = NULL;
  struct Node *node6 = NULL;

  // allocate 3 nodes in the heap 
  head = (struct Node *) malloc (sizeof (struct Node));
  node2 = (struct Node *) malloc (sizeof (struct Node));
  node3 = (struct Node *) malloc (sizeof (struct Node));
  node4 = (struct Node *) malloc (sizeof (struct Node));
  node5 = (struct Node *) malloc (sizeof (struct Node));
  node6 = (struct Node *) malloc (sizeof (struct Node));


  head->data = 22;		// data set for head node 
  head->next = node2;		// next pointer assigned to address of node2 

  node2->data = 30;
  node2->next = node3;

  node3->data = 24;
  node3->next = node4;

  node4->data = 20;
  node4->next = node5;

  node5->data = 16;
  node5->next = node6;

  node6->data = 12;
  node6->next = NULL;

  /*No need for & i.e. address as we do not
     need to change head address
   */
  printf ("Linked List Before Operations : ");
  display (head);

  //deleting first occurance of a value in linked list
  delete (&head, 1);
  delete (&head, 3);
  delete (&head, 4);

  printf ("Linked List After Operations : ");
  display (head);

  delete (&head, -2);		// not valid as pos negative
  delete (&head, 10);		// not valid as breaches size of Linked List
  printf ("Linked List After Operations : ");
  display (head);

  return 0;
}

Output

Linked List Before Operations: 22 30 24 20 16 12

Value 22, deleted
Value 20, deleted
Value 12, deleted
Linked List After Operations: 30 24 16

Enter valid position
Enter valid position
Linked List After Operations: 30 24 16
Deletion in singly Linked List in c meme

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Singly Linked List

  • Introduction to Linked List in Data Structure
  • Linked List in – C | C++ | Java
  • Singly Linked List in – C | C++ | Java
  • Insertion in singly Linked List – C | C++ | Java
    • Insertion at beginning in singly Linked List  – C | C++Java
    • Insertion at nth position in singly Linked List  – C | C++Java
    • Insertion at end in singly Linked List  – C | C++Java
  • Deletion in singly Linked List  – C | C++Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end in singly linked list : C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
  • Linked List Insertion and Deletion – C | C++Java
  • Reverse a linked list by changing links between nodes – C | C++Java
  • Linked List insertion in the middle – C | C++Java
  • Print reverse of a linked list without actually reversing – C |C++ | Java
  • Search an element in a linked list – C | C++Java
  • Insertion in a Sorted Linked List – C | C++Java
  • Delete alternate nodes of a Linked List – C | C++Java
  • Find middle of the linked list – C | C++Java
  • Reverse a linked list in groups of given size – C | C++Java
  • Find kth node from end of the linked list – C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list – C | C++Java
  • Check whether linked list is palindrome or not – C | C++Java
  • Fold a Linked List – C | C++Java
  • Insert at a given position – C | C++Java
  • Delete at a given position – C | C++Java

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • Linked List in –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++Java
  • Insertion at nth position in singly Linked List  –
    C | C++Java
  • Insertion at end in singly Linked List  –
    C | C++Java
  • Deletion in singly Linked List  –
    C | C++Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • Linked List Insertion and Deletion –
    C | C++Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++Java
  • Reverse a linked list by changing links between nodes –
    C | C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Insertion in the middle Singly Linked List –
    C | C++Java
  • Insertion in a Sorted Linked List –
    C | C++Java
  • Delete alternate nodes of a Linked List –
    C | C++Java
  • Find middle of the linked list –
    C | C++Java
  • Reverse a linked list in groups of given size –
    C | C++Java
  • Find kth node from end of the linked list –
    C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list –
    C | C++Java
  • Check whether linked list is palindrome or not –
    C | C++Java
  • Fold a Linked List –
    C | C++Java
  • Insert at given Position –
    C | C++Java
  • Deletion at given Position –
    C | C++Java