C program to delete element from 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

Delete element from circular linked list

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.

  1. Create a circular linked list and assign reference of first node to head.
    Circular linked list deletion - Step 1

  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.
    Circular linked list deletion - Step 2

  4. If current node contains key, i.e. if (cur->data == key). Then you got node to delete.
    Circular linked list deletion - Step 3

    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.

    Circular linked list deletion - Step 4

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

    Delete the node using free(cur);.

    Circular linked list deletion - Step 5

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

    Circular linked list deletion - Step 6

  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 <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