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?

3
  • I do not think doubly linked list help the ordering , it just makes traversing the list easier Jan 13, 2015 at 6:29
  • 2
    It doesn't make traversal easier. It simply makes removal of map entries more efficient.
    – Stephen C
    Jan 14, 2015 at 2:31
  • So that you can go backwards.
    – user207421
    Apr 28, 2018 at 9:27

6 Answers 6

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;
}
2
  • Nice and simply put.
    – Basixp
    Aug 22, 2019 at 19:35
  • Thank you so much!! Now i understood why singly Linked list was not enough.
    – aatif
    Jan 15, 2021 at 5:25
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.

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.

4
  • 2
    I do not think doubly linked list help the ordering , it just makes traversing the list easier Jan 13, 2015 at 6: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, 2015 at 6: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, 2015 at 8: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, 2015 at 2: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.

0

The other answers cover why the doubly linked list is currently needed. Java 21 has an additional reason: the reversed method on 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.

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.