LinkedHashSet - insertion order and duplicates - keep newest "on top"

Question

I need a collection that keeps insertion order and has unique values. LinkedHashSet looks like the way to go, but there's one problem - when two items are equal, it removes the newest one (which makes sense), here's an example:

set.add("one");
set.add("two");
set.add("three");
set.add("two");

The LinkedHashSet will print:

one, two, three

But what I need is:

one, three, two

What would be the best solution here? Is there any collection/collections method that can do this or should I implement it manually?

Solution 1

Most of the Java Collections can be extended for tweaking.

Subclass LinkedHashSet, overriding the add method.

class TweakedHashSet<T> extends LinkedHashSet<T> {

    @Override
    public boolean add(T e) {
        // Get rid of old one.
        boolean wasThere = remove(e);
        // Add it.
        super.add(e);
        // Contract is "true if this set did not already contain the specified element"
        return !wasThere;
    }

}

Solution 2

You can simply use a special feature of LinkedHashMap:

Set<String> set = Collections.newSetFromMap(new LinkedHashMap<>(16, 0.75f, true));
set.add("one");
set.add("two");
set.add("three");
set.add("two");
System.out.println(set); // prints [one, three, two]

In Oracle’s JRE the LinkedHashSet is backed by a LinkedHashMap anyway, so there’s not much functional difference, but the special constructor used here configures the LinkedHashMap to change the order on every access not only on insertion. This might sound as being too much, but in fact affects the insertion of already contained keys (values in the sense of the Set) only. The other affected Map operations (namely get) are not used by the returned Set.

If you’re not using Java 8, you have to help the compiler a bit due to the limited type inference:

Set<String> set
    = Collections.newSetFromMap(new LinkedHashMap<String, Boolean>(16, 0.75f, true));

but the functionality is the same.

Solution 3

When initializing you're LinkedHashSet you could override the add method.

Set<String> set = new LinkedHashSet<String>(){
    @Override
    public boolean add(String s) {
        if(contains(s))
            remove(s);
        return super.add(s);
    }
};

Now it gives you:

set.add("1");
set.add("2");
set.add("3");
set.add("1");
set.addAll(Collections.singleton("2"));

// [3, 1 ,2]

even the addAll method is working.

Solution 4

All solution provided above are excellent but if we don't want to override already implemented collections. We can solve this problem simply by using an ArrayList with a little trick

We can create a method which you will use to insert data into your list

public static <T> void addToList(List<T> list, T element) {
    list.remove(element); // Will remove element from list, if list contains it
    list.add(element); // Will add element again to the list 
}

And we can call this method to add element to our list

List<String> list = new ArrayList<>();

addToList(list, "one");
addToList(list, "two");
addToList(list, "three");
addToList(list, "two");

Only disadvantage here is we need to call our custom addToList() method everytime instead of list.add()

View more solutions