Most efficient way to find duplicates in a linkedlist of linkedlist of strings - java

Question

Let us suppose we have a linkedlist of linkedlist of strings.

LinkedList<LinkedList<String>> lls = new LinkedList<LinkedList<String>> ();
LinkedList<String> list1 = new LinkedList<String>(Arrays.asList("dog", "cat", "snake"));
LinkedList<String> list2 = new LinkedList<String>(Arrays.asList("donkey", "fox", "dog"));
LinkedList<String> list3 = new LinkedList<String>(Arrays.asList("horse", "cat", "pig"));
lls.add(list1);
lls.add(list2);
lls.add(list3);

As you can see, this 3 linkedlist of strings are different but also have some elements in common. My goal is to write a function that compares each list with the others and returns TRUE if there is at least one element in common (dog is in list1 and list2), FALSE otherwise.

I think that the first thing I need is to compare all possible permutation among lists and the comparison between lists is element by element. I'm not sure this is the most efficient approach. Could you suggest an idea that is eventually most efficient?

you need this one: `for(item : lls){System.out.println(yourFunc(item, lls))}`? — degr, Jan 25 '17 at 15:23
I would use a [`HashSet`](https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html) instead of LinkedList, if you have the option. — dsh, Jan 25 '17 at 15:24

score 2 · Accepted Answer · answered Jan 25 '17 at 15:41

Assuming that the given lists should not be changed by removing elements or sorting them (which has O(nlogn) complexity, by the way), you basically need one function as a "building block" for the actual solution. Namely, a function that checks whether one collection contains any element that is contained in another collection.

Of course, this can be solved by using Collection#contains on the second collection. But for some collections (particularly, for lists), this has O(n), and the overall running time of the check would be O(n*n).

To avoid this, you can create a Set that contains all elements of the second collection. For a Set, the contains method is guaranteed to be O(1).

Then, the actual check can be done conveniently, with Stream#anyMatch:

containing.stream().anyMatch(e -> set.contains(e))

So the complete example could be

import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class DuplicatesInLinkedLists
{
    public static void main(String[] args)
    {
        LinkedList<LinkedList<String>> lls =
            new LinkedList<LinkedList<String>>();
        LinkedList<String> list1 =
            new LinkedList<String>(Arrays.asList("dog", "cat", "snake"));
        LinkedList<String> list2 =
            new LinkedList<String>(Arrays.asList("donkey", "fox", "dog"));
        LinkedList<String> list3 =
            new LinkedList<String>(Arrays.asList("horse", "cat", "pig"));
        lls.add(list1);
        lls.add(list2);
        lls.add(list3);

        checkDuplicates(lls);
    }

    private static void checkDuplicates(
        List<? extends Collection<?>> collections)
    {
        for (int i = 0; i < collections.size(); i++)
        {
            for (int j = i + 1; j < collections.size(); j++)
            {
                Collection<?> ci = collections.get(i);
                Collection<?> cj = collections.get(j);
                boolean b = containsAny(ci, cj);
                System.out.println(
                    "Collection " + ci + " contains any of " + cj + ": " + b);
            }
        }
    }

    private static boolean containsAny(Collection<?> containing,
        Collection<?> contained)
    {
        Set<Object> set = new LinkedHashSet<Object>(contained);
        return containing.stream().anyMatch(e -> set.contains(e));
    }
}

A side note: The code that you posted almost certainly does not make sense in the current form. The declaration and creation of the lists should usually rely on List:

List<List<String>> lists = new ArrayList<List<String>>();
lists.add(Arrays.asList("dog", "cat", "snake");
...

If the elements of the list have to me modifiable, then you could write

lists.add(new ArrayList<String>(Arrays.asList("dog", "cat", "snake"));

or, analogously, use LinkedList instead of ArrayList, but for the sketched use case, I can't imagine why there should be a strong reason to deliberately use LinkedList at all...

Thank you for the brilliant solution and explanation. One more question: you said that there is no reason to use LinkedList and ArrayList is better in this case. Could you explain why this is preferrable? I want to clarify that once my list of list of strings is created, it will never be modified, even the elements inside. — user840718, Jan 25 '17 at 15:52
@user840718 This is related to [programming to an interface](http://stackoverflow.com/q/383947/). You would write `LinkedList` when you want to use methods that are *only* offered by `LinkedList` - for example, when you want to use `list.getLast()`. But when all the functionality that you really *need* is already defined in the `List` interface, then you should only use the `List` interface. There is no reason to use a more specific type then. Also, if the lists are not modified, then `Arrays.asList` is fine: It *does* return an unmodifiable `List` - no reason to create a copy. — Marco13, Jan 25 '17 at 16:04

score 0 · Answer 2 · answered Jan 25 '17 at 15:26

Add all the items in all lists to one single list, then sort it (Collections.sort). Then iterate through it and check for duplicates.

E.g.

ArrayList<String> list = new ArrayList<>();
list.addAll(list1); // Add the others as well
Collections.Sort(list);
for (String s : list) {
    If (the item is the same as the previous item) {
        return true;
    }
}

score 0 · Answer 3 · answered Jan 25 '17 at 15:33

0

Use retainAll()

    for (final LinkedList<String> ll : lls)
    {
        list1.retainAll(ll);
    }
    System.out.println("list1 = " + list1);

answered Jan 25 '17 at 15:33

Tobias Otto

1,634
13
20

score 0 · Answer 4 · answered Jan 25 '17 at 15:35

LinkedList is not the best collection for duplicates detection. If you can, try to use HashSet, but if you can not do it you still can put all elements from list to set. Hashset contains elemnts without duplicates, so if there is a duplicated element in list size of hashset will contain less elements than all lists.

score 0 · Answer 5 · answered Jan 25 '17 at 15:56

Assuming you want to use LinkedLists and aren't allowed convert to another data structure, what you could do is create a method that accepts a variable amount of LinkedLists. From there you want to grab all unique combinations of LinkedLists, and then compare all unique elements between those linked lists, if you find a common element mark that pair of linked lists as common. How you want to keep track of/return the data (set of linkedlist pairs that have an element in common for example) depends on what your output is supposed to look like, but that's the general structure of the code that i would use.

Most efficient way to find duplicates in a linkedlist of linkedlist of strings - java

5 Answers5