LinkedHashMap

LinkedHashMap is an implementation of the Map interface that maintains a predictable iteration order while still offering fast key-based access. It combines the performance of HashMap with order preservation using a linked list. This is a high-frequency interview topic, especially compared with HashMap and TreeMap.

What Is LinkedHashMap?

• Implementation of Map
• Stores key-value pairs
• Maintains order (insertion or access order)
• Allows one null key and multiple null values
• Part of java.util package

Map<Integer, String> map = new LinkedHashMap<>();
          

Position in Map Hierarchy

Map
 └── HashMap
      └── LinkedHashMap
          

✔ LinkedHashMap extends HashMap

Key Characteristics of LinkedHashMap

• Predictable iteration order
• Slightly slower than HashMap
• Faster than TreeMap
• Not synchronized (not thread-safe)
• Uses hashing + linked list

How LinkedHashMap Works Internally (Interview Favorite)

• Backed by a HashMap
• Maintains a doubly linked list of entries
• Each entry has:
  • before reference
  • after reference

HashMap + Doubly Linked List = LinkedHashMap

✔ HashMap → fast lookup
✔ Linked list → order preservation

Order Types in LinkedHashMap

1️⃣ Insertion Order (Default)

LinkedHashMap<Integer, String> map = new LinkedHashMap<>();

map.put(1, "Java");
map.put(2, "Python");
map.put(3, "C++");
System.out.println(map);
          

Output:

{1=Java, 2=Python, 3=C++}
          

✔ Order of insertion preserved

2️⃣ Access Order (Very Important)

LinkedHashMap<Integer, String> map =
    new LinkedHashMap<>(16, 0.75f, true);

map.get(1);
          

✔ Recently accessed entries move to the end

✔ Used in LRU Cache

Commonly Used LinkedHashMap Methods

map.put(1, "Java");
map.get(1);
map.remove(2);
map.containsKey(1);
map.size();
          

✔ Same methods as HashMap

LRU Cache Using LinkedHashMap (Interview Favorite)

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
          

✔ Real-world use case

✔ Frequently asked in interviews

Null Handling

map.put(null, "Java");   // allowed
map.put(1, null);       // allowed
          

✔ Same behavior as HashMap

Performance Complexity

⚠ Slight overhead due to linked list maintenance

LinkedHashMap vs HashMap vs TreeMap

When to Use LinkedHashMap

• Order of insertion matters
• Predictable iteration required
• Implementing LRU cache
• Fast lookup with ordering

When NOT to Use LinkedHashMap

• Sorting is required (use TreeMap)
• Order does not matter (use HashMap)
• Memory usage must be minimal

Common Beginner Mistakes

• Assuming sorted order
• Ignoring access-order constructor
• Using LinkedHashMap unnecessarily
• Forgetting it is not thread-safe

Interview-Ready Answers

Short Answer

LinkedHashMap is a HashMap implementation that maintains insertion or access order.

Detailed Answer

In Java, LinkedHashMap extends HashMap and maintains a doubly linked list of entries, allowing predictable iteration order. It supports insertion-order and access-order modes and is commonly used to implement LRU caches while still providing constant-time performance.

Key Takeaway

LinkedHashMap = HashMap with order guarantee. Use it when you need fast lookups plus predictable iteration order.