Is it possible to iterate LinkedHashMap in both the ways as it is implemented with help of Doubly Linked List?

Question

Is it possible to iterate LinkedHashMap in both the ways as it is implemented with help of Doubly Linked List ?

Answer 1

Not directly. The LinkedHashMap itself doesn't even provide a way to get an iterator (unless you count forEach()), so you'd need to iterate either the keySet(), entrySet() or values(). They only provide a regular forward-only Iterator.

It would be possible to create a List out of the entrySet(). It would keep the order and you could then iterate it as you wish, but you do incur the cost of creating the List.

Answer 2

Design

From a designers point of view, technically the current implementation of LinkedHashMap would be able to do so.

However they don't provide access to this. That also allows the developer to change the internal implementation someday. If they would provide both iteration directions, they would need to stick to that for the future in order to ensure backwards compatibility.

By the documentation, the only benefit of a LinkedHashMap should be to ensure iteration in insertion order, nothing more. So it only provides stuff needed for exactly that goal.

---

Manual (extra cost)

Without deploying reflection you won't be able to access the internal LinkedList and won't be able to iterate in both directions.

You can of course manually create a LinkedList on your own and use that for iteration in both directions:

LinkedHashMap<K, V> map = ...

LinkedList<Entry<K, V>> entries = new LinkedList<>(map.entrySet());
Iterator<Entry<K, V>> descIter = entries.descendingIterator();

while (descIter.hasNext()) {
    Entry<K, V> entry = descIter.next();
    ...
}

---

Reflection (no extra cost but discouraged)

Using reflection you can however access the internal LinkedList, note that this is strongly discouraged in general. It is not that easy since the linked list is implemented manually, therefore refer to an implementation like from OpenJDK version 8u40-b25.

First we need to access the tail element of LinkedHashMap:

transient LinkedHashMap.Entry<K,V> tail;

Therefore we need to make it public first and then retrieve the value:

Class<?> c = map.getClass();
Field tailField = c.getDeclaredField("tail");
tailField.setAccessible(true);
Object tailValue = tailField.get(map);
Entry<K, V> tail = (Entry<K, V>) tailValue;

Now you can start iterating using the tail, following the before field of LinkedHashMap.Entry:

Entry<K,V> before, after;

Iteration then looks like this:

LinkedHashMap<K, V> map = ...

// Get tail as seen before
Entry<K, V> tail = ...

// Preparation for accessing "before" element
Class<?> c = tail.getClass();
Field beforeField = c.getDeclaredField("before");
beforeField.setAccessible(true);

Entry<K, V> entry = tail;
while (entry != null) {
    // Do something with entry
    ...

    // Get next element
    Object beforeValue = beforeField.get(entry);
    entry = (Entry<K, V>) beforeValue;
}

Be aware that by this you break the intended design of the class. You should be aware of why reflection is discouraged in general. Your code will break if the designers change the implementation of the class in the future.