Removing objects from a list that don't appear in a list of ID's

Question

I have a list of objects with each of them having an ID. I have a second list that is just a list of media ID's. I want to remove the objects from the first list that don't match a mediaID contained in the second list. What is an efficient way of going about this? The only way I could think of was to have a nested for loop but that seems inefficient.

Here is my implementation. Note that "items" is the first list, containing MediaDetailsItem objects, with each of these objects having a specific mediaId. The second list is mediaIds.

List<MediaDetailsItem> shortenedList = new ArrayList<MediaDetailsItem>();
                        for(MediaDetailsItem item : items){
                            for(String id : mediaIds){
                                if(item.getMediaId().equals(id)){
                                    shortenedList.add(item);
                                    break;
                                }
                            }
                        }
                        items.clear();
                        items.addAll(shortenedList);

Answer 1

Since the for (String id : mediaIds) { ... } loop iterates over all the entries of mediaIds, this is inefficient, a linear search, for each item in items. The overall time-complexity of this approach is \$O(n^2)\$.

What is the type of mediaIds? If it's a Set, then you could replace the entire inner loop with a simple conditional a call to mediaIds.contains(...):

for (MediaDetailsItem item : items) {
  if (mediaIds.contains(item.getMediaId())) {
    shortenedList.add(item);
  }
}

This will improve the time-complexity to \$O(n)\$.

If the type of mediaIds is not a Set, you could build one:

Set<String> ids = new HashSet<>(mediaIds);

And then adjust the condition: ids.contains(item.getMediaId())

Answer 2

You can do this without external iteration, if you are using java-8:

items.removeIf(item -> !mediaIds.contains(item.getMediaId()));

It's not necessary to create a new list, this will modify the existing one.