Find number of times given element exists in single linked list (java/ example)

• Given a single linked list,  count number of times given element exist in a single linked list.
  • e.g. if we want to count node = 10 exist in a single linked list (Fig 1), then output should be 2.
• Similarly, if we would like to find node = 20 in a single linked list, then output should be 3.

Algorithm – find number of times element exists in a single linked list

• Find number of times element inputData = 10 exists in a single linked list
• Declare variable count = 0
  • defines number of time element exists in a single linked list
• Start traversing the linked list from head
  • Compare node data with 10
    • if data is equal
      • increment the count ( count++)
  • Keeps on iterating till, we reach end of single linked list
• By the end traversal, we will get number of times element exists in a single linked list.

Time complexity of algorithm is O(n).

Program: number of times given element exists in a single linked list (java)

1.) CountElement Class:

• countElement metehod, counts the number of times element exists in a single linked list
• insert function is used to insert element to a single linked list
  • insert function is used to create linked list
• print function is used to print the single linked list (head to tail)

package org.learn.Question;

import org.learn.List.Node;

public class CountElement {

 public static int countElement(Node head, int search) {

  int elementCount = 0;
  // 1 -> 2 -> 3
  while (head != null) {
   if (head.data == search) {
    elementCount++;
   }
   head = head.next;
  }
  return elementCount;
 }

 public static void insert(Node head, int data) {
  while (head.next != null)
   head = head.next;
  head.next = new Node(data);
 }

 public static void print(Node head) {
  while (head != null) {
   System.out.printf("%d ", head.data);
   head = head.next;
  }
  System.out.println("");
 }
}

2.) App Class:

• We are creating the single linked list in main method.
• We are printing the single linked list using CountElement.print method.
• We are calling countElement method, to count number of times, element(s) exists in a single linked list.

package org.learn.Client;

import org.learn.List.Node;
import org.learn.Question.CountElement;

public class App {
 public static void main(String[] args) {
  int[] data = { 10, 20, 10, 20, 50, 20, 50 };
  Node head = new Node(data[0]);
  for (int count = 1; count < data.length; count++)
   CountElement.insert(head, data[count]);

  System.out.printf("Linked list is : ");
  CountElement.print(head);

  int search = 10;
  int count = CountElement.countElement(head, search);
  System.out.printf("Element %d exists %d times in linked list", search, count);

  search = 20;
  count = CountElement.countElement(head, search);
  System.out.printf("\nElement %d exists %d times in linked list", search, count);

  search = 50;
  count = CountElement.countElement(head, search);
  System.out.printf("\nElement %d exists %d times in linked list", search, count);
 }
}

3.) Node Class:

• Node class representing the nodes of single linked list

package org.learn.List;

public class Node {
 public int data;
 public Node next;

 public Node(int num) {
  this.data = num;
  this.next = null;
 }
}

Output – find number of times given node exists in a linked list using java

Linked list is : 10 20 10 20 50 20 50
Element 10 exists 2 times in linked list
Element 20 exists 3 times in linked list
Element 50 exists 2 times in linked list

Download code – count given node/ element in single linked list in java