Home » Interview Questions » LinkedList Interview Questions » Find the occurrences of a number in a linked list

Find the occurrences of a number in a linked list


()

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;
}

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions