Deletion of the linked list can occur in different parts of the list. Some cases are:
- Beginning of the linked list.
- End of the linked list.
- 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.
head = head->next;
For example:
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.
struct node* temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
temp->next = NULL;
For example:
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.
for(int i=2; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}
temp->next = temp->next->next;
For example:
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.