Iterating through a LinkedHashMap in reverse order

Question

I have a LinkedHashMap:

LinkedHashMap<String, RecordItemElement>

that I need to iterate through from a given key's position, backwards. So if I was given the 10th item's key, I'd need iterate backwards through the hashmap 9, 8, 7 etc.

• Android Killer: Do you know the keys of all items or not ?
• Dominic Bou-Samra: I do. Suggesting I iterate through once, add to a list, then iterate that backwards using them as keys? Suppose that would work
• rogerdpack: I assume you just want to iterate in reverse in "order of insertion" here, or do you want real ordering based on some natural ordering? See also stackoverflow.com/a/1936472/32453

Answer 1

The question requires a LinkedHashMap in reverse order, some answers suggesting using a TreeSet but this will reorder the map based upon the key.

This solution allows the iteration over the original LinkedHashMap not the new ArrayList as has also been proposed:

List<String> reverseOrderedKeys = new ArrayList<String>(linkedHashMap.keySet());
Collections.reverse(reverseOrderedKeys);
for (String key : reverseOrderedKeys) {
 RecordItemElement line = linkedHashMap.get(key);
}

• M. Justin: I'd personally create a List<Entry<String, RecordItemElement>> using new ArrayList<>(linkedHashMap.entrySet()) and use the entries' keys & values, rather than storing just the keys and doing a second map lookup to get the value for each key.

Answer 2

The HashMap:

HashMap<Integer, String> map = new HashMap<Integer, String>();

Reverse iterating over values:

ListIterator<Sprite> iterator = new ArrayList<String>(map.values()).listIterator(map.size());
while (iterator.hasPrevious()) String value = iterator.previous();

Reverse iterating over keys:

ListIterator<Integer> iterator = new ArrayList(map.keySet()).listIterator(map.size());
while (iterator.hasPrevious()) Integer key = iterator.previous();

Reverse iterating over both:

ListIterator<Map.Entry<Integer, String>> iterator = new ArrayList<Map.Entry<Integer, String>>(map.entrySet()).listIterator(map.size());
while (iterator.hasPrevious()) Map.Entry<Integer, String> entry = iterator.previous();

Answer 3

You don't have to iterate through it. But it would be handy to pull the keys off and store it in a list. Thats the only way you can do indexOf() type operations.

List<String> keyList = new ArrayList<String>(map.keySet());
// Given 10th element's key
String key = "aKey";
int idx = keyList.indexOf(key);
for ( int i = idx ; i >= 0 ; i-- ) 
 System.out.println(map.get(keyList.get(i)));

• Shimi Bandiel: Instead of keyList.indexOf(...) use listIterator with the position. and iterate with previous()
• Óscar López: Instead of keyList.indexOf(...) use keyList.size()-1
• Pacerier: @Kal The operation of your solution is O(n), which is well.. horrible.
• Anton: Well doing so you create unnecessary overhead by copying the key set. Consider using TreeMap.
• Chthonic Project: The LinkedHashMap#keySet() returns a Set backed by a LinkedKeySet, which is a nested class with package-local visibility. The iteration order is defined by its Spliterator, which is ordered in the same order as the map entries. So, in this case, the order IS guaranteed.

Answer 4

new LinkedList(linkedHashMap.keySet()).descendingIterator();

Answer 5

As of Java 21, LinkedHashMap has the reversed() method, which returns a reversed view of the map. This can be iterated over in the standard manner.

myLinkedHashMap.reversed().forEach((key, value) -> {
 // Do something with the key and/or value
});

To specifically start with a given key as requested, a Stream over the reversed map's entry set could be used, using the dropWhile method to skip all elements encountered prior to that key:

String matchingKey = "someKey";
myLinkedHashMap.entrySet().stream()
 .dropWhile(e -> !matchingKey.equals(e.getKey()))
 .forEach(e -> {
 String key = e.getKey();
 RecordItemElement value = e.getValue();
 // Do something with key & value
 });

Answer 6

Using "user22745008" solution and labdas with some generics you can have a very neat solution as a method:

 public static <T, Q> LinkedHashMap<T, Q> reverseMap(LinkedHashMap<T, Q> toReverse)
 {
 LinkedHashMap<T, Q> reversedMap = new LinkedHashMap<>();
 List<T> reverseOrderedKeys = new ArrayList<>(toReverse.keySet());
 Collections.reverse(reverseOrderedKeys);
 reverseOrderedKeys.forEach((key)->reversedMap.put(key,toReverse.get(key)));
 return reversedMap;
 }

Answer 7

This is an old question, but I think it's lacking an answer that takes a newer approach. The following uses Java 9 features:

Deque<Map.Entry<String, RecordItemElement>> top = map.entrySet().stream()
 .takeWhile(e -> !givenKey.equals(e.getKey()))
 .collect(Collectors.toCollection(ArrayDeque::new));

The code above streams the map's entryset, keeping entries until a key equal to the given key is found. Then, the entries are collected to an ArrayDeque.

One detail is missing, though. Depending on whether you need the entry that matches the given key to also be included in the result or not, you might need to manually add it to the deque. If you don't want it added, then you're done. Otherwise, simply do:

top.add(Map.entry(givenKey, map.get(givenKey)));

Now, to iterate the Deque in reverse order, simply use its descendingIterator():

Iterator<Map.Entry<String, RecordItemElement>> descIt = top.descendingIterator();

It's worth mentioning that this approach only works if the stream is sequential. Anyways, we wouldn't have gained anything using a parallel stream here.