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
tempto point to the first node by copying theheadpointer to the pointertemp.Copy the address part of the first node to which
tempis pointing into theheadby accessing the structure membernext. This creates a link fromheadto the second node in the list.Now the link for the first node to which
tempis 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
tempto point first node in the list.Take one pointer
prevnodeof typestruct nodeto point previous node in the list.Move
temptill last node using while loop and each time copy thetempintoprevnode. Whentemppoints last node,prevnodepoints last but one node.Now, break the link of the last node from the list to which
tempis pointing by updating the address part of the node to which pointerprevnodeis pointing tozeroas it has to be the last node in the list.Free the node pointing to by the
tempusingfree(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, maketempto point first node.Move
tempfrom first node to that node whose position ispos-1using while loop.Take one pointer
nextnodeof typestruct nodeand 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
nextnodewhich 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)