Count nodes in a linked list with given value

by · June 22, 2020

“Count nodes in a linked list with given value” is a basic programming problem based on linked list data structures for beginners. Here, we are given a linked list and our task is to count nodes in a linked list with given value.

To do so, we need to traverse the complete linked list and increment the counter every time we encounter a node with value ‘x’.

Example:

Suppose, we need to count the occurrence of the nodes with value ‘2’ in the following linked list.
Linked List: 
1 -> 2 -> 3 -> 2 -> 2 -> 7 -> 2 
The following list has 4 occurrences of Nodes with value as ‘2’.

The steps to count nodes in a linked list with given value are as follows:

  1. Initialize a counter with 0.
  2. Traverse the complete linked list. While traversing, for every node, check if the node value is ‘x’ or not. If the node value is ‘x’, then increment the counter.
  3. Print the counter as the number of occurrences of the nodes with value ‘x’.

C++ Program to count nodes in a linked list with given value is as follows:

/* C++ Program to Count nodes in a linked list with given value */
#include<bits/stdc++.h>
using namespace std;
/* Structure of the node of the linked list */
struct node
{
    int data;
    struct node *next;
};

/* Function to Insert new node at the beginning of the linked list */
void insert_end(struct node **head, int ele)
{
    /* Creating a new node */
    struct node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* check whether the linked list is empty or not */
    
    /* If the linked list is empty */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    
    /* if the linked list is not empty, then traverse the complete linked list and 
    points the pointer of the last node of the linked list to the new node */
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to count all Occurrences of particular node in a linked list */
int count(struct node *head,int x)
{
    /* Traverse the complete linked list and for every node encountered,
    check whether node value is 'x' or not. If Node value is 'x', then increment
    counter by 1. */
    struct node *temp = head;
    int counter = 0;
    while(temp!=NULL)
    {
        if(temp->data == x)
        counter++;
        temp=temp->next;
    }
    return counter;
}

/* Function to print the linked list */
void print(struct node *head)
{
    struct node *p = head;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}
int main()
{
    struct node *head;
    head = NULL;
    /* Insert Some Nodes of the Linked List */
    insert_end(&head,1);
    insert_end(&head,2);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,2);
    insert_end(&head,7);
    insert_end(&head,2);
    cout<<"The elements of the linked list are:\n";
    print(head);
    int x = 2;
    int res = count(head,x);
    cout<<"\nThe total number of nodes in a linked list with value as "<<x<<" is "<<res;
}

OUTPUT:
The elements of the linked list are:
1 2 3 2 2 7 2 
The total number of nodes in a linked list with value as 2 is 4

Related Posts:

  1. Bubble Sort on Linked List.
  2. Detect a Loop in a Linked List.
  3. Find the Length of the Loop present in the Linked List.
  4. Detect and Remove Loop from a Linked List.
  5. Segregate Even and Odd Nodes of the Linked List.
  6. Delete Complete Linked List.
  7. Delete Nth Node of the Linked List.
  8. Delete without head pointer of the Linked List.
  9. Delete All Occurrences of particular node of the Linked List.
  10. Delete Alternate Nodes of the Linked List.
  11. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  12. Remove Duplicate Nodes from an Unsorted Linked List.
  13. Remove Duplicate Nodes from a Sorted Linked List.
  14. Find Union and Intersection of Two Linked List.
  15. Merge Two Sorted Linked List.
  16. Insert a New Node at the Middle of the Linked List.
  17. Insert a New Node at the Sorted Linked List.
  18. Reverse a Linked List.
  19. Reverse a Linked List Using Stack.
  20. Printing Linked List in Reverse Order without actually reversing the Linked List.

Tags:

You may also like...