0

I know this kind of question is asked in stackoverflow lots of time before. But my issue is little bit different and I could not find any similar scenario, so posting this question here

Problem: I need to remove duplicate objects from ArrayList. Structure of my arrayList is as below

dataList.add(new ObjectClass("a","b"));
dataList.add(new ObjectClass("c","n"));
dataList.add(new ObjectClass("b","a")); // should be counted as duplicate
dataList.add(new ObjectClass("z","x"));

I need to remove objects from above list such as, it treats combination of "a,b" and "b,a" as duplicates and remove any of those duplicate

My solution: step 1) Override equals method in DataClass class

class DataClass {
      String source;
      String destination;
    
      DataClass(String src, String dest) {
        this.source = src;
        this.destination = dest;
      }
    
      // getter setter for source and destination variables

    @Override
    public boolean equals(Object obj) {
        System.out.println("inside equals");
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        ObjectClass other = (ObjectClass) obj;
        if(i.equals(other.getJ())
            && j.equals(other.getI())) {
            return true;
        } else return false;
    }

step 2) method to remove duplicates

public List<DataClass> removeDuplicates(List<DataClass> dataList) {
            List<DataClass> resultList = new ArrayList<DataClass>();
        
            // Convert array list to Linked list
            LinkedList<DataClass> linkedList = new LinkedList<DataClass>();
            for(DataClass obj: dataList) {
                linkedList.add(obj);
            }
            
            // Iterate through linked list and remove if values are duplicates
            for(int i = 0; i<linkedList.size();i++) {
              for(int j = i+1;j<linkedList.size();j++) {
                if(linkedList.get(j).equals(linkedList.get(i))) {
                    linkedList.remove();
                }
              }
            }
            resultList.addAll(linkedList);
            return resultList;
        }

I am still looking for any better optimized solution, if there is any. Thanks in advance

Update with solution : my equals method was needed to correct some comparison logic. So here is my updated ObjectClass instead of DataClass including correct overridden equals method

public class ObjectClass {
    String i;
    String j;
    public  ObjectClass(String i, String j) {
        this.i = i;
        this.j = j;
    }
    // getters setters
    // override hashcode
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        ObjectClass other = (ObjectClass) obj;

        if((i.equals(other.getJ()) || i.equals(other.getI()))
            && (j.equals(other.getI()) || j.equals(other.getJ()))) {
            return true;
        } else return false;
    }   
}
  1. After fixing equals method I tried below implementation in removeDuplicate method as Janos mentioned and it is working fine as expected

     for(ObjectClass obj: dataList) {
         if(!resultList.contains(obj))
             resultList.add(obj);
     }
    
4
  • 3
    Perhaps you're looking for... a Set?
    – Rogue
    Dec 9, 2017 at 6:57
  • 1
    Do you mean new DataClass("a","b") and new DataClass("z","x") are duplicates (equals) ? And why there is ObjectClass in the equals method of DataClass?
    – vinS
    Dec 9, 2017 at 7:01
  • The issues in this Question have indeed been handled many many times already on Stack Overflow. Please search thoroughly before posting. Dec 9, 2017 at 8:44
  • @vinS: No, i mean (a,b) and (b,a) are duplicates
    – Rohan
    Dec 10, 2017 at 2:27

4 Answers 4

3

There are several problems here:

class DataClass {
      String source;
      String destination;

      // ...

    @Override
    public boolean equals(Object obj) {
        // ...
        ObjectClass other = (ObjectClass) obj;
        if(i.equals(other.getJ())
            && j.equals(other.getI())) {
            return true;
        } else return false;
    }

The equals method casts the other object to ObjectClass. It should cast to the same class where this method is defined: DataClass.

The equals method compares i and j variables, but they are not defined anywhere within the class. There's source and destination.

The equals method will return true when this.i is the same as other.j and this.j is the same as other.i, and return false otherwise. In other words, (a, b) will be equal to (b, a). But it will not be equal to itself. That's very strange, and probably not what you intended.


The removeDuplicates method is overcomplicated. For example converting an array list to a linked list is unnecessary. Here's a much simpler algorithm:

  • For each value in the source list
    • If the value does not exist in the result list, add it to the result list

That's it.

List<DataClass> result = new ArrayList<>();

for (DataClass item : dataList) {
    if (!result.contains(item)) {
        result.add(item);
    }
}
return result;

This assumes that the implementation of the equals method is fixed. Otherwise the result.contains step will not work correctly.

Also note that result.contains performs a linear search: it checks every item until it finds a match. You could improve performance by using a set.

3
  • Just a simple suggestion for improving performance. If the constraint is such that its always a single character in "source" and "destination" then we could have a temporary array of size: 'z' + 'z' = 244 + 1 = 245. Notice that any combination of two character is same, e.g: 'a' + 'b' = 195 = 'b' + 'a', so first time we see a combination 'a' + 'b' we set that index-195 to '1' and second time when we see that 'b' + 'a' and see that index-195 is already 1, then we can safely say that its a repetition. O(n) complexity for finding is now O(1). Dec 9, 2017 at 7:17
  • @ShababbKarim: Initially I though the same solution. But as of now I am not sure if my object values would be character only all the time. So just to implement more generic logic, I was trying different options. Thanks for your time though
    – Rohan
    Dec 10, 2017 at 3:01
  • @janos: sorry for code mess of DataClass/ObjectClass. I updated the answer above. fixing equals method and iteration over arraylist worked very fine. Thank you so much
    – Rohan
    Dec 10, 2017 at 3:03
1

With your code

    linkedList.remove();

Each time it removes an item from linkedList, the indexes of all following items are decremented. That is going to mess up your iteration loop.

1
  • True. Removed linkedList logic :)
    – Rohan
    Dec 10, 2017 at 3:03
0

Use HashSet for equals and hashCode so that it does not distinguish order.:

class DataClass {
  String source;
  String destination;
  private final Set<String> content = new HashSet< String >();

  DataClass(String src, String dest) {
    this.source = src;
    this.destination = dest;
    content.add(src);
    content.add(dest);
  }

  // getter setter for source and destination variables

@Override
public boolean equals(Object obj) {
    System.out.println("inside equals");
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (!DataClass.class.equals(obj.getClass()))
        return false;
    DataClass other = (DataClass) obj;
    return content.equals(other.content);
}

public int hashCode() {
    return content.hashCode();
}

For further reading to how to implement equals and hashCode, you might want to read https://www.mkyong.com/java/java-how-to-overrides-equals-and-hashcode/


Use LinkedHashSet for finding duplicates:

public List<DataClass> removeDuplicates(List<DataClass> dataList) {
    return new ArrayList<DataClass>(new LinkedHashSet<DataClass>(dataList));
}

Why we use LinkedHashSet instead of HashSet? LinkedHashSet preserves ordering while HashSet does not. Quoted from LinkedHashSet javadoc:

This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).

1
  • Yes. LinkedHashSet is good solution too. But I went with existing ArrayList logic since it requires minimum changes in ObjectClass. Thank you for your feedback
    – Rohan
    Dec 10, 2017 at 3:06
0

example:

DataClass dc = new DataClass("a","b");
List<DataClass> resultList = new ArrayList<DataClass>();
resultList .add(dc);

for (int i=0; i < resultList.size(); i++) {
 if(resultList.get(i).source.equals(dc.source) && resultList.get(i).destination.equals(dc.destination) || resultList.get(i).source.equals(dc.destination) && resultList.get(i).destination.equals(dc.source)) {
    resultList.remove(i);
 }
}
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.