Delete node Circular linked list

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 -

• Delete element from Singly Linked List.
• Delete element from Doubly Linked List.

Step by step descriptive logic to delete element from circular linked list by key.

1. Create a circular linked list and assign reference of first node to head.

2. Input key to delete from user. Store it in some variable say key. Say key to delete is 20.
3. To keep track of previous node and node to delete, declare two variables of node type. Say cur = head and prev. Make sure prev points to last node.

4. 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->next with cur->next if there are more than one nodes i.e. cur->next != NULL. Otherwise assign prev->next = NULL.

   Adjust head node if needed. Means assign head = prev->next if cur == head.

   Delete the node using free[cur];.

   Update current node, i.e. assign cur = prev->next if prev != NULL. Otherwise assign NULL.

5. If current node does not contain key to delete, then simply update previous and current node. Say prev = cur and cur = cur->next.
6. 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 #include /* 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 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; idata = 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]; }

Happy coding