Remove duplicate items from a LinkedList, where the nested collection items can be in any order

Question

I have Nested LinkedList which contains Some elements.I want to Remove Duplicate Inner LinkedList From Outter LinkedList.The order of element Does not Matter.[Cat,Mouse,Dog] is Same As [Mouse,Cat,Dog] and I Want To remove 1 Of Them. example:

suppose

[[Cat,Mouse,Dog],[Dog,Mouse,Cat],[Dog,Horse,Cat],[Dog,Tiger,Lion]] 

then I Want Output like this

[[Cat,Mouse,Dog],[Dog,Horse,Cat],[Dog,Tiger,Lion]]

I have tried it. but I want Optimal Solution...... My code is as below

for (int iBoardListCnt = 0; this.roomCombinationsMasterList != null && iBoardListCnt < this.roomCombinationsMasterList.size(); iBoardListCnt++) {

        LinkedList<Board> alRoomCombinationList = new LinkedList<>();
        alRoomCombinationList = this.roomCombinationsMasterList.get(iBoardListCnt);
        ArrayList<String> alTemp = new ArrayList();
        for (int icount = 0; icount < alRoomCombinationList.size(); icount++) {
            alTemp.add((alRoomCombinationList.get(icount).getRoomDescription() + alRoomCombinationList.get(icount).getDescription()).toString());
        }
        roomCombinationsMasterList.remove(iBoardListCnt);



        Collections.sort(alTemp, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.compareToIgnoreCase(s2);
            }
        });

        Iterator<LinkedList<Board>> iterator = roomCombinationsMasterList.iterator();
        while (iterator.hasNext()) {

            ArrayList<String> alTemp1 = new ArrayList<>();
            for (Board data : iterator.next()) {
                alTemp1.add((data.getRoomDescription() + data.getDescription()).toString());

            }
            Collections.sort(alTemp1, new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    return s1.compareToIgnoreCase(s2);
                }
            });

            if (alTemp.equals(alTemp1)) {
                iterator.remove();
                continue;
            }

        }

        roomCombinationsMasterList.add(iBoardListCnt, alRoomCombinationList);

    }

In this code i have taken Fist element from Nested LinkedList. stored in to the temporally LinkedList i removed that element from main arraylist.Now i have the next element from LinkedList stored into 2nd temporally LinkedList. Sort both LinkedList using Comparator And using equals() method compare those two LinkedList.If both are same then remove 1 of them using Iterator. please give me Optimal Solution over It.

Answer 1

There are several ways to remove duplicate elements from your list. The "optimal" solution you are up to will require using appropriate data structure, which is optimized for contains operation. In your case it will be HashSet.

The idea is that while traversing your original collection in the same time you maintain the set of traversed elements and check if the current element was already traversed. This approach modifies your original collection in place.

    List<List<String>> input = new LinkedList<List<String>>(Arrays.asList(
            Arrays.asList("Cat", "Mouse", "Dog"),
            Arrays.asList("Dog", "Mouse", "Cat"),
            Arrays.asList("Dog", "Horse", "Cat"),
            Arrays.asList("Dog", "Tiger", "Lion")));

    Set<Set<String>> distinctElements = new HashSet<Set<String>>();

    for (Iterator<List<String>> iterator = input.iterator(); iterator.hasNext(); ) {
        List<String> element = iterator.next();
        HashSet<String> elementAsSet = new HashSet<String>(element);
        if (!distinctElements.contains(elementAsSet)) {
            distinctElements.add(elementAsSet);
        } else {
            iterator.remove();
        }
    }

    System.out.println(input);

Second option will be transforming your original list of lists into LinkedHashSet<LinkedHashSet<String>>. LinkedHashSet behaves like a Set and List at the same time (actually, it has both of these data structures under the hood). So it eliminates duplicates while preserving the order of elements, just as you need. Probably it's not an option for you, as you said that you have to preserve your collection type, but still, it's a good (and short) option worth consideration.

    LinkedHashSet<LinkedHashSet<String>> results = new LinkedHashSet<LinkedHashSet<String>>();
    for (List<String> strings : input) {
        results.add(new LinkedHashSet<>(strings));
    }
    System.out.println(results);

And finally the one-liner for Java 8:

LinkedList<LinkedList<String>> results = input.stream().map(LinkedHashSet::new).distinct()
        .map(LinkedList::new).collect(Collectors.toCollection(() -> new LinkedList<LinkedList<String>>()));

Or it's shorter version if you don't care about the type of returned collection:

List<List<String>> results = input.stream().map(LinkedHashSet::new).distinct()
        .map(LinkedList::new).collect(Collectors.toList());