Doubly Linked List - deletion
Deleting the First Node from a Doubly Linked List
Step 1: If the linked list is empthy (START == NULL)
Write "Sorry Buddy list is Empthy"
Step 2: If the 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;
START -> PREV = NULL;
free(PTR);
Step 4 : EXIT
Deleting the last node from a Doubly Linked List
Step 1: If the linked list is empthy (START == NULL)
Write "Sorry Buddy list is Empthy"
Step 2: If the linked list have only one node (START == START -> NEXT)
free(START)
START = NULL
Step 3: If the list have more than one node
PTR = START
while(PTR -> NEXT != NULL)
{
PTR = PTR -> NEXT
}
PTR -> PREV -> NEXT = NULL
free(PTR)
Step 4 : EXIT
Deleting a Specific Node from the Doubly 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 & move the PTR pointer upto specified position
PTR = START;
MOVE = 1;
while(MOVE < POS)
{
PTR = PTR->NEXT;
MOVE++;
}
PTR -> NEXT -> PREV = PTR -> PREV;
PTR -> PREV -> NEXT = PTR -> NEXT;
free(PTR);
Write "Node deleted successfuly..."
[END OF IF]
ELSE
Write "Position is invalid "
Step 5 : EXIT
C Program to Implement Doubly Linked List
# include <stdio.h>
# include <conio.h>
#include <malloc.h>
# include <stdlib.h>
struct Doubly_Linked_List
{
struct Doubly_Linked_List *prev;
int data;
struct Doubly_Linked_List *next;
};
typedef struct Doubly_Linked_List node;
node *start = NULL;
node* createnode()
{
node * newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter the data : ");
scanf("%d", &newnode -> data);
newnode -> next = NULL;
newnode -> prev = NULL;
return newnode;
}
void create_Doubly_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;
newnode -> prev = ptr ;
}
}
}
void insert_beg()
{
node *newnode ,*ptr;
newnode = createnode();
if(start == NULL)
{
start = newnode;
}
else
{
newnode -> next = start;
start -> prev = newnode;
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;
newnode -> prev = ptr;
}
}
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 ;
newnode -> prev = ptr ;
ptr -> next -> prev = newnode;
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 if(start->next == NULL)
{
free(start);
start=NULL;
printf("\n Node deleted successfuly... ");
}
else
{
ptr = start;
start = start -> next;
start -> prev = NULL ;
free(ptr);
printf("\n Node deleted successfuly... ");
}
}
void delete_last()
{
node *ptr, *temp;
if(start == NULL)
{
printf("\n Sorry Buddy there is no node ...List is Empty");
return ;
}
else if(start->next == NULL)
{
free(start);
start=NULL;
printf("\n Node deleted successfuly... ");
}
else
{
ptr = start;
while(ptr -> next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\n Node deleted successfuly... ");
}
}
void delete_mid()
{
node *ptr;
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 = start;
while(move < pos)
{
ptr = ptr -> next;
move ++;
}
ptr -> next -> prev = ptr -> prev;
ptr -> prev -> 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 Doubly_Linked_List : \n");
if(start == NULL)
{
printf("\n Sorry Buddy there is no node... List is Empty");
return;
}
else
{
while(ptr != NULL)
{
printf(" %d <-- -->", ptr -> data);
ptr = ptr -> next;
}
printf(" X ");
}
}
int menu()
{
int choice;
printf("\n --------Doubly 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_Doubly_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 "Doubly Linked List - node deletion algorithm "
Post a Comment