Count occurences of a given number in a LinkedList

user_9060189 0
Viewed 167

Given a class LinkedList

public class LinkedList {

    public Node head = null;

    public class Node {
        public int value;
        public Node next;
    }
}

I would like to add a method public int count(int value) that counts the amount of times a number occurs in a list. I tried the following but it doesn't always work and I'm not sure what I am doing wrong.

public int count(int value) {

    int counter = 0;

    while(head != null) {

        Node tmp = head.next;

        while(tmp != null) {

            if(head.value == value) {
                counter++;
            }
            tmp = tmp.next;
        }
        head = head.next;
    }
    return counter;
}

This method works for 1 4 3 4 4 5, int value = 4 (which returns 3, as it should)

but for 1 2 3 4 4 5, int value = 4, it returns 1.

linked-list java
3 Answers

Try this:

public int count(int value) {
    int counter = 0;
    Node tmp = head;
    while (tmp != null) {
        if(tmp.value == value) { // this line contained your biggest mistake
            counter++;
        }
        tmp = tmp.next;
    }
    return counter;
}

You were not using value parameter at all in your method.

I would suggest you improve your Java learning through the use of an IDE that might give you hints of problems in your code. In this case, the lack of usage of value parameter in your method implementation.

I would suggest: IntelliJ IDEA, Eclipse or Visual Studio code. I am sure there are many more but these are the ones that I know.

This is a small example of what I mean:

enter image description here

user_676060

The simplest approach is: Iterate through the list and increase count for each node that contains 'value'. Since there were several problems in your code, I tried to explain the reason for each line with comments.

public int count(int value) {
    int count = 0;
    
    // 'tmp' is the node we are currently processing.
    // Starting at the head...
    Node tmp = head;
    
    // while we not reached the end of the list
    while(tmp != null) {
        // if the node has the same value we are searching for
        if(tmp.value == value) {
            // increase count since we found the value
            count++;
        }
        // Go to the next node (null if we reached the end of the list).
        tmp = tmp.next;
    }
    
    return count;
}
user_151377780

Here is the recursive-approach of your problem:

int count(int value){
    /* dummy node of your head */
    LinkedList temp = this.head;
    return count(temp, value);
}

private int count(LinkedList temp, int value){ 
   int counter = 0;
   if(temp == null){
      return 0;
   }
   
   /* increment counter, when value is matched */
   if(temp.value == value){
      counter += 1;
   }
   
   counter += count(temp.next, value);
   /* return the final result at the end */
   return counter;
}
user_83596230
Related