why linkedhashmap maintains doubly linked list for iteration

Question

As there is no internal and reasonable explanation in any thread. Please give me exact reason.

1. for the insertion order it is enough to maintain with singly linked list but why not?

2. how doubly linked list increases performance in this scenario?

3. all the methods are inherited from the hashmap xpt 4 methods then an iterator for hashmap not maintains the order whereas the linkedhashmap maintains the order?

Answer 1

You are right that you only need to maintain a singly linked list to keep track of insertion order. But in order to efficiently maintain a singly linked list, you actually need a doubly linked list.

Consider three entries in order

A ---> B ---> C

Suppose you remove B. Obviously A should now point to C. But unless you know the entry before B you cannot efficiently say which entry should now point to C. To fix this, you need entries to point in both directions.

  --->   ---> 
A      B      C
  <---   <---

This way, when you remove B you can just look at the entries before and after B (A and C) and update so that A and C point to each other.

The reason LinkedHashMap maintains insertion order while HashMap doesn't, despite the fact that all but 4 methods are inherited, is that it's very cleverly written. Most implementation-specific operations are members of HashMap.Entry, not HashMap. LinkedHashMap has a private static class LinkedHashMap.Entry which extends the static class HashMap.Entry of HashMap. When you call put or remove, for example, the code for LinkedHashMap can be the same as the code for HashMap because it is the entries themselves that keep track of before and after information. As an example, here is the code in full for LinkedHashMap.Entry.remove() that I was explaining above

private void remove() {
    before.after = after;
    after.before = before;
}

Answer 2

The LinkedHashMap basically maintains two pointers for each entry namely -: Before , After

as the name suggest both the pointers are used for the ordering purpose and are used to adjust the pointers in case of insertions or deletions.