Check If Two Lists Are Equal Without Order Java

Comparing two lists for equality typically checks both their elements and their order. However, many real-world scenarios require evaluating lists based purely on their content, irrespective of the sequence in which elements appear. In this article, you will learn how to effectively check if two lists are equal in Java when the order of elements does not matter.

Problem Statement

The standard equals() method for List in Java considers two lists equal only if they have the same size and the elements at corresponding positions are equal. This means [1, 2, 3] is not equal to [3, 2, 1] using the default comparison. The challenge is to implement a comparison that evaluates [1, 2, 3] and [3, 2, 1] as equal, as they contain the same set of elements. This problem often arises in data validation, comparing query results, or checking if two collections of items are semantically identical.

Example

Consider two lists: list1 = [Apple, Banana, Orange] and list2 = [Orange, Apple, Banana]. If we use list1.equals(list2), the result will be false because the elements are not in the same order. Our goal is to achieve a true result for such cases.

Background & Knowledge Prerequisites

To understand the solutions presented, familiarity with the following Java concepts is beneficial:

• java.util.List: Basic understanding of list operations like adding elements, getting size, and iterating.
• java.util.Collections.sort(): Knowledge of how to sort a list.
• java.util.Set: Understanding of sets as collections that do not allow duplicate elements and have no inherent order. Specifically, HashSet.
• java.util.Map: Familiarity with HashMap for storing key-value pairs, particularly for counting element frequencies.
• Generics: Basic understanding of how generics are used with collections.

Use Cases or Case Studies

Order-independent list comparison is useful in various situations:

• Configuration Validation: Ensuring two configuration files, when parsed into lists of settings, contain the same set of parameters regardless of their order.
• API Response Comparison: Validating that an API endpoint returns the expected set of items, even if the server shuffles the order of results.
• Test Case Assertion: In unit tests, asserting that a method produced a specific collection of objects, where the output order is not guaranteed or relevant.
• Database Query Results: Comparing the result set of two different database queries to ensure they return the same data, even if the database's internal ordering differs.
• Permissions Management: Checking if a user's current permissions (represented as a list) match a required set of permissions, without strict order.

Solution Approaches

Here are three common approaches to compare two lists without considering the element order, each suitable for different scenarios.

Approach 1: Sorting and Comparing

This approach involves sorting both lists and then using their standard equals() method. This works because once sorted, if the lists contain the same elements, they will be in the same order, making a direct comparison valid.

• One-line summary: Sort both lists and then compare them using List.equals().

// List Equality By Sorting
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Create two lists with the same elements but different order
        List<String> list1 = new ArrayList<>(Arrays.asList("Apple", "Banana", "Orange"));
        List<String> list2 = new ArrayList<>(Arrays.asList("Orange", "Apple", "Banana"));
        List<String> list3 = new ArrayList<>(Arrays.asList("Apple", "Banana", "Grape")); // For negative test

        System.out.println("Original list1: " + list1);
        System.out.println("Original list2: " + list2);
        System.out.println("Original list3: " + list3);

        // Step 2: Create copies of the lists to avoid modifying originals
        List<String> sortedList1 = new ArrayList<>(list1);
        List<String> sortedList2 = new ArrayList<>(list2);
        List<String> sortedList3 = new ArrayList<>(list3);

        // Step 3: Sort the copied lists
        Collections.sort(sortedList1);
        Collections.sort(sortedList2);
        Collections.sort(sortedList3);

        System.out.println("\\nSorted list1: " + sortedList1);
        System.out.println("Sorted list2: " + sortedList2);
        System.out.println("Sorted list3: " + sortedList3);

        // Step 4: Compare the sorted lists using List.equals()
        boolean areEqual1And2 = sortedList1.equals(sortedList2);
        boolean areEqual1And3 = sortedList1.equals(sortedList3);

        System.out.println("\\nAre list1 and list2 equal (after sorting)? " + areEqual1And2);
        System.out.println("Are list1 and list3 equal (after sorting)? " + areEqual1And3);
    }
}

Run

• Sample Output:

Original list1: [Apple, Banana, Orange]
Original list2: [Orange, Apple, Banana]
Original list3: [Apple, Banana, Grape]

Sorted list1: [Apple, Banana, Orange]
Sorted list2: [Apple, Banana, Orange]
Sorted list3: [Apple, Banana, Grape]

Are list1 and list2 equal (after sorting)? true
Are list1 and list3 equal (after sorting)? false

• Stepwise Explanation:

