Frequency of a given number in a Linked List

You are given a linked list. You have to write a function that will give frequency of a given number in linked list.

Here is a solution

Algorithm:

1. Initialize count as zero.
2. Loop through each element of linked list:
3. If element data is equal to the given number then increment the count.
4. Return count

#include<stdio.h>
#include<stdlib.h>
 
/* Link list node */
struct node 
{
    int data;
    struct node* next;
};

void insert(struct node** head, int value) 
{
   
    struct node* new_node = 
            (struct node*) malloc(sizeof(struct node)); 
 
    new_node->data  = value; 
     
    new_node->next = (*head); 

    (*head)    = new_node; 
}
 
/* Counts the no. of occurences of a node in a linked list */
int count(struct node* start, int item) 
{
    struct node* current = start;
    int count = 0;
    while (current != NULL) 
    {
        if (current->data == item)
           count++;
        current = current->next;
    }
    return count;
}
 
// main program
int main()
{
    struct node* start = NULL;
     
    insert(&start, 2); 
    insert(&start, 5); 
    insert(&start, 1);  
    insert(&start, 2);
    insert(&start, 2);    
     
    /* Check the count function */
    printf("count of 2 is %d", count(start, 2));    
    return 0;
}

Complexity: O(N)

One Thought on “Frequency of a given number in a Linked List

  1. Ajay Tiwary on May 9, 2015 at 3:39 pm said:

    recursive:-

    public class LinkedList {
    static int k=0;
    public static void main(String[] args) {
    Node n1 = new Node(1);
    Node n2 = new Node(2);
    Node n3 = new Node(3);
    Node n4 = new Node(4);
    Node n5 = new Node(5);
    Node n6 = new Node(5);
    Node n7 = new Node(7);

    n1.setNext(n2);
    n2.setNext(n3);
    n3.setNext(n4);
    n4.setNext(n5);
    n5.setNext(n6);
    n6.setNext(n7);

    int count = countNum(n1,5);
    System.out.println(count);

    }

    private static int countNum(Node n1, int i) {

    Node temp = n1;

    if(temp==null)
    {
    return k;
    }
    if(temp.getData()==i)
    {
    k++;
    }
    return countNum(n1.getNext(),i);
    }

    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation