Java - java.util.List problem

Question

I have a java.util.ArrayList<Item> and an Item object.

Now, I want to obtain the number of times the Item is stored in the arraylist.

I know that I can do arrayList.contains() check but it returns true, irrespective of whether it contains one or more Items.

Q1. How can I find the number of time the Item is stored in the list?

==================================================================================

Q2. Also, If the list contains more than one Item, then how can I determine the index of other Items because arrayList.indexOf(item) returns the index of only first Item every time?

Answer 1

This is easy to do by hand.

public int countNumberEqual(ArrayList<Item> itemList, Item itemToCheck) {
    int count = 0;
    for (Item i : itemList) {
        if (i.equals(itemToCheck)) {
          count++;
        }
    }
    return count;
}

Keep in mind that if you don't override equals in your Item class, this method will use object identity (as this is the implementation of Object.equals()).

Edit: Regarding your second question (please try to limit posts to one question apiece), you can do this by hand as well.

public List<Integer> indices(ArrayList<Item> items, Item itemToCheck) {
    ArrayList<Integer> ret = new ArrayList<Integer>();
    for (int i = 0; i < items.size(); i++) {
        if (items.get(i).equals(itemToCheck)) {
            ret.add(i);
        }
    }
    return ret;
}

Answer 2

You can use Collections class:

public static int frequency(Collection<?> c, Object o)

Returns the number of elements in the specified collection equal to the specified object. More formally, returns the number of elements e in the collection such that (o == null ? e == null : o.equals(e)).

If you need to count occurencies of a long list many times I suggest you to use an HashMap to store the counters and update them while you insert new items to the list. This would avoid calculating any kind of counters.. but of course you won't have indices.

HashMap<Item, Integer> counters = new HashMap<Item, Integer>(5000);
ArrayList<Item> items = new ArrayList<Item>(5000);

void insert(Item newEl)
{
   if (counters.contains(newEl))
     counters.put(newEl, counters.get(newEl)+1);
   else
     counters.put(newEl, 1);

   items.add(newEl);
 }

A final hint: you can use other collections framework (like Apache Collections) and use a Bag datastructure that is described as

Defines a collection that counts the number of times an object appears in the collection.

So exactly what you need..

Answer 3

As the other respondents have already said, if you're firmly committed to storing your items in an unordered ArrayList, then counting items will take O(n) time, where n is the number of items in the list. Here at SO, we give advice but we don't do magic!

As I just hinted, if the list gets searched a lot more than it's modified, it might make sense to keep it sorted. If your list is sorted then you can find your item in O(log n) time, which is a lot quicker; and if you have a hashcode implementation that goes well with your equals, all the identical items will be right next to each other.

Another possibility would be to create and maintain two data structures in parallel. You could use a HashMap containing your items as keys and their count as values. You'd be obligated to update this second structure any time your list changes, but item count lookups would be o(1).

Answer 4

I could be wrong, but it seems to me like the data structure you actually want might be a Multiset (from google-collections/guava) rather than a List. It allows multiples, unlike Set, but doesn't actually care about the order. Given that, it has a int count(Object element) method that does exactly what you want. And since it isn't a list and has implementations backed by a HashMap, getting the count is considerably more efficient.

Answer 5

Thanks for your all nice suggestion. But this below code is really very useful as we dont have any search method with List that can give number of occurance.

void insert(Item newEl) 
{ 
   if (counters.contains(newEl)) 
     counters.put(newEl, counters.get(newEl)+1); 
   else 
     counters.put(newEl, 1); 

   items.add(newEl); 
 } 

Thanks to Jack. Good posting.

Thanks,

Binod Suman

http://binodsuman.blogspot.com