Creating a Histogram from an Array using parallel Arraylists

Question

I writing a program learning arraylists. Essentially what it does is pulls from an array of Strings (each a word) and find the duplicates using to parallel arraylists. There are two arraylists one for the words and one for the number of times each word appears. The word in 0th spot of the words list corresponds to the number in the 0th spot of counts list and so on. I am successfully finding duplicate words and counting their occurrences but for words that occur only once I am getting a count of 2 and I can't seem to find out why. Here is the code

String[] wordList = fileContents.split("\\s");

        ArrayList<String> words = new ArrayList<String>();
        ArrayList<Integer> counts = new ArrayList<Integer>();
        words.add(wordList[0]);
        counts.add(0);
        for (int i = 0; i < wordList.length; i++) {
            String tempWord = wordList[i];
            boolean foundEqual = false;
            int count = 0;
            for(int q = 0;q < words.size();q++) {
                if (tempWord.equals(words.get(q))) {
                    foundEqual = true;
                    counts.add(q, counts.get(q) + 1);
                } 

            }
            if(!foundEqual){
                words.add(tempWord);
                counts.add(1);
            }

        }
        for (int i = 0; i < words.size(); i++) {
            System.out.println(words.get(i) + ":" + counts.get(i));
        }

Here are the words

this is a test
this is also a test
this is the last test

And here it the output, as you can see the last three items should be 1 but are 2.

this:3
is:3
a:2
test:3
also:2
the:2
last:2

Any help would be really appreciated!

Answer 1

When looking at the structure of counts and words in a debugger just before the print statement, it becomes clear that there is something amiss.

words:       counts
  0 = this     0 = 3
  1 = is       1 = 3
  2 = a        2 = 2
  3 = test     3 = 3
  4 = also     4 = 2
  5 = the      5 = 2
  6 = last     6 = 2
               7 = 1
               8 = 0
               9 = 1
              10 = 1
              11 = 1
              12 = 1
              13 = 1
              14 = 1

The problem is the add statement in the ArrayList. From the Javadocs:

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

And so, each time you are doing that counts.add(q, counts.get(q) + 1) you are inserting another element into the list. You should instead use set.

Setting a breakpoint on the for and running this through a debugger (eclipse debugging tutorial) I can look at the arrays as each one of them grows:

words:       counts
  0 = this     0 = 0

This is from the first bit of:

    words.add(wordList[0]);
    counts.add(0);

When it hits the for loop again:

words:       counts
  0 = this     0 = 1
               1 = 0

What happened there is that the counts.add(0,1) put a 1 at the 0th location and then shifted everything else in the array down.

After several iterations of the not finding, we are back to this again.

words:       counts
  0 = this     0 = 1
  1 = is       1 = 0
  2 = a        2 = 1
  3 = test     3 = 1
               4 = 1

And then matching the 'this' again:

words:       counts
  0 = this     0 = 2
  1 = is       1 = 1
  2 = a        2 = 0
  3 = test     3 = 1
               4 = 1
               5 = 1

And you should be able to see how this structure is growing incorrectly.

Answer 2

Aside: your main loop should start at i = 1, since i = 0 is covered before the loop starts.

The bug is that you're counting the first occurence on each subsequent trip through. Change q = 0 to q = i + 1 to avoid that.

You'll also have to check your end conditions because of that.