LinkedHashMap walkthrough

LinkedHashMap is a data structure that stores key value pairs just as a HashMap, but with the added advantage of preserving insertion order.
To understand internal working of LinkedHashMap, understanding HashMap implementations are important. You can go through https://delveintojava.blogspot.com/2019/11/hashmap-walkthrough.html before starting this section.

LinkedHashMap extends HashMap and implements Map interface. It's nodes contain two extra pointers to track the previous and next nodes in terms of the insertion order.

The figure shows the internal structure of LinkedHashMap. As you can see in the figure, the before and after references point to the entries that were inserted before and after that node.

The following code would result into the LinkedHashMap internal structuring as shown in the figure.

LinkedHashMap<String, String> linkedHM = new LinkedHashMap<>();
linkedHM.put("key1", "val1");
linkedHM.put("key2", "val2");
linkedHM.put("key3", "val3");
linkedHM.put("key4", "val4");
System.out.println(linkedHM);

OUTPUT: {key1=val1, key2=val2, key3=val3, key4=val4}

Let's break things down. Let's see the constructor of LinkedHashMap entry.

As you can see, Entries in linkedHashMap extends HashMap.Node, so the structure of entries is the same as HashMap node with the addition of two more references - before and after.

Apart from that, we can also see two entry member variables declared - head and tail. These are required to track the first node and last node that was inserted in the LinkedHashMap.

Whenever new key value pair is inserted in the LinkedHashMap, the insertion happens in the same way as a HashMap. But before insertion, the new entry is linked with the last entry that was inserted (Note that till this point node is not linked with the last node in the bucket. The new entry is just linked to the last inserted entry). Let's see what happens when a new entry is created.

This is the overridden newNode method of HashMap. So, whenever HashMap's putVal method is called to insert key value pairs, it internally calls newNode implementation of LinkedHashMap to take care of maintaining insertion order.
As you can see after creation of the new node, it is linked with the last node that was inserted in the function - linkNodeLast. If it's the first node, the node is saved as head. The new node is made the tail node, and linked with the previous node.

So, you can tell that bucket maintains singly linked list that will be used to search a key in the same bucket. And the insertion order is maintained by a doubly linked list implementation, where each node might point to nodes in other buckets.

So, now let's see how the iterator in LinkedHashMap works. How does it return the entries in the order they were inserted ?

The only thing worth noting is the traversal to the next node. In the nextNode - second last line, next node is pointing to the after reference, and not the next reference in entry node. Since after refers to the insertion order, the traversal too happens in the insertion order.

References:
http://androidxref.com/9.0.0_r3/xref/libcore/ojluni/src/main/java/java/util/LinkedHashMap.java
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/LinkedHashMap.java