Frequency of data in Linked list

 2 Approaches

1. Normal traverse o (n)

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

//normal traversing approach

class node{

    public:

    int data;

    node* next;

};

void push(node** head_ref, int new_data)

{

    node* new_node= new node(); new_node->data= new_data;

    new_node->next= (*head_ref); (*head_ref)= new_node;

    

} //f ends

int count(node* head, int search_for)

{

    node* current = head; int count =0;

    while(current!=NULL) 

    {

        if(current->data== search_for) count++; current= current->next;

        

    } //while ends

    return count;

}//count ends

int main() {

  node* head= NULL;

  push(&head, 1);

   push(&head, 3);

    push(&head, 1);

     push(&head, 2);

      push(&head, 1);

     cout<<count(head, 1)<<endl;

return 0;

}

2. HASHMAP

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

//using hashmap key:value

struct node{

    int data;

    struct node* next;

};

//global var to count frequency of element k

int freq;

void push(struct node** head_ref, int new_data)

{

    struct node* new_node= new node(); new_node->data= new_data;

    new_node->next= (*head_ref); (*head_ref)= new_node;

} //f ends

int count(struct node* head, int key)

{

    if(head==NULL) return freq; 

    if(head->data==key) freq++; return count(head->next, key); 

} //count ends

int main() {

struct node* head= NULL;

push(&head, 1);

push(&head, 2);

push(&head, 3);

push(&head, 4);

push(&head, 1);

cout<< count(head, 1)<<endl;

return 0;

}