Swapnil - 6 months ago 32

Java Question

Any idea why

`contains`

`firstSchema.contains(firstSchema.get(0))`

`List<String> firstSchema = new ArrayList<String>();`

firstSchema.add(0,"test");

firstSchema.add(1,"testy");

if(!(firstSchema.contains(firstSchema))){

System.out.println("hey arraylist content matched");

}

Even No luck for

`if(!(firstSchema.contains("test"))){`

System.out.println("hey arraylist content matched");

}

Answer

The simplest way to check if a list contains any elements from another list is to call `contains()`

on one of the lists, passing *each element* as an argument in turn. Something like:

```
public <E> boolean slowListContains(List<E> a, List<E> b) {
for (E element : a) {
if (b.contains(element)) {
return true;
}
}
return false;
}
```

This is slow, however, because `contains()`

is a linear operation (`O(n)`

), and since we're calling it in a loop the `slowListContains()`

function takes quadratic time (`O(n^2)`

) which is poor. We can do better.

A `Set`

(or more precisely a hash-based set such as `HashSet`

) has an efficient `contains()`

method which runs in less-than-linear time (constant time in the case of `HashSet`

). Converting one or the other list into a `Set`

will make the loop in `slowListContains()`

much faster. Something like:

```
public <E> boolean fasterListContains(List<E> a, List<E> b) {
Set<E> aSet = new HashSet<>();
aSet.addAll(a);
for (E element : b) {
if (aSet.contains(b)) {
return true;
}
}
return false;
}
```

This isn't perfect, but it's certainly much faster than the naive solution. A slight improvement would be to always convert the smaller list into the `Set`

, rather than the first one. You could also take arbitrary `Iterable`

parameters rather than `List`

parameters, then check if either of them are already a `Set`

and if so skip the set-construction step.