3

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?

Community
  • 1
  • 1
Chris Abbott
  • 316
  • 3
  • 9
  • 1
    `TreeMap` would be my approach. A few thousand entries is relatively small, and I wouldn't worry about O(n) performance for add / remove. – vikingsteve Oct 13 '15 at 13:20

1 Answers1

2

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.

libik
  • 22,239
  • 9
  • 44
  • 87
  • 1
    Just to add to this answer, you can then wrap them both in a new data structure that will do the dirty work of owning and updating both via one common interface. – Jose Martinez Oct 13 '15 at 15:32
  • It doesn't look very elegant, but it definitely did do the job and met my efficiency requirements. Thanks! – Chris Abbott Oct 13 '15 at 18:15