## Find the number of occurrences of a number in the given linked list

**Occurrences :** number of times x is coming.

### Example

## Algorithm

**Time Complexity : O(n)**

**Space Complexity : O(1)**

**Step 1 :** Create a function which takes a linked list, a number as arguments and give the count of the number in the given linked list.

**Step 2 :** Initialize count equal to 0.

**Step 3 :** Traverse in Linked List, compare with the given number, if found a number equal to it, update count.

a)Â Â Â If the element data equal to the required number increment count.

b)Â Â Â After reaching the end of the Linked List return count.

**Step 4 :** call the function on given linked list and number you want to know occurrences. It prints the number of occurrences.

### Algorithm Working Example

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct LL{
int data;
LL *next;
};
void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
struct LL* curr=new LL;
curr->data=dataToBeInserted;
curr->next=NULL;
if(*head==NULL)
*head=curr; //if this is first node make this as head of list
else
{
curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
int countOccurence(struct LL**head,int X)
{
int count=0;
struct LL*temp=*head;
while(temp!=NULL)
{
if(temp->data == X)
count++;
temp=temp->next;
}
return count;
//O(number of nodes)
}
void display(struct LL**head)
{
struct LL*temp=*head;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
int main()
{
struct LL *head = NULL; //initial list has no elements
insertAtBeginning(&head,23);
insertAtBeginning(&head,49);
insertAtBeginning(&head,23);
insertAtBeginning(&head,15);
insertAtBeginning(&head,12);
insertAtBeginning(&head,1);
insertAtBeginning(&head,23);
cout<<"Initial List is :-\n";
display(&head);
int X = 23;
cout<<"The number of times "<<X<<" occurs is "<<countOccurence(&head,X)<<endl;
return 0;
}
```