Calculate asymmetric difference of two lists in Java 1.4

Question

I've got two lists:

List x = [1, 2, 5, 7, 8];
List y = [1, 3, 4, 5];

I'm trying to get the following calculated asymmetric differences:

x - y (what's in x that's not in y) => 2 7 8
y - x (what's in y that's not in x) => 3 4

I've already checked some pointers on this and this, but I have some constraints on my back:

1. What I'm trying to implement is exactly what guava's Sets.difference offers, except I'm stuck with Java 1.4 (I'm easily able to change my implementation from using Lists to Sets)

2. Using Collection.removeAll/retainAll would be a deal breaker, as those methods work in-place. The objects I'm holding in the lists are some heavyish POJOS that are actually mapped to Hibernate.

3. In this sense, I need something that should work out of a hash-based implementation, as this calculation is already implemented in those POJOS.

Bottom line is, is there anything like Sets utility class for Java 1.4? Or something that could calculate the asymmetric difference of two collections?

Answer 1

Working in-place may be fine for short lists, but with hundreds of elements, converting to HashSet should be faster. But is speed your problem? You didn't mention it, but if not then everything you need is provided by the JDK even in your ancient version. I'm not sure what's your goal, so I'm proposing multiple options.

In case you want to remove from x everything contained in y, do either x.removeAll(y) or x.removeAll(new HashSet(y)). The former is faster for short lists, the latter for long ones.

In case you don't want to modify x, I'd suggest to create a copy. Creating a view the way Guava does is possible, but it's more work and working with the view is slower than working directly with a collection (especially when working with large Lists as they have slow contains).

In case you want to simultaneously remove from both x and y the elements of the other list, then do this: HashSet xx = new HashSet(x), yy = HashSet(y); x.removeAll(y); y.removeAll(x);.

Note that by creating new collections, no objects get copied, just new references to old objects get created.