Get the items difference between two lists in Java

Question

I'm trying to get the items difference between two lists, but, sometimes one list is bigger than other, sometimes one is smaller and sometimes they are equal. Also, missing objects can happen in both lists.

I found good solutions to get the difference between two lists, like How can I return the difference between two lists?, but no one considers 2 lists.

I saw Find common and different elements between two list in java too, but it isn't exactly what I'm asking.

I elaborate one example to illustrate what I want to do.

Consider one list of ordered items, and one list of sent items. They must be equal because client must receive the items that he ordered.

So I did this way:

public class Main {
    public static void main(String[] args) {
        // Case 1
        List<String> order1 = Arrays.asList(new String[] { "A", "B" });
        List<String> sended1 = Arrays.asList(new String[] { "A", "B" });

        // No difference
        System.out.println("Case 1: " + getDifference(order1, sended1));

        // Case 2
        List<String> order2 = Arrays.asList(new String[] { "A", "B", "C" });
        List<String> sended2 = Arrays.asList(new String[] { "B", "C" });

        // "1 item(s) missing in sended: A"
        System.out.println("Case 2: " + getDifference(order2, sended2));

        // Case 3
        List<String> order3 = Arrays.asList(new String[] { "A", "D" });
        List<String> sended3 = Arrays.asList(new String[] { "A", "B", "C", "D" });

        // "2 item(s) missing in order: B, C"
        System.out.println("Case 3: " + getDifference(order3, sended3));

        // Case 4
        List<String> order4 = Arrays.asList(new String[] { "A", "D", "F" });
        List<String> sended4 = Arrays.asList(new String[] { "A", "B", "C", "D" });

        // 1 item(s) missing in sended: "F" & 2 item(s) missing in order: "B", "C"
        System.out.println("Case 4: " + getDifference(order4, sended4));
    }

    private static String getDifference(List<String> order, List<String> sended) {
        StringBuilder output = new StringBuilder();

        if (order.equals(sended)) {
            output.append("No difference");

        } else {
            List<String> auxOrder = new ArrayList<>(order);
            auxOrder.removeAll(sended);

            if (auxOrder.size() > 0) {
                output.append(auxOrder.size()).append(" item(s) missing in sended: ");
                output.append("\"").append(String.join("\", \"", auxOrder)).append("\"");
            }

            List<String> auxSended = new ArrayList<>(sended);
            auxSended.removeAll(order);

            if (auxSended.size() > 0) {
                if (output.length() > 0) {
                    output.append(" & ");
                }

                output.append(auxSended.size()).append(" item(s) missing in order: ");
                output.append("\"").append(String.join("\", \"", auxSended)).append("\"");
            }
        }
        return output.toString();
    }
}

It works, but I'm not sure that it is the best way to do it, so I ask for your help!

Answer 1

Using Java 8 streams:

Logic Here:

I have used the java 8 stream operation to get the difference between two given lists and created a output message using StringBuilder as mentioned in the problem statement.

Code:

public class Test {
    public static void main(String[] args) {
        // Case 1
        List<String> order1 = Arrays.asList("A", "B");
        List<String> sended1 = Arrays.asList("A", "B");
        System.out.println("Case 1: " + getMissingItems(order1,sended1));

        // Case 2
        List<String> order2 = Arrays.asList("A", "B", "C");
        List<String> sended2 = Arrays.asList("B", "C");
        System.out.println("Case 2: " + getMissingItems(order2,sended2));

        // Case 3
        List<String> order3 = Arrays.asList("A", "D");
        List<String> sended3 = Arrays.asList("A", "B", "C", "D");
        System.out.println("Case 3: " + getMissingItems(order3,sended3));

        // Case 4
        List<String> order4 = Arrays.asList("A", "D", "F");
        List<String> sended4 = Arrays.asList("A", "B", "C", "D");
        System.out.println("Case 4: " + getMissingItems(order4,sended4));
    }

