Java - How to find count of items in a list in another list

Question

Say I have two lists:

List<String>products = new ArrayList<String>(); 
products.add("computer"); 
products.add("phone"); 
products.add("mouse"); 
products.add("keyboard"); 

List<String>cart = new ArrayList<String>(); 
cart.add("phone"); 
cart.add("monitor"); 

I need to find how many items in the cart list exist in the products list. For the lists above, the answer would be 1 (as phone is in products and cart). If the cart list was:

List<String>cart = new ArrayList<String>(); 
cart.add("desk"); 
cart.add("chair"); 

The result would be 0. If cart contained computer, mouse, desk, chair, the result would be 2 (for computer and mouse).

Is there something in the Apache Commons Collections or the Google Collections API? I've looked through them and see ways to get a bag count, but not from another list, although it's possible I'm missing something. Right now, the only way I can think of is to iterate over the cart items and see if products contains the individual item and keep a count. I can't use containsAll as I need the count (not a boolean), and that would fail if all items in cart didn't exist in the product list (which can happen).

I'm using Java 1.6 if that matters.

Answer 1

int count = 0;
for (String item : cart) {
   if (products.contains(item))
    count++;
   }
}

Answer 2

If creating another collection is not a constraint then just add the list elements from both lists to a Set. Then the difference in final set size and sum of sizes of two lists is your answer

Answer 3

I'm pretty sure the static frequency-method in Collections would come in handy here:

List<String>products = ...
List<String>cart = ...

for (String cartItem : cart) {
       int occurrences = Collections.frequency(products, cartItem);

       if (occurrences > 0) {
          System.out.println(cartItem + ": " + occurrences);
       }
} 

This is jdk 1.6 straight up. If the item in the cart-list exists in products, it will be printed with the number of occurrences. Just remove the if-clause if you want to print 0-occurrences as well.

Answer 4

If you're willing to create another collection, you could do the following:

List<String> productsInCart = new ArrayList<String>(products);
productsInCart.retainAll(cart);

That'll give you all of the entries that appear in both cart and products.

Answer 5

For one extra line of code to sort (plus the run-time cost) and then calling a different method to do the containment check, you can get something that may very efficient for a list of products that is very long (as long as the list is efficient for random access and the list order of products isn't significant to the app):

Collections.sort(products);  // or maintain products in sort order at all times
int count = 0;
for(String i: cart) {
  if (Collections.binarySearch(products, i) >= 0) {
    count++;
  }
}

Answer 6

If your data set is small or if you do not care about speed, bart's answer should suffice. But when you have a large data set and do not want the O(N*N) complexity, you can use this (assuming no product name duplicated)

Set<String> productsSet = new HashSet<String>(products);

Then use Bart's code with products replaced by productsSet.

This should give you the result in O(N) time, although will cost more memory.

Answer 7

Many of the solutions posted work for "I need to find how many items in the cart list exist in the products list.", but they may be based on different assumptions.

Some work if you assume that each element in product or cart must be unique. In this case, you may want to enforce this by using HashSet instead of ArrayList.

Others work even works for repeated elements in the cart, if we assume that if an element is in product, there exists unlimited number of that particular product. It wouldn't work if we cannot assume this, i.e. we assume that that the number of occurrence of an element in product means the number of stock the company has. In this case, you may want to consider using other data structures such as HashMap.

I guess in the end it boils down to the assumptions made. You should find out the exact conditions and determine which solution best suits your problem.