How to prevent the adding of duplicate objects to an ArrayList [duplicate]

Question

Possible Duplicate:
Prevent duplicate entries in arraylist

I have an arraylist of a particular class C.

List<C> myList = new ArrayList<C>();

Class C has two attributes viz.

String str1;
String str2;

Now as and when I am adding objects of type C to the ArrayList myList, I want to check if there already exists an object in the list with the values of str1 and str2 matching the values of the parameters (str1 and str2) of the object I am about to add.

Is there any efficient way to do this without having to iterate everytime through the complete list and checking for matching between the parameters?

Answer 1

When you need to check for duplicates or ensure unique values, consider using a Set - like data structure, rather than a List.

You can choose from one of the below -

• HashSet

  • Faster access - O(1) access roughly speaking.
  • not sorted
  • Hash table used as base storage.

• TreeSet

  • Slower access (relative to HashSet) - O(log(n))
  • values sorted automatically.
  • Red-Black tree used as base storage.

Set automatically only allows unique values. Attempts to add values that previously exist will fail.

Note that for this to work you will need to override equals and hashcode to tell the Set how to compare your objects. This step is better explained at What issues should be considered when overriding equals and hashCode in Java?

Answer 2

You need to override the equals method in Class C.

e.g.

public boolean equals(Object c) {
    if(c !instanceof C) {
        return false;
    }

    C that = (C)c;
    return this.str1.equals(that.getStr1()) && this.str2.equals(that.getStr2());
}

Then you can call myList.contains(viz) to see if the list already contains an equal object.

This is untested, you may want some additional error handling.

If you do override the equals method like this, you should also make sure you override the hashcode() method. See: http://www.technofundo.com/tech/java/equalhash.html

Edit: As pointed out in the comments, the set implementation is going to be more efficient, though you will still need to override equals / hashcode method so the above example may be best used in conjunction with Karthiks answer above.