Which data structure from Collections can efficiently store key-value mappings, preserve insertion ordering and allow efficient reverse traversal? The data structure must come from the original Java Collections, so using the Apache Commons library is out of the question.
I'm currently using a LinkedHashMap, which is ideal because it preserves insertion order, allows key-value mappings, and has add() and remove() methods that operate in O(1) time. The issue however, is that to reverse the LinkedHashMap, I need to perform a set-copy every time a new key is added:
List<Integer> reverseKeys = new ArrayList<>(keys);
Collections.reverse(reverseKeys);
which becomes very costly over large key sets (as was mentioned here: Iterating through a LinkedHashMap in reverse order).
Alternatively, I could use a TreeMap with a custom comparator to preserve insertion order, but this seems like a waste because add() and remove() will be running in O(n) time. The benefit of this approach is that the TreeMap has the descendingKeySet() method which would allow efficient reverse traversal.
My only other thought is to use an ArrayList of Entry objects, however I'm unsure how efficient this would be.
Which of these approaches would perform the best overall over a few thousand Key-value mappings? Are there any approaches that I haven't listed that would be a better alternative?
Do you HAVE to have only one variable? It is common approach to have same data multiple-times in different structure, if you want to query them often.
The add/remove costs more, however selecting can cost a lot less.
In your case, you can have LinkedList in reversed order (adding at zero position is O(1) ) and LinkedHashMap.
Ideally you should create your own class with these two variables and methods like "add/remove etc.", to make sure it is consistent.