LinkedHashMap in Java

A LinkedHashMap is a special version of HashMap that maintains insertion order or access order of elements.

It is part of the java.util package and is widely used when you need both:

• Fast performance (like HashMap)
• Predictable ordering (unlike HashMap)

What is LinkedHashMap in Java?

A LinkedHashMap is a combination of HashMap + Doubly LinkedList that:

• Stores key–value pairs
• Maintains insertion order by default
• Can maintain access order if enabled
• Allows one null key and multiple null values
• Provides O(1) average performance
• Is not thread-safe

Use case: If you need ordering + speed, LinkedHashMap is ideal.

Internal Structure of LinkedHashMap

LinkedHashMap = Hash Table (buckets) + Doubly LinkedList (ordering)

• Hash Table: For fast hashing
• Doubly Linked List: For maintaining order

LinkedHashMap Internal Diagram (Insertion Order)

Head → [A=10] ⇄ [B=20] ⇄ [C=30] → Tail

Hash Table Buckets:

0 → null
1 → [A=10]
2 → [B=20] → [E=50]
3 → [C=30]
4 → null

Each node contains:

[key | value | hash | next (bucket) | before | after]

before and after pointers maintain order.

Where LinkedHashMap Fits in Collection Hierarchy

Iterable
   └── Collection
          └── Map
                └── HashMap
                      └── LinkedHashMap

Implements:

• Map
• Cloneable
• Serializable

Underlying Data Structure:

• Hash Table
• Doubly Linked List

Key Features of LinkedHashMap

• Maintains insertion order
• Supports access order (LRU-like behavior)
• Faster than TreeMap
• Allows null keys/values
• Predictable iteration
• Ideal for cache implementations

When to Use LinkedHashMap

Creating a LinkedHashMap in Java

1. Default LinkedHashMap (Insertion Order)

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

2. With Initial Capacity

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

3. With Capacity + Load Factor

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

4. Maintain Access Order (for LRU (Least Recently Used) Cache)

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

Example: Insertion Order

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++}

Example: Access Order Enabled

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

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

map.get(1);  // Access element

System.out.println(map);

Output (recently accessed moves last):

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

Common LinkedHashMap Methods

1. Add / Update Methods

put(K key, V value) → Adds or updates a key-value pair.

map.put(101, "Java");
map.put(102, "Python");

putIfAbsent(K key, V value) → Adds only if key is not already present.

map.putIfAbsent(103, "C++");

putAll(Map m) → Adds all entries from another map.

map.putAll(otherMap);

2. Search / Check Methods

get(Object key) → Returns the value associated with the key.

map.get(101);

containsKey(Object key) → Checks if the map contains the specified key.

map.containsKey(102);

containsValue(Object value) → Checks if the map contains the specified value.

map.containsValue("Java");

getOrDefault(Object key, V defaultValue) → Returns value or default if key is missing.

map.getOrDefault(104, "Default");

3. Remove Methods

remove(Object key) → Removes the entry by key.

map.remove(102);

remove(Object key, Object value) → Removes entry only if key and value match.

map.remove(103, "C++");

clear() → Removes all entries from the map.

map.clear();

4. Replace / Update Methods

replace(K key, V value) → Updates value for a key.

map.replace(101, "JDK");

replace(K key, V oldValue, V newValue) → Replaces value only if old value matches.

map.replace(101, "Java", "JDK");

compute(K key, BiFunction) → Updates value using a function.

map.compute(101, (k, v) -> v + " Updated");

merge(K key, V value, BiFunction) → Merges value with a function.

map.merge(101, "NewValue", (oldV, newV) -> oldV + newV);

5. Iteration Methods

keySet() → Returns all keys.

for (var key : map.keySet()) {
    System.out.println(key);
}

values() → Returns all values.

for (var value : map.values()) {
    System.out.println(value);
}

entrySet() → Returns all key-value pairs for iteration.

for (var e : map.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

6. Utility Methods

size() → Returns the number of entries.

map.size();

isEmpty() → Checks if the map is empty.

map.isEmpty();

Time Complexity of LinkedHashMap

LinkedHashMap vs HashMap

LRU (Least Recently Used) Cache Using LinkedHashMap

protected boolean removeEldestEntry(Map.Entry e) {
    return size() > 5;
}

Advantages

• Maintains predictable order
• Fast operations (O(1))
• Supports access-order → useful for caches
• Allows null values and null key
• Uses less memory than TreeMap

Disadvantages

• More memory than HashMap (linked list pointers)
• Not thread-safe
• No sorting
• Slightly slower than HashMap

Real-World Use Cases

• LRU Cache
• Maintaining order of items
• Storing recent user activity
• Implementing history systems
• Building predictable APIs
• Resource tracking
• Session storage

Example Program

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

public class Main {
    public static void main(String[] args) {

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

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

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

Output:

1 = Java
2 = Python
3 = C++

Points to Remember

• HashMap is ideal when you only need speed and do not care about order.
• LinkedHashMap is ideal when you need predictable iteration, such as for caches or tracking recent access.
• LinkedHashMap uses slightly more memory than HashMap because of the linked list pointers used to maintain order.