 Explore
Placement Prep Edit Edit

Published on 07 Mar 2020

Deletion in a linked list can happen at various places in a list. A few cases are:

• At the beginning of the linked list.
• At the end of the linked list.
• At a given position in the linked list.

Now, let us look at a program for each of these cases.

### Deletion at the beginning of the linked list • To delete the first node (head node), copy the head node in a temporary node.
• Make the second node as the head node.
• Now, delete the temporary node.

Program to delete a node at the beginning of the Linked List

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

// Creating node with data and a pointer
struct node {
int data;
struct node *next;
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));
// When the list is empty
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
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;
}
}
}
}

/* Function to delete the first node */
void deletion_beginning()
{
// Empty List
printf("\n The list is Empty\n");
struct node *temp;
free(temp); // Delete the temporary node
}
void displayList()
{
struct node *temp;
{
printf("List is empty.");
}
else
{
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}


OUTPUT: ### Deletion at the end of the linked list • To delete the last node, start traversing the list from the head node and continue traversing until the address part of the node is NULL.
• Keep track of the second last node in some temporary variable say prev_node.
• Once the address part of the node is NULL, set the address part of the prev_node as NULL and then delete the last node.

Program to delete a node at the end of the Linked List

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

// Creating node with data and a pointer
struct node {
int data;
struct node *next;
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));
// When the list is empty
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
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;
}
}
}
}

/* Function to delete the last node */
void deletion_end()
{
// Empty List
{
head = NULL; // make the reference to NULL
}
while(temp -> next != NULL)
{
prev_node = temp;
temp = temp -> next; //Traverse to to the last node
}
free(temp); //Delete the last node
prev_node -> next = NULL;
}

void displayList()
{
struct node *temp;
{
printf("List is empty.");
}
else
{
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}


OUTPUT: ### Deletion at a given position in the linked list • Now let us assume that the node at position 2 has to be deleted.
• Start traversing the list from the head node and move up to that position.
• While traversing, keep track of the previous node to the node to be deleted.
• In this case, since we want to delete the second node, you need to traverse till node 2, storing node 1 in some temporary variable.
• Now, the address part of node 2 is assigned to the address part of node 1 and then node 2 is deleted.

Program to delete a node at a given position in the Linked List

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

// Creating node with data and a pointer
struct node {
int data;
struct node *next;
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 : "); //position of the node to be deleted
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));
// When the list is empty
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
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;
}
}
}
}

/* Function to delete the node at given position */
void deletion_given_pos(int pos)
{
// Empty List
{
head = NULL; // make the reference to NULL
}
int count = 0;
while(temp -> next != NULL && pos != count)
{
prev_node = temp;  // Tracking the (position - 1 )node
temp = temp -> next;
count = count + 1;
}
if(pos == count)
{
prev_node -> next = temp -> next;  // Assigning the address of the node to be deleted to its previous node
free(temp); // Delete the node
}
}

void displayList()
{
struct node *temp;
{
printf("List is empty.");
}
else
{
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}


OUTPUT: ﻿  