LinkedHashMap

TL;DR

• LinkedHashMap extends HashMap.
• It maintains a doubly-linked list running through all its entries.
• This guarantees Predictable Iteration Order (by default, the order in which keys were inserted).
• Performance is slightly slower than HashMap due to maintaining the linked list.

Concept

A standard HashMap scrambles the order of keys. If you want to iterate over the keys in the exact order you added them, you must use a LinkedHashMap.

Access Order vs Insertion Order

By default, LinkedHashMap maintains Insertion Order. However, it has a special constructor that allows it to maintain Access Order instead. In access order mode, every time an element is accessed (via get or put), it is moved to the end of the list. This makes LinkedHashMap the perfect data structure for building an LRU (Least Recently Used) Cache.

Examples

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // --- 1. Default: Insertion Order ---
        Map<String, String> insertionMap = new LinkedHashMap<>();
        insertionMap.put("1", "One");
        insertionMap.put("2", "Two");
        insertionMap.put("3", "Three");
        
        System.out.println(insertionMap.keySet()); // [1, 2, 3] always!
        
        // --- 2. Special: Access Order (LRU Cache Basics) ---
        // initialCapacity, loadFactor, accessOrder (true)
        Map<String, String> accessMap = new LinkedHashMap<>(16, 0.75f, true);
        accessMap.put("A", "Apple");
        accessMap.put("B", "Banana");
        accessMap.put("C", "Cherry");
        
        // Accessing "A" moves it to the end of the line!
        accessMap.get("A");
        
        System.out.println(accessMap.keySet()); // [B, C, A]
    }
}

Interview Questions

Q: How would you implement an LRU Cache using LinkedHashMap?
A: You would instantiate a LinkedHashMap with accessOrder = true. Then, you would override its protected removeEldestEntry() method. This method is called automatically by put(). If you make it return true whenever the size() > MAX_CAPACITY, the map will automatically delete the least recently used entry (the one at the head of the list) to make room for new items.

Q: Does updating a value in a LinkedHashMap affect its insertion order?
A: No. If you re-insert a key that already exists (e.g., map.put("A", "NewValue")), the value is updated, but its position in the insertion-ordered linked list remains exactly the same. (Unless the map is in access-order mode, in which case it is moved to the end).