Deletion in Linked List

Deletion of the linked list can occur in different parts of the list. Some cases are:

  1. Beginning of the linked list.
  2. End of the linked list.
  3. Given position in the linked list.

Let’s take a look at the schedule for each of these cases.

1. Deletion at beginning of the linked list:

  • To remove the first node (primary node), copy the primary node to a temporary node.
  • Make the second node the primary node.
  • Now delete the temporary node.

Deletion

head = head->next;

For example:

Deletion

Deletion

Deletion

Deletion

Here Code:

#include <stdio.h>
#include <stdlib.h>
struct node {
          int data;
          struct node *next;
}*head;
void createList(int n);
void deletion_beginning();
void displayList();
int main()
{
          int n, data, pos;
          printf("\nEnter the total number of nodes: ");
          scanf("%d", &n);
          if(n == 0)
          {
                   printf("Empty List\n");
                   exit(0);
          }
          else
          {
                   createList(n);
          }
          printf("\nThe List is \n");
          displayList();
          deletion_beginning();
          printf("\n\nAfter Deleting the first node, the List is\n");
          displayList();
          return 0;
          }
          void createList(int n)
          {
                   struct node *newNode, *temp;
                   int data, i;
                   head = (struct node *)malloc(sizeof(struct node));
                   if(head == NULL)
                   {
                             printf("Unable to allocate memory.");
                   }
                   else
                   {
                             printf("\nEnter the data of node 1: ");
                             scanf("%d", &data);
                             head->data = data;
                             head->next = NULL;
                             temp = head;
                   for(i=2; i<=n; i++)
                   {
                             newNode = (struct node *)malloc(sizeof(struct node));
                             if(newNode == NULL)
                             {
                                      printf("Unable to allocate memory.");
                                      break;
                             }
                             else
                             {
                             printf("\nEnter the data of node %d: ", i);
                             scanf("%d", &data);
                             newNode->data = data;
                             newNode->next = NULL;
                             temp->next = newNode;
                             temp = temp->next;
                             }
                   }
          }
}
void deletion_beginning()
{
          if(head == NULL)
          printf("\n The list is Empty\n");
          struct node *temp;
          temp = head;
          head = head -> next;
          free(temp);
}
void displayList()
{
          struct node *temp;
          if(head == NULL)
 {
          printf("List is empty.");
 }
else
{
          temp = head;
          while(temp != NULL)
          {
                   printf("%d\t", temp->data);
                   temp = temp->next;
          }
          printf("\n");
          }
}

2. Deletion at end of the linked list:

  • To remove the last node, start looping through the list from the parent node and continue scrolling until the address part of the node is null.
  • Track the penultimate node with a temporary variable such as prev_node.
  • If address part of node NULL, set address part of previous node to NULL and remove last node.

Deletion

struct node* temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
temp->next = NULL;

For example:

Deletion

Deletion

Deletion

Deletion

Here Code:

#include <stdio.h>
#include <stdlib.h>
struct node {
          int data;
          struct node *next;
}*head;
void createList(int n);
void deletion_end();
void displayList();
int main()
{
          int n, data, pos;
          printf("\nEnter the total number of nodes: ");
          scanf("%d", &n);
          createList(n);
          printf("\nThe List is \n");
          displayList();
          deletion_end();
          printf("\n\nAfter Deleting the last node, the List is\n");
          displayList();
          return 0;
}
void createList(int n)
{
          struct node *newNode, *temp;
          int data, i;
          head = (struct node *)malloc(sizeof(struct node));
          if(head == NULL)
          {
                   printf("Unable to allocate memory.");
          }
          else
          {
                   printf("\nEnter the data of node 1: ");
                   scanf("%d", &data);
                   head->data = data;
                   head->next = NULL;
                   temp = head;
          for(i=2; i<=n; i++)
          {
                   newNode = (struct node *)malloc(sizeof(struct node));
          if(newNode == NULL)
          {
                   printf("Unable to allocate memory.");
                   break;
          }
          else
          {
          printf("\nEnter the data of node %d: ", i);
          scanf("%d", &data);
          newNode->data = data;
          newNode->next = NULL;
          temp->next = newNode;
          temp = temp->next;
          }
          }
}
}
void deletion_end()
{
          if(head -> next == NULL)
          {
          free(head);
          head = NULL;
          }
          struct node *temp = head,*prev_node;
          while(temp -> next != NULL)
          {
                   prev_node = temp;
                   temp = temp -> next;
          }
          free(temp);
          prev_node -> next = NULL;
          }
          void displayList()       
          {
                   struct node *temp;
                   if(head == NULL)
                   {
          printf("List is empty.");
          }
          else
          {
                   temp = head;
          while(temp != NULL)
          {
                   printf("%d\t", temp->data);
                   temp = temp->next;
          }
          printf("\n");
          }
}

