Fetch the most recent inserted element in LinkedHashSet efficiently [duplicate]

Question

This question already has answers here:

Java LinkedHashMap get first or last entry (16 answers)

Closed 6 years ago.

According to LinkedHashSet's Javadoc, it will keep the insertion order of inserted elements by using a doubly linked list internally.

it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order)

If I want to fetch the first inserted element, I can use code like:

linkedHashSet.iterator().next()

This will give me the first inserted element in the set in O(1).

I am trying to solve a problem, which requires me to access the most recent inserted element into the set in O(1), and let's assume there will not be any duplicated element inserted into the set. For example,

linkedHashSet.add(2); // the most recent inserted element in the set is 2
linkedHashSet.add(3); // the most recent inserted element in the set is 3
linkedHashSet.add(5); // the most recent inserted element in the set is 5
linkedHashSet.remove(5); // the most recent inserted element in the set is 3 because 5 is removed and not in the set now

Since it is a doubly linked list in the set, it seems the most recent element should be the last one in the doubly linked list and should be able to be accessed in O(1) if there is some API to get it.

My question is: is there any way in JDK to do this or do I need to create my own ReversedIteratingLinkedHashSet to do this?

Basically, I try to find a Set data structure with O(1) time complexity for all operations including: insertion/deletion/search/check the most recent inserted element in the set. The built in LinkedHashSet seems a good fit with a very small modification internally but I am not sure if this can be done with default JDK class API or not.

Note: I checked JDK's source code and know that LinkedHashSet is internally implemented with LinkedHashMap, and if there is any solution that could use LinkedHashMap to access the most recent inserted element in O(1), it is useful for me too.

Thanks a lot.

Answer 1

Unfortunately, it seems like there's no direct/clean way to access the most recently added element in a LinkedHashSet (or LinkedHashMap) in O(1).

A clean way would be to convert the set into an array and access the last element, but that would be O(n).

A dirty way would be to use reflection to access the internal hash map, the map's head entry and finally the entry's predecessor (before).