Linked List Malfunctioning

Question

I am trying to make a linked last class that will store data and how frequently the data appears.

For example if someone adds the integer 5 to the linked list 12 times, when asked for the frequency of 5 (with getFrequencyOf(5)) the result should be 12.

Unfortunately the first number that is added to my linked list is returning a frequency one less than it should. My code is posted below. Any thoughts on how to proceed with fixing this problem would be greatly appreciated.

package main;

//    //Implement using a linked list
public class FrequencyBag<T>
{
    // TO DO: Instance Variables
    private Node firstNode;
    private int numOfItems;

    private class Node{
        //Node Instance Variables

        private T data;
        private int frequency;
        private Node next;

        private Node(T Data, Node nextNode){
            data= Data;
            next=nextNode;
            frequency=1;
        }

        private void addF(){
            frequency++;
        }

        private int getF(){
            return frequency;
        }

    }


    /**
     * Constructor
     * Constructs an empty frequency bag.
     */
    public FrequencyBag()
    {
        firstNode=null;
        numOfItems =0;
    }

    /**
     * Adds new entry into this frequency bag.
     * @param aData the data to be added into this frequency bag.
     */
    public void add(T aData)
    {

        if(firstNode!=null){
            boolean found =false;
            Node currNode=firstNode;

            while(currNode.next !=null){

                if(currNode.data.equals(aData)){
                    currNode.addF();
                    found=true;
                    break;
                }
                currNode= currNode.next;
            }

            if(!found){
                Node tempNode=firstNode;
                firstNode= new Node(aData,tempNode);

            }
        }

        else{
            firstNode= new Node(aData,null);
        }
        numOfItems++; 
    }
    /**
     * Gets the number of occurrences of aData in this frequency bag.
     * @param aData the data to be checked for its number of occurrences.
     * @return the number of occurrences of aData in this frequency bag.
     */
    public int getFrequencyOf(T aData)
    {
        Node currNode= firstNode;
        while(currNode!=null){
            if(currNode.data.equals(aData)){
                return currNode.getF();
            }
            currNode= currNode.next;
        }

        return 0;
    }

    /**
     * Gets the maximum number of occurrences in this frequency bag.
     * @return the maximum number of occurrences of an entry in this
     * frequency bag.
     */
    public int getMaxFrequency()
    {
        if(firstNode!=null){
            Node currNode= firstNode;
            Node maxNode= firstNode;
            while(currNode!=null){
                if(currNode.getF()>=maxNode.getF()){
                    maxNode=currNode;
                }
                currNode=currNode.next;
            }
            return maxNode.getF();
        }
        else{
            return 0;
        }
    }

    /**
     * Gets the probability of aData
     * @param aData the specific data to get its probability.
     * @return the probability of aData
     */
    public double getProbabilityOf(T aData)
    {
        if(firstNode!=null){
            boolean flag=true;
            double dataF=0;
            double prob=0;
            Node currNode= firstNode;
            while(currNode!=null){
                if(currNode.data.equals(aData)){
                    dataF=(double)currNode.getF();
                    flag=false;
                    break;
                }
                currNode= currNode.next;
            }   
            if(!flag){
                prob= dataF/(double)numOfItems;
            }
            return prob;
        }
        else{
            return 0;
        }
    }

    /**
     * Empty this bag.
     */
    public void clear()
    {
        firstNode=null;
        numOfItems=0;
    }

    /**
     * Gets the number of entries in this bag.
     * @return the number of entries in this bag.
     */
    public int size()
    {
        return numOfItems;
    }
}

You should run your code under a debugger to see what's going wrong. It is too long to debug it just by looking at it. — kraskevich, Jan 22 '15 at 19:20
Just use a hashtable for the frequencies - simpler, more efficient and memory wise in the vast majority of cases not a problem. — Voo, Jan 22 '15 at 19:30
@ILoveCoding. If I could "-1" your comment I would. He should write [unit tests](http://stackoverflow.com/questions/67299/is-unit-testing-worth-the-effort) to work out why it isn't working, and make this code maintainable and correct. — Andy Brown, Jan 22 '15 at 19:59
@Turtle I have shown you how to correct this code, but once you have fixed it in your code you should consider putting it on http://codereview.stackexchange.com to get general feedback about your approach as there are a few things I can see that could be improved. — Andy Brown, Jan 22 '15 at 20:10

Andy Brown · Accepted Answer · 2015-01-22T20:08:49.393

Your logic in add is wrong. You skip the first node without testing it when you have only done add once (i.e. in your second add operation) because firstNode.next is null at that point.

Make your while (currNode.next != null) a while (currNode != null). See below for a correct version (for that specific problem only: I haven't tested for all expected behaviour as I don't have your spec).

Note that the code can be shortened as shown (and more still after that). Start writing unit tests and you can both find bugs like this faster, and refactor with more confidence in order to make your code shorter and easier to follow.

Corrected:

public void add(T aData)
{       
    if(firstNode!=null){
        boolean found =false;
        Node currNode=firstNode;

        while(currNode != null){
            if(currNode.data.equals(aData)){
                currNode.addF();
                found=true;
                break;
            }
            currNode= currNode.next;
        }

        if(!found){
            Node tempNode=firstNode;
            firstNode= new Node(aData,tempNode);
        }
    }
    else {
        firstNode= new Node(aData,null);
    }
    numOfItems++; 
}

Corrected and shortened:

public void add(T aData)
{       
    boolean found =false;
    Node currNode=firstNode;

    while(currNode != null){
        if(currNode.data.equals(aData)){
            currNode.addF();
            found=true;
            break;
        }
        currNode= currNode.next;
    }

    if(!found){
        Node tempNode=firstNode;
        firstNode= new Node(aData,tempNode);
    }
    numOfItems++; 
}

Linked List Malfunctioning

1 Answers1