3. Deletion at given position in the linked list:

  • Now suppose you need to remove the node at position 2.
  • Start scrolling through the list from the main node and move to that position.
  • During your walkthrough, track past nodes to the node you want to remove.
  • In this case, you must traverse node 2 to remove the second node and store node 1 in a temporary variable.
  • Now the address part of node 2 is mapped to the address part of node 1 and node 2 is removed.

Deletion

for(int i=2; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}
temp->next = temp->next->next;

For example:

Deletion

Deletion

Deletion

Deletion

Here Code:

#include <stdio.h>
#include <stdlib.h>
struct node {
          int data;
          struct node *next;
}*head;
void createList(int n);
void deletion_given_pos(int pos);
void displayList();
int main()
{
          int n, data, pos;
          printf("\nEnter the total number of nodes: ");
          scanf("%d", &n);
          createList(n);
          printf("\nThe List is \n");
          displayList();
          printf("\nEnter the position : ");
          scanf("%d",&pos);
          deletion_given_pos(pos);
          printf("\n\nAfter Deleting the node at given position, the List is\n");
          displayList();
          return 0;
}
void createList(int n)
{
          struct node *newNode, *temp;
          int data, i;
          head = (struct node *)malloc(sizeof(struct node));
if(head == NULL)
{
          printf("Unable to allocate memory.");
}
else
{
          printf("\nEnter the data of node 1: ");
          scanf("%d", &data);
          head->data = data;
          head->next = NULL;
          temp = head;
for(i=2; i<=n; i++)
{
          newNode = (struct node *)malloc(sizeof(struct node));
          if(newNode == NULL)
          {
                   printf("Unable to allocate memory.");
                   break;
          }
          else
          {
                   printf("\nEnter the data of node %d: ", i);
                   scanf("%d", &data);
                   newNode->data = data;
                   newNode->next = NULL;
                   temp->next = newNode;
                   temp = temp->next;
          }
          }
}
}
void deletion_given_pos(int pos)
{
          if(head == NULL)
          {
                   free(head);
                   head = NULL;
          }
          struct node *temp = head,*prev_node;
          int count = 0;
          while(temp -> next != NULL && pos != count){
                   prev_node = temp; 
                   temp = temp -> next;
                   count = count + 1;
          }
          if(pos == count){
                   prev_node -> next = temp -> next; 
                   free(temp);
          }
}
void displayList(){
          struct node *temp;
          if(head == NULL){
                   printf("List is empty.");
          }
          else{
                   temp = head;
          while(temp != NULL){
                   printf("%d\t", temp->data);
                   temp = temp->next;
          }
          printf("\n");
          }
}

Conclusion:

In this article, you should learn that removing a node from a linked list also includes several locations where you can remove the node. You can remove the first node, the last node, or the k-th random node from the linked list. After deletion, the next and other pointers in the linked list must be adjusted properly to keep the linked list intact.

Recommended Articles:

  1. Traversal in Circular Linked List
  2. How to split a circular linked list into two halves?
  3. C++ program to insert in a sorted circular linked list?
  4. Insertion in Doubly Linked List
  5. Deletion in Doubly Linked List
  6. How to reverse a doubly linked list?
  7. QuickSort on Doubly Linked List
  8. Merge Sort for Doubly Linked List
  9. How to reverse a string using stack?
  10. Insertion in Circular Singly Linked List
  11. How to reverse a linked list?
  12. How to swap nodes in a linked list without Swapping data?
  13. How to write C functions that modify head pointer of a Linked List?
  14. Find Length of a Linked List (Iterative and Recursive)?
  15. A Programmer’s approach of looking at Array vs. Linked List
  16. How to delete a node in a linked list at a given Location?
  17. Insertion in Linked List
  18. Differences between Arrays and Linked Lists?
  19. Introduction to Linked List

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 71 times, 1 visits today)

0 0 vote
Article Rating
Subscribe
Notify of
1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] Deletion in Linked List […]

You cannot copy content of this page
Scroll Up
1
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.