Circular Linked List -Deletion
Now we will see how a new node is deleted from an already existing circular linked list.
It can be performed in two ways. They are as follows...
- Deleting the first node
- Deleting the last node
Rest of the cases are similar to Singly Linked List deletion operation
Deleting the First Node from a Circular 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 != START)
{
PTR = PTR -> NEXT
}
PTR -> NEXT = START -> NEXT
free(START)
START = PTR -> NEXT
Step 4 : EXIT
Deleting the Last Node from a Circular Linked List
Step 1: If the linked list is empthy (START == NULL)
Write "Sorry Buddy linked 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 -> NEXT!= START)
{
PTR = PTR -> NEXT
}
TEMP = PTR -> NEXT
PTR -> NEXT = START
free(TEMP)
Step 4 : EXIT
Display the Nodes of the Circular Single Linked List
Step 1: If the linked list is empthy (START == NULL)
Write "Sorry Buddy there is no node
Step 2: If the linked list is not Empthy
PTR = START;
do
{
printf("%d-->", PTR -> DATA);
PTR = PTR -> NEXT;
} while(PTR != START);
Step 3: EXIT
C Program to Implement Circular Linked List
#include <stdio.h>
#include<conio.h>
#include <malloc.h>
#include <stdlib.h.h>
struct Circular_Linked_List
{
int data;
struct Circular_Linked_List *next;
};
typedef struct Circular_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;
return newnode;
}
void create_Circular_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 ->next = start;
}
void insert_beg()
{
node *newnode ,*ptr;
newnode = createnode();
if(start == NULL)
{
start = newnode;
newnode -> next = start;
}
else
{
ptr = start;
while(ptr -> next != start)
{
ptr = ptr -> next;
}
ptr -> next = newnode;
newnode -> next =start;
start = newnode;
}
}
void insert_end()
{
node *newnode, *ptr;
newnode = createnode();
if(start == NULL)
{
start = newnode;
newnode -> next = start;
}
else
{
ptr = start;
while(ptr -> next != start)
{
ptr = ptr -> next;
}
ptr -> next = newnode;
newnode -> next = start;
}
}
int countnode(node *ptr)
{
int num_of_node=0;
if (start != NULL)
{
do
{
num_of_node++;
ptr = ptr -> next;
}while(ptr != start);
}
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;
while(ptr -> next != start)
{
ptr = ptr -> next;
}
ptr -> next = start -> next;
free(start);
start = ptr -> next ;
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 ==start->next)
{
free(start);
start=NULL;
}
else
{
ptr = start;
while(ptr -> next -> next != start)
{
ptr = ptr -> next;
}
temp = ptr -> next;
ptr->next =start;
free(temp);
}
}
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 Circular_Linked_List : \n");
if(start == NULL)
{
printf("\n Sorry Buddy there is no node... List is Empty");
return;
}
else
{ do
{
printf("\t %d -->", ptr -> data);
ptr = ptr -> next;
} while(ptr != start);
printf(" X ");
}
}
int menu()
{
int choice;
printf("\n --------Circular 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_Circular_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 "Circular Linked List -Deletion Algorithm & Program"
Post a Comment