Internal Working of LinkedHashMap in Java

Introduction

A LinkedHashMap in Java is a part of the java.util package and is used to store key-value pairs while maintaining insertion order. It extends HashMap and uses a doubly linked list to preserve the order of elements.

Unlike HashMap, which does not guarantee any specific iteration order, LinkedHashMap maintains the order in which elements were inserted, making it useful for caching and ordering-sensitive applications.

---

1. Data Structure Used

LinkedHashMap is implemented using a combination of HashMap and a doubly linked list. This ensures:

• Fast key lookups (O(1)) via a hash table.
• Maintaining insertion order via a doubly linked list.

Implementation in Java:

public class LinkedHashMap<K,V> extends HashMap<K,V> {
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
    }
    transient Entry<K,V> head, tail;
}

• head and tail maintain the order of elements.
• before and after pointers allow sequential traversal of elements.

Internally, LinkedHashMap extends HashMap but overrides specific methods to maintain order.

---

2. How Elements are Stored and Accessed

Adding an Element (put())

When put() is called:

1. The key-value pair is stored in the hash table.
2. A new node is added to the linked list to maintain order.
3. If the key already exists, the old value is replaced, but order remains unchanged.

Example:

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
System.out.println(map); // Output: {Apple=1, Banana=2, Cherry=3}

Retrieving an Element (get())

Elements are accessed in constant time (O(1)):

System.out.println(map.get("Banana")); // Output: 2

Removing an Element (remove())

When remove() is called:

1. The key is removed from the hash table.
2. The corresponding node is removed from the linked list.
3. The before and after pointers are updated to maintain order.

Example:

map.remove("Banana");
System.out.println(map); // Output: {Apple=1, Cherry=3}

---

3. Internal Working of LinkedHashMap

How the Linked List Works

• Each node contains references (before and after) to the previous and next nodes.
• When an element is inserted, it is linked to the previous last element.
• When iterating, elements are returned in insertion order.

Maintaining Insertion Order

Initial State:   head -> Apple -> Banana -> Cherry -> tail
After Removal:   head -> Apple -> Cherry -> tail

Access Order Mode (LRU Cache)

• By default, LinkedHashMap maintains insertion order.
• If created with accessOrder=true, the order is based on recent access (LRU – Least Recently Used).
• This makes LinkedHashMap useful for implementing LRU caches.

Example:

LinkedHashMap<Integer, String> lruMap = new LinkedHashMap<>(5, 0.75f, true);
lruMap.put(1, "A");
lruMap.put(2, "B");
lruMap.put(3, "C");
lruMap.get(1); // Moves '1' to the end (most recently used)
System.out.println(lruMap); // Output: {2=B, 3=C, 1=A}

---

4. Performance Analysis

Operation	Time Complexity
Insert (put())	O(1)
Get (get())	O(1)
Remove (remove())	O(1)
Iteration	O(n)

Comparison with HashMap and TreeMap

Feature	LinkedHashMap (Ordered)	HashMap (Unordered)	TreeMap (Sorted)
Maintains Order	✅ Yes (Insertion Order)	❌ No	✅ Yes (Sorted)
Performance	⚡ Fast (O(1))	⚡ Fast (O(1))	⏳ Slower (O(log n))
Best Use Case	Caching, Iteration Order	Fastest Lookups	Sorted Data Retrieval

---

5. Use Cases of LinkedHashMap

1. Maintaining Order in Caching Mechanisms: LRU cache implementation.
2. Preserving Insertion Order: Ensuring iteration order matches the insertion sequence.
3. Efficient Lookups with Order Constraints: Retains fast lookups like HashMap while maintaining order.

Example: Implementing an LRU Cache

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

---

6. Key Takeaways

✔ LinkedHashMap extends HashMap but maintains insertion order.

✔ Uses a doubly linked list for ordered iteration.

✔ Allows constant time (O(1)) lookups like HashMap.

✔ Supports access order mode for LRU cache implementations.

✔ Ideal for caching, ordering-sensitive applications, and predictable iteration.

Understanding the internal working of LinkedHashMap helps in selecting the right data structure when both fast lookups and ordering are required.