How to count distinct Strings in ArrayList without using Set?

Question

How do you count the number of distinct Strings in an ArrayList without using the Set data structure in the Java libraries?

I made two ArrayLists, one stored and one empty and want to store the empty one with distinct Strings. What am I doing wrongly?

public void distinctCount (WordStream words) {
ArrayList<String> loaded = new ArrayList<String>();
  ArrayList<String> empty = new ArrayList<String>();
  int count = 0;

  // Fill loaded with word stream
  for(String i : words) {
    loaded.add(i);
  }

  // Fill empty with loaded
  // Catch collisions
  for(int i = 0; i < loaded.size(); i++) {
    if(loaded.get(i) != empty.get(i)) {
      empty.add(loaded.get(i));
    }
  }
  return empty.size();
}

Answer 1

Here is a very bad / slow option you have:

for(String s: loaded){
    if(!empty.contains(s)){
        empty.add(s);
    }
}

or if you are Java 8 fan:

empty = loaded.stream().distinct().collect(Collectors.toList())

Answer 2

The problem is that you're comparing only corresponding elements. Meaning that you compare the n^th element with the n^th element in the second arraylist.

The straightforward solution would be having nested loops: for each element in the first arraylist, loop over all elements in the second array list, if no match found - you know it's distinct. This solution's complexity is O(n²).

Of course there are many helpful methods in the ArrayList API that can make your life much easier. If there's no restriction on other data structures, you can consider using Map as well.