1. Two List objects (list1, list2) are created, containing the same elements but in different orders. list3 is created for a negative test.
2. Copies of the original lists (sortedList1, sortedList2, sortedList3) are made to preserve the original lists if needed.
3. Collections.sort() is applied to each copied list, arranging their elements in natural order (or according to a custom Comparator if provided).
4. The equals() method of the sorted lists is then called. Since sortedList1 and sortedList2 now have the same elements in the same order, equals() returns true. sortedList1 and sortedList3 contain different elements, so equals() returns false.

Approach 2: Using Sets

This approach leverages the properties of Set collections, which inherently do not maintain order and do not allow duplicate elements. If two lists contain the same unique elements, converting them to sets and comparing the sets will yield true. This method implicitly ignores duplicates: [1, 2, 2] converted to a set becomes {1, 2}.

• One-line summary: Convert both lists to HashSet objects and compare the sets using Set.equals().

// List Equality Using Sets
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Create lists, including one with duplicates
        List<Integer> listA = new ArrayList<>(Arrays.asList(1, 2, 3, 2));
        List<Integer> listB = new ArrayList<>(Arrays.asList(3, 1, 2));
        List<Integer> listC = new ArrayList<>(Arrays.asList(1, 2, 4)); // Different element
        List<Integer> listD = new ArrayList<>(Arrays.asList(1, 2, 2, 3)); // Same elements, different duplicates

        System.out.println("Original listA: " + listA);
        System.out.println("Original listB: " + listB);
        System.out.println("Original listC: " + listC);
        System.out.println("Original listD: " + listD);

        // Step 2: Convert lists to sets
        Set<Integer> setA = new HashSet<>(listA);
        Set<Integer> setB = new HashSet<>(listB);
        Set<Integer> setC = new HashSet<>(listC);
        Set<Integer> setD = new HashSet<>(listD);

        System.out.println("\\nSet from listA: " + setA);
        System.out.println("Set from listB: " + setB);
        System.out.println("Set from listC: " + setC);
        System.out.println("Set from listD: " + setD);

        // Step 3: Compare the sets using Set.equals()
        boolean areEqualAAndB = setA.equals(setB);
        boolean areEqualAAndC = setA.equals(setC);
        boolean areEqualAAndD = setA.equals(setD); // Note: this will be true if sets are used

        System.out.println("\\nAre listA and listB equal (using sets)? " + areEqualAAndB);
        System.out.println("Are listA and listC equal (using sets)? " + areEqualAAndC);
        System.out.println("Are listA and listD equal (using sets)? " + areEqualAAndD);
    }
}

Run

• Sample Output:

Original listA: [1, 2, 3, 2]
Original listB: [3, 1, 2]
Original listC: [1, 2, 4]
Original listD: [1, 2, 2, 3]

Set from listA: [1, 2, 3]
Set from listB: [1, 2, 3]
Set from listC: [1, 2, 4]
Set from listD: [1, 2, 3]

Are listA and listB equal (using sets)? true
Are listA and listC equal (using sets)? false
Are listA and listD equal (using sets)? true

• Stepwise Explanation:

1. List objects are initialized. listA and listD contain duplicates, which Set will handle by storing only unique values.
2. Each List is passed to the HashSet constructor, which creates a set containing only the unique elements from the list.
3. The equals() method of Set is used to compare setA with setB, setC, and setD. Since setA, setB, and setD all contain the same unique elements {1, 2, 3}, their comparison yields true. setC contains {1, 2, 4}, making it unequal to setA. This approach is ideal when duplicates do not influence equality.

Approach 3: Frequency Map Comparison

When duplicate elements *do* matter (e.g., [1, 2, 2] is not considered equal to [1, 2]), a frequency map (or multiset) approach is most robust. This involves counting the occurrences of each element in both lists and then comparing these frequency maps.

• One-line summary: Create frequency maps for both lists (element to count) and then compare these maps.

// List Equality Using Frequency Maps
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// Main class containing the entry point of the program
public class Main {

    /**
     * Helper method to create a frequency map for a given list.
     * @param list The list to create a frequency map from.
     * @return A map where keys are list elements and values are their counts.
     */
    private static <T> Map<T, Integer> createFrequencyMap(List<T> list) {
        Map<T, Integer> frequencyMap = new HashMap<>();
        for (T item : list) {
            frequencyMap.put(item, frequencyMap.getOrDefault(item, 0) + 1);
        }
        return frequencyMap;
    }

