Count the number of occurrences of an element in a linked list using recursion

In this tutorial, we will learn how to count the number of occurrences of an element in a linked list using recursion using the C program? By Piyas Mukherjee Last updated : August 01, 2023

Solution

Required function:

func_occurence ( node *temp) //recursive function

Input

A singly linked list whose address of the first node is stored in a pointer, say head and key is the data of which we have to count the number of occurrences.

Output

The number of times key occurred in the list, (c)

Data Structure Used

Singly linked list where each node contains a data element say data and the address of the immediate next node say next, with Head holding the address of the first node.

Pseudo Code

Begin
    c=0 //global variable
    if(temp=NULL)
        print c
    Else 
        if(temp->data=key)
            c=c+1;
            func_occurence(temp->next);
        End If
    End If-else
End

C program to count the number of occurrences of an element in a linked list using recursion

#include <stdio.h>
#include <stdlib.h>

//linked list structure
typedef struct list {
    int data;
    struct list* next;
} node;

// global variables
int key, c = 0;
int occurence(node* temp); //function to check occurence

int main()
{
    node *head = NULL, *temp, *temp1;
    int choice, count;

    //building the linked list
    do {
        temp = (node*)malloc(sizeof(node));
        if (temp != NULL) {
            printf("\nEnter the element in the list : ");
            scanf("%d", &temp->data);
            temp->next = NULL;
            if (head == NULL) {
                head = temp;
            }
            else {
                temp1 = head;
                while (temp1->next != NULL) {
                    temp1 = temp1->next;
                }
                temp1->next = temp;
            }
        }
        else {
            printf("\nMemory not avilable...node allocation is not possible");
        }
        printf("\nIf you wish to add more data on the list enter 1 : ");
        scanf("%d", &choice);
    } while (choice == 1);

    printf("\nEnter the data to find it's occurrence : ");
    scanf("%d", &key);
    count = occurence(head);
    printf("%d occured %d times in the list", key, count);

    return 0;
}

//finding occurence of the key value
int occurence(node* temp)
{
    if (temp == NULL)
        return c;
    else {
        if (temp->data == key)
            c = c + 1;
        occurence(temp->next);
    }
}

Output

Enter the element in the list : 1

If you wish to add more data on the list enter 1 : 1

Enter the element in the list : 2

If you wish to add more data on the list enter 1 : 1

Enter the element in the list : 3

If you wish to add more data on the list enter 1 : 1

Enter the element in the list : 4

If you wish to add more data on the list enter 1 : 1

Enter the element in the list : 5

If you wish to add more data on the list enter 1 : 0

Enter the data to find it's occurrence : 1
1 occured 1 times in the list