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