Home » C programs

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

Here, we are going to learn how to count the number of occurrences of an element in a linked list using recursion?
Submitted by Piyas Mukherjee, on January 11, 2019

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>

typedef struct list //linked list structure
{
	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