There are three possibilities of deleting a node from a linked list :
- Delete from beginning.
- Delete from end.
- Delete from specified position.
To understand the process of deleting a node from a linked list, you must have the knowledge of creating and displaying the linked list. To know the implementation of linked list click here.
Lets assume that the linked list is already created as shown in fig below,
Fig.1 Linked list
1. Deleting a node from beginning :
To delete a first node from the list, make the pointer
temp
to point to the first node by copying thehead
pointer to the pointertemp
.Copy the address part of the first node to which
temp
is pointing into thehead
by accessing the structure membernext
. This creates a link fromhead
to the second node in the list.Now the link for the first node to which
temp
is pointing is broken so free that memory space using functionfree(temp)
.Display the linked list after deletion.
void deleteFromBeg(struct node ** head)
{
struct node *temp;
temp = *head;
*head = temp->next;
free(temp);
}
2. Deleting a node from end :
Make
temp
to point first node in the list.Take one pointer
prevnode
of typestruct node
to point previous node in the list.Move
temp
till last node using while loop and each time copy thetemp
intoprevnode
. Whentemp
points last node,prevnode
points last but one node.Now, break the link of the last node from the list to which
temp
is pointing by updating the address part of the node to which pointerprevnode
is pointing tozero
as it has to be the last node in the list.Free the node pointing to by the
temp
usingfree(temp)
and display the linked list.
void deleteFromEnd(struct node **head, struct node *temp)
{
struct node *prevnode;
temp = *head;
while(temp->next != 0)
{
prevnode = temp;
temp = temp->next;
}
if(temp == *head)
*head = 0;
else
prevnode->next = 0;
free(temp);
}
3. Deleting a node from specified position :
Enter the position after which a node is to be inserted in the list and store that position value into any variable of type
int
. Here, position variable is taken aspos
.If
pos
(entered position) is greater than the number of nodes in the linked list, then printinvalid position
.If
pos
(entered position) is less than the number of nodes in the linked list then, maketemp
to point first node.Move
temp
from first node to that node whose position ispos-1
using while loop.Take one pointer
nextnode
of typestruct node
and make it to point to the node(which you want to delete) by copying the address part of the node pointing to bytemp
.
Note : temp
is pointing to the node just before the node you want to delete.
- To delete a node from the list, create a link from the node just before the node you want to delete to the node immediate after that specified position's (
pos
)node. The link is created as,
temp->next = nextnode->next;
- Free the
nextnode
which is pointing to the node you want to delete and display the linked list.
void deleteFromPos(struct node *head, struct node *temp, int count)
{
struct node *nextnode;
int pos, i=1;
printf("Enter the position : ");
scanf("%d", &pos);
if(pos>count)
{
printf("Invalid position.");
exit(0);
}
else
{
temp = head;
while(i < pos-1)
{
temp=temp->next;
i++;
}
nextnode = temp->next;
temp->next = nextnode->next;
free(nextnode);
}
}
C code that demonstrates the deletion from linked list :
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node * next;
};
int displayLL(struct node * head)
{
int num = 0;
struct node * temp;
temp = head;
temp=head;
while(temp!=0)
{
printf("%d ",temp->data);
temp = temp->next;
num++;
}
return num;
}
void deleteFromBeg(struct node * * head)
{
struct node * temp;
temp = * head;
* head = temp->next;
free(temp);
}
void deleteFromEnd(struct node **head, struct node *temp)
{
struct node *prevnode;
temp = *head;
while(temp->next != 0)
{
prevnode = temp;
temp = temp->next;
}
if(temp == *head)
*head = 0;
else
prevnode->next = 0;
free(temp);
}
void deleteFromPos(struct node *head, struct node *temp, int count)
{
struct node *nextnode;
int pos, i=1;
printf("Enter the position : ");
scanf("%d", &pos);
if(pos>count)
{
printf("Invalid position.");
exit(0);
}
else
{
temp = head;
while(i < pos-1)
{
temp=temp->next;
i++;
}
nextnode = temp->next;
temp->next = nextnode->next;
free(nextnode);
}
}
int main()
{
struct node *head = 0, *newnode, *temp;
int n, choice, newdata;
// Create Linked List //
printf("Enter the number of nodes in the list : ");
scanf("%d", &n);
for(int i = 1; i<=n; i++)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data%d : ", i);
scanf("%d", &newnode->data);
newnode->next = 0;
if(head == 0)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
}
printf("--------------------------------\n");
printf("Linked list : ");
int count = displayLL(head);
printf("\nCount = %d", count);
printf("\nEnter '1' for deleting node from beginning.\nEnter '2' for deleting node from end.\nEnter '3' for deleting after given position.\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
{
deleteFromBeg(&head);
printf("\nLinked list after deleting a node from beginning : ");
int count = displayLL(head);
break;
}
case 2:
{
deleteFromEnd(&head, temp);
printf("\nLinked list after deleting a node from end : ");
int count = displayLL(head);
break;
}
case 3:
{
deleteFromPos(head, temp, count);
printf("\nLinked list after deleting a node from specified pos : ");
int count = displayLL(head);
break;
}
}
}
I own a website www.coderlogs.com where in I write similar blogs so do visit this website for more such blog posts.
Top comments (0)