Singly Linked List - deletion of a node
Now we will see how a node is deleted form an already existing linked list.
In a single linked list, the deletion operation can be performed in three ways. They are as follows...
- Deleting the first node of the list
- Deleting the last node of the list
- Deleting a Specific Node
Algorithm to delete first node in singly linked list
Step 1: If linked list is empthy (START == NULL)
Write "Sorry Buddy there is no node "
Step 2: If linked list have only one node (START -> NEXT== NULL)
free(START)
START = NULL
Step 3: If the list have more than one node
PTR = START
START = START -> NEXT
free(PTR)
Step 4 : EXIT
Algorithm to delete last node from a singly linked list
Step 1: If linked list is empthy (START == NULL)
Write "Sorry Buddy there is no node "
Step 2: If linked list have only one node (START -> NEXT== NULL)
free(START)
START = NULL
Step 3: If the list have more than one node
PTR = START
while(PTR -> NEXT != NULL)
{
PREPTR = PTR
PTR = PTR -> NEXT
}
PREPTR -> NEXT = NULL
free( PTR )
Step 4 : EXIT
Counting total no of nodes in a singly linked list
int countnode(node *START)
{
if(START == NULL)
return(0);
else
return(1 + count(START-> NEXT));
}
Deleting a Specific Node from the Singly linked list
Step 1: If linked list is empthy (START == NULL)
Write "Sorry Buddy there is no node "
Step 2: Enter the position (POS) of node u want to delete & count total no of node
totalnode = countnode()
if(POS > totalnode )
Write "Given node not found in the list!"
Step 3: Ensure that enter postion is in between first and last node
IF( POS > 1 && POS < totalnode)
Step 4: Store the starting address in PTR & PREPTR & then move the PTR pointer upto specified position
PTR = PREPTR = START;
MOVE = 1;
while(MOVE< POS)
{
PREPTR = PTR
PTR = PTR->NEXT;
MOVE++;
}
PREPTR -> NEXT = PTR -> NEXT;
free(PTR);
Write "Node deleted successfuly..."
[END OF IF]
ELSE
Write "Position is invalid "
Step 5 : EXIT
C Program to Create, Insert ,Delete and Display the Elements in the Singly Linked List.
#include<stdio.h>
#include<conio.h>
#include <malloc.h>
#include <stdlib.h>
struct Linked_List
{
int data;
struct Linked_List *next;
};
typedef struct Linked_List node;
node *start = NULL;
node* createnode()
{
node * newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter the data : ");
scanf("%d", &newnode -> data);getchar();
newnode -> next = NULL;
return newnode;
}
void create_Linked_List(int n)
{
int i;
node *newnode , *ptr;
for(i = 0; i < n; i++)
{
newnode = createnode();
if(start == NULL)
{
start = newnode;
}
else
{
ptr = start;
while(ptr -> next != NULL)
{
ptr = ptr -> next;
}
ptr -> next = newnode;
}
}
}
void insert_beg()
{
node *newnode;
newnode = createnode();
if(start == NULL)
{
start = newnode;
}
else
{
newnode -> next = start;
start = newnode;
}
}
void insert_end()
{
node *newnode, *ptr;
newnode = createnode();
if(start == NULL)
{
start = newnode;
}
else
{
ptr = start;
while(ptr -> next != NULL)
{
ptr = ptr -> next;
}
ptr -> next = newnode;
}
}
int countnode(node *ptr)
{
int num_of_node=0;
while(ptr != NULL)
{
num_of_node++;
ptr = ptr -> next;
}
return (num_of_node);
}
void insert_mid()
{
node *newnode, *ptr, *preptr;
int pos, totalnode, move = 1;
printf("\n Enter the position where u want to insert the node : ");
scanf("%d", &pos);
totalnode = countnode(start);
if(pos > 1 && pos < totalnode)
{
newnode = createnode();
ptr = start;
while(move < pos-1)
{
ptr = ptr -> next;
move++;
}
newnode -> next = ptr -> next ;
ptr -> next = newnode;
;
}
else
printf("\n\t position %d is not a middle position", pos);
}
void delete_beg()
{
node *ptr;
if(start == NULL)
{
printf("\n Sorry Buddy there is no node... List is Empty");
return ;
}
else
{
ptr = start;
start = ptr -> next;
free(ptr);
printf("\n Node deleted successfuly... ");
}
}
void delete_last()
{
node *ptr, *preptr;
if(start == NULL)
{
printf("\n Sorry Buddy there is no node ...List is Empty");
return ;
}
else
{
ptr = start;
preptr = start;
while(ptr -> next != NULL)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = NULL;
free(ptr);
printf("\n Node deleted successfuly... ");
}
}
void delete_mid()
{
node *ptr, *preptr;
int pos, totalnode, move = 1;
if(start == NULL)
{
printf("\n Sorry Buddy there is no node... List is Empty");
return ;
}
else
{
printf("\n Enter position of node u want to delete: ");
scanf("%d", &pos);
totalnode = countnode(start);
if(pos > totalnode)
{
printf("\n There is no such node found in the list!");
}
if(pos > 1 && pos < totalnode)
{
ptr = preptr = start;
while(move < pos)
{
preptr = ptr;
ptr = ptr -> next;
move ++;
}
preptr -> next = ptr -> next;
free(ptr);
printf("\n Node deleted successfuly...");
}
else
{
printf("\n Position is invalid... ");
getch();
}
}
}
void display_List()
{
node *ptr;
ptr = start;
printf("\n The contents of Linked_List : \n");
if(start == NULL)
{
printf("\n Empty List");
return;
}
else
{ printf("\t");
while(ptr != NULL)
{
printf("%d -->", ptr -> data);
ptr = ptr -> next;
}
}
printf(" X ");
}
int menu()
{
int choice;
printf("\n --------Singly Linked List -------\n");
printf("\n 1. Create a list ");
printf("\n 2. Display the list");
printf("\n----------------------------------");
printf("\n 3.Insert a new node at beginning ");
printf("\n 4.Insert a new node at end");
printf("\n 5.Insert a new node at middle");
printf("\n---------------------------------");
printf("\n 6.Delete a node from the beginning");
printf("\n 7.Delete a node from the Last");
printf("\n 8.Delete a node from the Middle");
printf("\n-----------------------------------");
printf("\n 9. Count total no of nodes ");
printf("\n 10. Exit ");
printf("\n\n Enter your choice : ");
scanf("%d",&choice);
return choice;
}
int main()
{
int choice, n;
while(1)
{
choice = menu();
switch(choice)
{
case 1: if(start == NULL)
{
printf("\n Enter number of nodes you want to create: ");
scanf("%d", &n);
create_Linked_List(n);
printf("\n List created successfuly..");
}
else
printf("\n List is already created..");
break;
case 2: display_List(); break;
case 3: insert_beg(); break;
case 4: insert_end(); break;
case 5: insert_mid(); break;
case 6: delete_beg(); break;
case 7: delete_last(); break;
case 8: delete_mid(); break;
case 9: printf("\n Total number of nodes : %d ", countnode(start));
break;
case 10 : exit(0);
}
getch();
}
}
0 Comment to "singly linked list deletion algorithm"
Post a Comment