    public static void main(String[] args) {
        // Step 1: Create lists with varying elements and duplicates
        List<String> listX = new ArrayList<>(Arrays.asList("A", "B", "A", "C"));
        List<String> listY = new ArrayList<>(Arrays.asList("A", "C", "B", "A"));
        List<String> listZ = new ArrayList<>(Arrays.asList("A", "B", "C")); // Fewer duplicates
        List<String> listW = new ArrayList<>(Arrays.asList("A", "B", "A", "D")); // Different element

        System.out.println("Original listX: " + listX);
        System.out.println("Original listY: " + listY);
        System.out.println("Original listZ: " + listZ);
        System.out.println("Original listW: " + listW);

        // Step 2: Create frequency maps for each list
        Map<String, Integer> freqMapX = createFrequencyMap(listX);
        Map<String, Integer> freqMapY = createFrequencyMap(listY);
        Map<String, Integer> freqMapZ = createFrequencyMap(listZ);
        Map<String, Integer> freqMapW = createFrequencyMap(listW);

        System.out.println("\\nFrequency Map for listX: " + freqMapX);
        System.out.println("Frequency Map for listY: " + freqMapY);
        System.out.println("Frequency Map for listZ: " + freqMapZ);
        System.out.println("Frequency Map for listW: " + freqMapW);

        // Step 3: Compare the frequency maps using Map.equals()
        boolean areEqualXAndY = freqMapX.equals(freqMapY);
        boolean areEqualXAndZ = freqMapX.equals(freqMapZ);
        boolean areEqualXAndW = freqMapX.equals(freqMapW);

        System.out.println("\\nAre listX and listY equal (using frequency maps)? " + areEqualXAndY);
        System.out.println("Are listX and listZ equal (using frequency maps)? " + areEqualXAndZ);
        System.out.println("Are listX and listW equal (using frequency maps)? " + areEqualXAndW);
    }
}

Run

• Sample Output:

Original listX: [A, B, A, C]
Original listY: [A, C, B, A]
Original listZ: [A, B, C]
Original listW: [A, B, A, D]

Frequency Map for listX: {A=2, B=1, C=1}
Frequency Map for listY: {A=2, B=1, C=1}
Frequency Map for listZ: {A=1, B=1, C=1}
Frequency Map for listW: {A=2, B=1, D=1}

Are listX and listY equal (using frequency maps)? true
Are listX and listZ equal (using frequency maps)? false
Are listX and listW equal (using frequency maps)? false

• Stepwise Explanation:

1. A helper method createFrequencyMap iterates through a list, building a HashMap where each element is a key and its value is the count of its occurrences in the list.
2. List objects are created, demonstrating different counts of elements.
3. createFrequencyMap is called for each list to generate their respective frequency maps.
4. The equals() method of Map is used to compare the generated frequency maps. freqMapX and freqMapY are equal because they both map A to 2, B to 1, and C to 1. freqMapX and freqMapZ are unequal because A has different counts. freqMapX and freqMapW are unequal because W contains D instead of C. This method provides the most comprehensive comparison when both element presence and their multiplicity (number of duplicates) are important, regardless of order.

Conclusion

Checking for list equality without considering order in Java can be achieved through several robust methods. The choice of method depends on whether duplicate elements should be treated as distinct or ignored. For simple cases where duplicates should be treated distinctly, sorting both lists and comparing them is an effective approach. When only the unique elements matter, converting lists to sets offers a concise solution. Finally, for scenarios where element multiplicity is crucial (i.e., [1,2,2] is different from [1,2]), comparing frequency maps provides the most accurate and flexible solution.

Summary

• Problem: Standard List.equals() considers order; we need order-independent comparison.
• Approach 1: Sorting: Copy lists, sort them, then use List.equals().
• Pros: Simple for lists with comparable elements, handles duplicates correctly.
• Cons: Modifies original lists (if not copied), adds sorting overhead.
• Approach 2: Sets: Convert lists to HashSet and compare sets.
• Pros: Concise, handles unique elements efficiently.
• Cons: Ignores duplicates (e.g., [1,2,2] becomes {1,2}).
• Approach 3: Frequency Maps: Create HashMaps of element counts for both lists and compare maps.
• Pros: Most robust, correctly handles duplicates and element counts.
• Cons: More complex implementation, higher memory usage for large lists.
• Recommendation: Choose based on whether duplicates should contribute to equality. Use Sorting or Frequency Maps if duplicates matter; use Sets if only unique elements matter.