    private static String getMissingItems(List<String> order, 
                                          List<String> sended){
        StringBuilder sb = new StringBuilder();
        List<String> missingInOrder = getMissingInList(order, sended);
        createMessage(sb, missingInOrder," item(s) missing in order: ");
        List<String> missingInSended = getMissingInList(sended, order);
        if(!missingInOrder.isEmpty() && !missingInSended.isEmpty()){
            sb.append(" && ");
        }
        createMessage(sb, missingInSended," item(s) missing in sended: ");
        return sb.isEmpty() ? "No difference":sb.toString();
    }

    private static void createMessage(StringBuilder sb, 
                                      List<String> diffInList,
                                      String msg) {
        if(!diffInList.isEmpty()){
            sb.append(diffInList.size())
              .append(msg)
              .append(String.join(",", diffInList));
        }
    }

    private static List<String> getMissingInList(List<String> list1, 
                                                 List<String> list2) {
        return list2.stream()
                    .filter(e -> !list1.contains(e))
                    .collect(Collectors.toList());
    }
}

Output:

Case 1: No difference
Case 2: 1 item(s) missing in sended: A
Case 3: 2 item(s) missing in order: B,C
Case 4: 2 item(s) missing in order: B,C && 1 item(s) missing in sended:F

Answer 2

First, it's not clear enough if there are duplicates or not. Secondly, if you don't care about order then don't use the list equals() method as it will fail in many cases where both lists contains the same items but in different order.

Besides that, the algorithm should work but it could be optimized. I believe the main problem is that using the removeAll() method between a list of size n and a list of size m has a worst time complexity of O(n*m) (quadratic) when you could actually achieve a time complexity of O(n+m) (lineal). If you don't care about duplicates you could slightly modify your solution to use HashSet to achieve this goal in the following way:

// If duplicates are irrelevant
private static String getDifference(List<String> ordered, List<String> sent) {
    Set<String> orderedSet = new HashSet<>(ordered);
    Set<String> sentSet = new HashSet<>(sent);
    if (orderedSet.equals(sentSet)) {
        return "No difference";
    } else {
        StringBuilder output = new StringBuilder();
        orderedSet.removeAll(sent);

        if (!orderedSet.isEmpty()) {
            output.append(orderedSet.size()).append(" item(s) missing in sent: ");
            output.append("\"").append(String.join("\", \"", orderedSet)).append("\"");
        }

        sentSet.removeAll(ordered);

        if (!sentSet.isEmpty()) {
            if (output.length() > 0) {
                output.append(" & ");
            }

            output.append(sentSet.size()).append(" item(s) missing in ordered: ");
            output.append("\"").append(String.join("\", \"", sentSet)).append("\"");
        }

        return output.toString();
    }
}

If you care about duplicates then you aren't actually comparing Lists but Multisets. For a Multiset implementation you could use the Guava library. A possible implementation with Multisets looks like this:

// If duplicates are relevant, with Guava
private static String getDifferenceWithDuplicates(List<String> ordered, List<String> sent) {
    Multiset<String> orderedSet = HashMultiset.<String>create(ordered);
    Multiset<String> sentSet = HashMultiset.<String>create(sent);
    if (orderedSet.equals(sentSet)) {
        return "No difference";
    } else {
        StringBuilder output = new StringBuilder();

        for (String item : Sets.union(orderedSet.elementSet(), sentSet.elementSet())) {
            int orderedCount = orderedSet.count(item);
            int sentCount = sentSet.count(item);

            if (orderedCount != sentCount) {
                if (output.length() > 0) {
                    output.append(" & ");
                }

                output.append(Math.abs(orderedCount - sentCount)).append(" item(s) missing in ");
                output.append(orderedCount > sentCount ? "sent" : "ordered").append(": ");
                output.append("\"").append(item).append("\"");
            }
        }
        return output.toString();
    }
}

If for some reason you can't use Guava, then you can implement the same behavior of a HashMultiset using a HashMap of type Map<String, Integer> where the key is the item and the value is the amount of appearances in the original list (this is an exercise for the reader).