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.

Solution 1

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

Solution 2

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);
}

Solution 3

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();

Solution 4

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

View more solutions

Comments

[Dave Thomas]

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.

[trss]

Doesn't a Set destroy the order? Consequently, wouldn't keyList contain the keys in random order?

[trss]

I suppose it works because the documentation says the returned Set is backed by the LinkedHashMap. Seems flaky though, since there is generally no guarantee on the order of iteration of a Set.

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