Write a C program to delete element from circular linked list by key. In this article I will explain how to delete by key element from circular linked list. I will explain logic and program to delete element from circular linked list by key.
Required knowledge
Functions, Pointers, Structures, Dynamic Memory Allocation
Logic to delete element from Circular Linked List
In my previous posts, I have explained to delete an element by key from singly linked list. Deletion of an element by key from circular linked list, is very much similar to singly linked list.
Read more –
Step by step descriptive logic to delete element from circular linked list by key.
- Create a circular linked list and assign reference of first node to head.
- Input key to delete from user. Store it in some variable say key. Say key to delete is 20.
- To keep track of previous node and node to delete, declare two variables of node type. Say
cur = headandprev. Make sure prev points to last node.
- If current node contains key, i.e.
if (cur->data == key). Then you got node to delete.
Before deleting a node, you must first adjust previous node link. Link
prev->nextwithcur->nextif there are more than one nodes i.e.cur->next != NULL. Otherwise assignprev->next = NULL.
Adjust head node if needed. Means assign
head = prev->nextifcur == head.Delete the node using
free(cur);.
Update current node, i.e. assign
cur = prev->nextifprev != NULL. Otherwise assignNULL.
- If current node does not contain key to delete, then simply update previous and current node. Say
prev = curandcur = cur->next. - Repeat step 3-4 till last node.
Program to delete element from Circular Linked List
/**
* C program to delete all occurrence of an element by key in Circular linked list.
*/
#include <stdio.h>
#include <stdlib.h>
/* Basic node structure. */
struct node {
int data;
struct node * next;
};
/* Functions declarations */
void createList(struct node ** head, int n);
void displayList(struct node ** head);
void deleteAll(struct node ** head, int key);
int main()
{
int n, key, data, choice;
struct node * head = NULL;
/* Run forever until user chooses 0 */
while(choice != 0)
{
printf("--------------------------------------------\n");
printf(" CIRCULAR LINKED LIST PROGRAM \n");
printf("--------------------------------------------\n");
printf("1. Create List\n");
printf("2. Display list\n");
printf("3. Delete all by key\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter number of nodes to create: ");
scanf("%d", &n);
createList(&head, n);
break;
case 2:
displayList(&head);
break;
case 3:
printf("Enter key to delete from list: ");
scanf("%d", &key);
deleteAll(&head, key);
break;
case 0:
exit(0);
break;
default:
printf("Error! Invalid choice. Please choose between 0-3");
}
printf("\n\n\n\n");
}
return 0;
}
/**
* Delete all occurrence of an element by key from a
* given circular linked list.
*/
void deleteAll(struct node ** head, int key)
{
int i, count;
struct node *prev, *cur;
if (*head == NULL)
{
printf("List is empty.\n");
return;
}
count = 0;
cur = *head;
prev = cur;
// Find node before head node
while (prev->next != *head)
{
prev = prev->next;
count++;
}
// Iterate till first node
i = 0;
while (i <= count)
{
if (cur->data == key)
{
// Link prev node with next node of current
if (cur->next != cur)
prev->next = cur->next;
else
prev->next = NULL;
// Adjust head node if needed
if (cur == *head)
*head = prev->next;
// Delete current node
free(cur);
// Move current node ahead
if (prev != NULL)
cur = prev->next;
else
cur = NULL;
}
else
{
prev = cur;
cur = cur->next;
}
i++;
}
}
/**
* Create a circular linked list of n nodes.
*/
void createList(struct node ** head, int n)
{
int i, data;
struct node *prevNode, *newNode;
prevNode = NULL;
/* Creates and link n nodes */
for(i=1; i<=n; i++)
{
newNode = malloc(sizeof(struct node));
printf("Enter data of %d node: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
// Link the previous node with newly created node
if (prevNode != NULL)
prevNode->next = newNode;
// Adjust head node
if (*head == NULL)
*head = newNode;
// Move previous node ahead
prevNode = newNode;
}
// Link last node with first node
prevNode->next = *head;
printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n");
}
/**
* Display content of the linked list.
*/
void displayList(struct node ** head)
{
struct node *current;
int n = 1;
if(*head == NULL)
{
printf("List is empty.\n");
return;
}
current = *head;
printf("DATA IN THE LIST:\n");
do {
printf("Data %d = %d\n", n, current->data);
current = current->next;
n++;
}while(current != *head);
}--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 1
Enter number of nodes to create: 5
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30
Enter data of 4 node: 40
Enter data of 5 node: 50
CIRCULAR LINKED LIST CREATED SUCCESSFULLY
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 10
Data 2 = 20
Data 3 = 30
Data 4 = 40
Data 5 = 50
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 3
Enter key to delete from list: 10
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 20
Data 2 = 30
Data 3 = 40
Data 4 = 50
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 3
Enter key to delete from list: 30
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 20
Data 2 = 40
Data 3 = 50
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 3
Enter key to delete from list: 50
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 20
Data 2 = 40
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Delete all by key
0. Exit
--------------------------------------------
Enter your choice : 0