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.

LinkedHashMap Examples

1. Creating a LinkedHashMap

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "Java");
        map.put(2, "API");
        System.out.println(map);
    }
}
          

Output

{1=Java, 2=API}
          

2. Maintains Insertion Order

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(3, "C");
        map.put(1, "A");
        map.put(2, "B");
        System.out.println(map);
    }
}
          

Output

{3=C, 1=A, 2=B}
          

3. Duplicate Key Overwrites Value (Order Preserved)

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "Java");
        map.put(1, "Selenium");
        System.out.println(map);
    }
}
          

Output

{1=Selenium}
          

4. Allows One null Key and Multiple null Values

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<String, String> map = new LinkedHashMap<>();
        map.put(null, "A");
        map.put("X", null);
        map.put("Y", null);
        System.out.println(map);
    }
}
          

Output

{null=A, X=null, Y=null}
          

5. Iterating Using entrySet()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "A");
        map.put(2, "B");

        for (Map.Entry<Integer, String> e : map.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }
    }
}
          

6. Iterating Using keySet()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(10, "X");
        map.put(20, "Y");

        for (Integer k : map.keySet()) {
            System.out.println(k);
        }
    }
}
          

7. Iterating Using values()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "Java");
        map.put(2, "API");

        for (String v : map.values()) {
            System.out.println(v);
        }
    }
}
          

8. Difference Between HashMap and LinkedHashMap

import java.util.*;

class Demo {
    public static void main(String[] args) {
        Map<Integer, String> h = new HashMap<>();
        h.put(2, "B");
        h.put(1, "A");

        Map<Integer, String> l = new LinkedHashMap<>();
        l.put(2, "B");
        l.put(1, "A");

        System.out.println(h);
        System.out.println(l);
    }
}
          

Output

{1=A, 2=B}
{2=B, 1=A}
          

9. Access-Order LinkedHashMap

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map =
            new LinkedHashMap<>(16, 0.75f, true);

        map.put(1, "A");
        map.put(2, "B");
        map.put(3, "C");

        map.get(1);
        map.get(2);

        System.out.println(map);
    }
}
          

Output

{3=C, 1=A, 2=B}
          

Explanation

Order changes based on access.

10. LinkedHashMap as LRU Cache (Very Important)

import java.util.*;

class LRUCache extends LinkedHashMap<Integer, String> {
    private final int capacity;

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

    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.get(1);
        cache.put(3, "C");
        System.out.println(cache);
    }
}
          

Output

{1=A, 3=C}
          

11. putIfAbsent() with LinkedHashMap

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "Java");
        map.putIfAbsent(1, "API");
        map.putIfAbsent(2, "API");
        System.out.println(map);
    }
}
          

Output

{1=Java, 2=API}
          

12. replace() Method

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "Java");
        map.replace(1, "Selenium");
        System.out.println(map);
    }
}
          

13. Conditional remove()

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "Java");
        map.remove(1, "API");   // no effect
        map.remove(1, "Java");  // removed
        System.out.println(map);
    }
}
          

14. Custom Object as Key (equals & hashCode Required)

class User {
    int id;
    User(int id) { this.id = id; }

    public boolean equals(Object o) {
        return this.id == ((User)o).id;
    }

    public int hashCode() {
        return id;
    }
}

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<User, String> map = new LinkedHashMap<>();
        map.put(new User(1), "Admin");
        map.put(new User(1), "Admin");
        System.out.println(map.size());
    }
}
          

Output

1
          

15. LinkedHashMap Is Not Thread-Safe

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<String, String> map = new LinkedHashMap<>();
        map.put("A", "Not Thread Safe");
        System.out.println(map);
    }
}
          

16. Thread-Safe LinkedHashMap

import java.util.*;

class Demo {
    public static void main(String[] args) {
        Map<String, String> map =
            Collections.synchronizedMap(new LinkedHashMap<>());
        map.put("A", "Safe");
        System.out.println(map);
    }
}
          

17. Converting HashMap to LinkedHashMap

import java.util.*;

class Demo {
    public static void main(String[] args) {
        Map<Integer, String> hashMap = new HashMap<>();
        hashMap.put(2, "B");
        hashMap.put(1, "A");

        LinkedHashMap<Integer, String> linked =
            new LinkedHashMap<>(hashMap);

        System.out.println(linked);
    }
}
          

18. LinkedHashMap Size & Empty Check

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        System.out.println(map.isEmpty());
        map.put(1, "Java");
        System.out.println(map.size());
    }
}
          

Output

true
1
          

19. Performance Note (Concept)

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

Explanation

• Slightly slower than HashMap
• Extra memory for doubly-linked list
• Predictable iteration order

20. Interview Summary – LinkedHashMap

import java.util.*;

class Demo {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "Ordered");
        map.put(2, "KeyValue");
        System.out.println(map);
    }
}
          

Key Points

• Maintains insertion or access order
• Allows one null key
• Backed by HashMap + Linked List
• Used for LRU cache
• Not thread-safe by default