15

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?

Kick Buttowski
  • 6,709
  • 13
  • 37
  • 58
Mohamed Rafic S
  • 161
  • 1
  • 5

6 Answers6

17

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;
}
Paul Boddington
  • 37,127
  • 10
  • 65
  • 116
3

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.

Puneet_Techie
  • 197
  • 6
1

To maintain Insertion Order there is doubly LinkedList. AT any point of time you can move ahead node or backward Node. But if you are having single LinkedList if your Pointer moved to last element you again need to start from initial point and you can not moved on previous node.

Prashant
  • 2,556
  • 2
  • 20
  • 26
  • 2
    I do not think doubly linked list help the ordering , it just makes traversing the list easier – Kick Buttowski Jan 13 '15 at 06:29
  • If you see internally HashMap is based on linkedList. so if you are having information like which node was inserted before or after then that is simply an ordering. – Prashant Jan 13 '15 at 06:34
  • A singly linked list is sufficient to maintain an order. This is not the correct explanation for why they have used a doubly linked list in this context. – Stephen C Jan 13 '15 at 08:53
  • 2
    And it should be noted that `LinkedHashMap.keySet().iterator()` returns an plain `Iterator` not a `ListIterator`. You CANNOT iterate the keys in reverse insertion order ... irrespective of the fact that a doubly-linked list is used. The APIs don't allow it. – Stephen C Jan 14 '15 at 02:30
0

One thing I would also like to add is that LinkedHashMap can also be used as an LRU Cache by setting it's accessOrder boolean to true via its constructor.

Now LinkedHashMap maintains two pointers head(eldest of the LinkedHashMap) and tails(youngest of the LinkedHashMap). So keep in mind when you set accessOrder to true it stops maintaining the insertion-order and starts behaving like a proper LRU cache.

Now when LRU cache exceeds its limit and we want to remove the eldest entry, as it maintains DoublyLinkedList internally the removal of eldest entry is comparatively fast, as it maintains two pointers(head and tails) which can move in both directions or we can say if it was a Singly LinkedList for removing eldest entry we need to traverse all the nodes and then remove it. Thanks to pointers head and tails it can easily be done by just removing the last node(eldest one) by reaching there with help of tails pointer and taking that last node's previous pointer to make second last node tail of the DoublyLinkedList in LinkedHashMap.

Gurinder
  • 943
  • 2
  • 9
  • 19
0

The other answers cover why the doubly linked list is currently needed. Java 21 is adding an additional reason: A reversed method is being added to LinkedHashMap which provides a reversed view of the map. The backwards links are needed to efficiently iterate through the list backwards to provide this view.

M. Justin
  • 14,487
  • 7
  • 91
  • 130
-1

LinkedHashMap can be used for maintaining the insertion order and for maintaining the access order. LinkedHashMap inherited the same functionality of hashmap for maintain list in bucket,so used next reference.

For maintaining the insertion order they used doubly linked list(used before and after reference),but that can be done by using singly linked list. At the same time they have to achieve the access order functionality and in that they need frequent movement of the element to the end and that require frequent deletion for frequent deletion they used doubly linked list .

user1464350
  • 9
  • 2