2

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.

nybon
  • 8,894
  • 9
  • 59
  • 67
  • Please cover my tutorial [Internal life of LinkedHashMap](http://volodial.blogspot.com/2013/07/internal-life-of-linkedhashmap-in-java.html) to know better LinkedHashSet because the latter is just a wrapper of the former – Volodymyr Levytskyi Jul 30 '13 at 15:20
  • I would recommend to use LinkedHashMap here. Because after inserting a mapping you can get it very quickly by key. Anyway LinkedHashSet is LinkedHashMap. – Volodymyr Levytskyi Jul 30 '13 at 16:26
  • Voting to reopen, since while retrieving the last element in a `LinkedHashSet` is very similar to doing the same for `LinkedHashMap`, they are two distinct types with different semantics and methods to achieve the goal. – M. Justin Jun 13 '23 at 04:39
  • I'm retracting my repoen vote. The question has a valid duplicate, just not the one mentioned in the close reason. This is a duplicate of https://stackoverflow.com/q/14024022/1108305. – M. Justin Jun 13 '23 at 04:52

1 Answers1

2

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).

Thomas
  • 87,414
  • 12
  • 119
  • 157
  • Thanks for letting me know the "dirty way" to do this, and I ended up with writing my own LinkedHashSet variant. – nybon Jul 26 '13 at 23:58
  • @VolodymyrLevytskyi besides your manners (calling someone a liar), you should prove your claims. When iterating, the most recently inserted element is last in the order, unless you have your own implementation that does it the other way round. – Thomas Jul 30 '13 at 15:25
  • Sorry! The truth is the most recently added element is at the head of linked list and is the last when iterating... – Volodymyr Levytskyi Jul 30 '13 at 15:54
  • @VolodymyrLevytskyi I had a look at the code (in JDK 6, but I doubt there were many changes) and that doesn't seem to true. The `header` entry will always be an empty entry and any new entry will be added before the header. However, since the list is doubly linked, there's no real "head" besides the element that is referenced as `header` and this reference doesn't seem to be changed at all. – Thomas Jul 30 '13 at 15:56
  • Variable "header" references the first inserted element by its "after" variable and the most recently added element by its "before" variable. Variable "header" is used whenever you iterate linked list because its "after" variable references the first inserted Entry. Variable "header" has also its "before" variable that is used whenever new Entry is created. header.before references the most recently inserted Entry in order to link the future Entry to the current one comprising linked list . Cover my tutorial and it will get clear. I was hasting and made a mistake about iteration order. – Volodymyr Levytskyi Jul 30 '13 at 16:07
  • @VolodymyrLevytskyi please read my answer again, that's just what I said: get the head (ok, it's called `header`), then its predecessor (`before`) which is the most recently inserted entry. – Thomas Jul 30 '13 at 16:11