Count the number of occurrences of an element in a linked list in c++

In this tutorial, we will learn how to count the number of occurrences of an element in a linked list in c++.

For example

Example

If num=3.

Then the output will be it occurs 2 times.

If num=1

Then the output will be it occurs 1 time.

How to count the number of occurrences of an element in a linked list in c++?

Method 1:

We will use STL(Standard template library) here.

1. Create a list using STL.
2. Traverse the list by using an iterator.
3. Compare each element with num to be found and increase the count.
4. Print count.

Here, is the code:

#include <bits/stdc++.h>
using namespace std;
int main() {
   list<int> mylist;
    int n;
    cin>>n;
    int data;

    for(int i=0;i<n;i++)
    {
        cin>>data;
        mylist.push_back(data);
    }
    int num;
    cin>>num;
    int count=0;

   for(list<int>::iterator head=mylist.begin();head!=mylist.end();head++)
   {
     if(*head==num)//comparing element
     count++;
   }
    cout<<num<<" occurs "<<count<<" times ";

}

Input:

5

1 2 3 2 1

2

Output:

2 occurs 2 times

Method 2(By recursion):

We will create a linked list with the help of a class. The function createll(int n) creates the linked list by inserting elements at the end.

1. int countrepetition(node *head,int num,int count)
   The count is initialized to 0.
2. if(head->next==NULL)

   return count;

   This is our base case. It means that we have reached to the end of our linked list.
3. Now compare the current head data to num and increase the count.
4. count=countrepetition(head->next,num,count);

   Recursive call for next element and the head is changed to head->next.

Here, is the code:

#include<iostream>
using namespace std;

class node{
public:
    int data;
    node* next;
    node(int d)
    {
        data=d;
        next=NULL;
    }

};

node *createll(int n){

int x;
node *head=NULL;
node *tail=NULL;

for(int i=0;i<n;i++)
{
    cin>>x;


        node *n=new node(x);
        if(head==NULL)
        {
            head=n;
            tail=n;
        }

    else
    {
        tail->next=n;
        tail=tail->next;
    }
}
return head;
}

void display(node *head)
{
    node *temp=head;

    while(temp!=NULL)
    {
        cout<<temp->data<<"-->";
        temp=temp->next;
    }
cout<<endl;

}

int countrepetition(node *head,int num,int count)
{
    if(head->next==NULL)
        return count;

    if(head->data==num)
    {
        count++;
    }

    count=countrepetition(head->next,num,count);

    return count;
}



int main()
{
    int n;
    cin>>n;
   node *head=createll(n);
   cout<<"Our linked list is:"<<endl;
    display(head);
    int num;
    cin>>num;

    int count=countrepetition(head,num,0);
    cout<<num<<" occurs "<<count<<" times ";



}

Input:

5 

1 2 3 2 1

3

Output:

Our linked list is:

1-->2-->3-->2-->1-->

3 occurs 1 time

Also, refer to:

Reverse linked list using STL