Deletion in Linked List | Linked List Operations

30 min read

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

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;
}*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));
 // When the list is empty
 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;
 }
 }
 }
}

/* Function to delete the first node */
void deletion_beginning()

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

 

OUTPUT

delete first node in linked list

 

Deletion at the end of the linked list

deletion in linked list - at the end

  • 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;
}*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));
// When the list is empty
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;
}
}
}
}


/* Function to delete the last node */
void deletion_end()
{
// Empty List
if(head -> next == NULL)
{
free(head); //Delete head
head = NULL; // make the reference to NULL
}
struct node *temp = head,*prev_node;
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;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}

 

OUTPUT

delete last node in linked

 

Deletion at a given position in the linked list

deletion in linked list - at a given position

  • 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;
}*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 : "); //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
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;
}
}
}
}


/* Function to delete the node at given position */
void deletion_given_pos(int pos)
{
// Empty List
if(head == NULL)
{
free(head); //Delete head
head = NULL; // make the reference to NULL
}
struct node *temp = head,*prev_node;
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;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
// Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}

 

OUTPUT

delete a specific node in linked list

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error