LinkedHashMap in Java – Complete Guide with Examples

LinkedHashMap is a HashMap that remembers order. By default it returns entries in the order they were inserted; optionally it can order them by most recent access, which makes it the classic building block for an LRU cache.

It lives in java.util, extends HashMap, and has been available since JDK 1.4. You get HashMap's O(1) speed plus predictable iteration, at the cost of a little extra memory.

1. What Is a LinkedHashMap?

Think of a restaurant waiting list: each party's name (key) is linked to the party size (value), and the list keeps the order in which people arrived. A LinkedHashMap is a fast lookup table that also keeps such a list.

• All HashMap features: unique keys, O(1) operations, one null key and null values.
• Insertion order by default; updating an existing key does not move it.
• Access order on request: every read or write moves the entry to the end.
• removeEldestEntry() hook to evict old entries automatically.
• A SequencedMap since Java 21, with firstEntry(), lastEntry(), putFirst() and reversed().
• Not synchronized.

2. Class Hierarchy and Declaration

public class LinkedHashMap<K, V> extends HashMap<K, V>
        implements SequencedMap<K, V>   // Java 21+ (Map before)

3. Insertion Order in Action

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

public class LinkedHashMapQuickStart {
    public static void main(String[] args) {
        String[] steps = {"wake", "exercise", "breakfast", "commute", "work"};

        Map<String, Integer> hash = new HashMap<>();
        Map<String, Integer> linked = new LinkedHashMap<>();
        for (int i = 0; i < steps.length; i++) {
            hash.put(steps[i], i + 1);
            linked.put(steps[i], i + 1);
        }
        System.out.println("HashMap:       " + hash);
        System.out.println("LinkedHashMap: " + linked);

        linked.put("wake", 0);               // updating a key keeps its position
        System.out.println("After update:  " + linked);
    }
}

HashMap:       {wake=1, work=5, exercise=2, breakfast=3, commute=4}
LinkedHashMap: {wake=1, exercise=2, breakfast=3, commute=4, work=5}
After update:  {wake=0, exercise=2, breakfast=3, commute=4, work=5}

The HashMap scrambles the morning routine; the LinkedHashMap keeps it in order. Updating "wake" changed its value but not its position.

4. Constructors

Java 19 added LinkedHashMap.newLinkedHashMap(int numMappings) for pre-sizing.

5. Access Order

With accessOrder = true, every get(), put() (and getOrDefault(), compute(), merge() …) on a key moves that entry to the end. The first entry is then always the least recently used one.

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

public class AccessOrderDemo {
    public static void main(String[] args) {
        // third argument true = access order (least recently used first)
        Map<String, String> pages = new LinkedHashMap<>(16, 0.75f, true);
        pages.put("home", "...");
        pages.put("about", "...");
        pages.put("blog", "...");
        System.out.println("Start:            " + pages.keySet());

        pages.get("home");                   // reading moves "home" to the end
        System.out.println("After get(home):  " + pages.keySet());

        pages.put("about", "updated");       // writing also counts as access
        System.out.println("After put(about): " + pages.keySet());
    }
}

Start:            [home, about, blog]
After get(home):  [about, blog, home]
After put(about): [blog, home, about]

6. Building an LRU Cache

An LRU (Least Recently Used) cache keeps a fixed number of entries and throws away the one that has not been used for the longest time. LinkedHashMap does almost all the work: use access order and override removeEldestEntry(), which is called after every insert.

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

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

    public LruCache(int capacity) {
        super(16, 0.75f, true);              // access order
        this.capacity = capacity;
    }

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

    public static void main(String[] args) {
        LruCache<Integer, String> cache = new LruCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        cache.get(1);                        // 1 is now most recently used
        cache.put(4, "four");                // evicts 2, the least recently used
        System.out.println("Cache: " + cache.keySet());
        System.out.println("Contains 2? " + cache.containsKey(2));
    }
}

Cache: [3, 1, 4]
Contains 2? false

Key 2 was evicted because key 1 had been read more recently. For production caches with expiry, statistics or concurrency, a library such as Caffeine is a better choice; this pattern is perfect for small, single-threaded caches and for interviews.

7. How LinkedHashMap Works Internally

LinkedHashMap reuses all of HashMap's hashing logic. Its entries are a subclass of HashMap's nodes with two extra links, before and after, which form a doubly linked list through all entries. The map also keeps head and tail references.

• put (new key): HashMap stores the node in its bucket, and the node is linked at the tail.
• remove: the node is removed from its bucket and unlinked from the list.
• access (access-order mode): the node is moved to the tail.
• iteration: walks the list from head to tail, so it is O(n) regardless of capacity.
• after insert: removeEldestEntry(head) is called; if it returns true, the head is removed.

8. Java 21: SequencedMap Methods

Since Java 21, LinkedHashMap implements SequencedMap, giving direct access to both ends:

import java.util.LinkedHashMap;

public class SequencedMapDemo {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> queue = new LinkedHashMap<>();
        queue.put("Asha", 1);
        queue.put("Ravi", 2);
        queue.put("Meera", 3);

        // Java 21 SequencedMap methods
        System.out.println("firstEntry(): " + queue.firstEntry());
        System.out.println("lastEntry():  " + queue.lastEntry());

        queue.putFirst("VIP", 0);            // insert at the front
        System.out.println("After putFirst: " + queue);

        System.out.println("pollFirstEntry(): " + queue.pollFirstEntry() + " -> " + queue);
        System.out.println("reversed():       " + queue.reversed());
    }
}

firstEntry(): Asha=1
lastEntry():  Meera=3
After putFirst: {VIP=0, Asha=1, Ravi=2, Meera=3}
pollFirstEntry(): VIP=0 -> {Asha=1, Ravi=2, Meera=3}
reversed():       {Meera=3, Ravi=2, Asha=1}

putFirst() and putLast() also move an existing key to that end. sequencedKeySet(), sequencedValues() and sequencedEntrySet() return ordered views.

9. Practical Example: Keeping a Sorted Result

When you sort map entries with a stream, collect them into a LinkedHashMap; a plain HashMap would lose the order immediately.

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;

public class SortByValue {
    public static void main(String[] args) {
        Map<String, Integer> runs = Map.of("Rohit", 45, "Virat", 82, "Gill", 17, "Rahul", 60);

        Map<String, Integer> ranked = runs.entrySet().stream()
                .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
                        (a, b) -> a, LinkedHashMap::new));   // LinkedHashMap keeps the sort

        System.out.println("Top scorers: " + ranked);
    }
}

Top scorers: {Virat=82, Rahul=60, Rohit=45, Gill=17}

10. Common Methods

11. HashMap vs LinkedHashMap vs TreeMap

12. When to Use LinkedHashMap

• The order of entries is visible to users, logs, JSON output or tests.
• You build a simple LRU or FIFO cache.
• You need to keep the result of a sort or a grouping in order.
• You want repeatable iteration order without paying for sorting.

13. Thread Safety

LinkedHashMap is not synchronized. Wrap it with Collections.synchronizedMap(new LinkedHashMap<>(...)) and synchronize on the wrapper while iterating. There is no concurrent LinkedHashMap in the JDK; for concurrent caches, use a dedicated library.

14. Summary

• LinkedHashMap is a HashMap with a doubly linked list through its entries.
• It keeps insertion order by default, or access order with accessOrder = true.
• Overriding removeEldestEntry() turns it into an LRU or FIFO cache.
• Operations are O(1); iteration is O(n) and predictable.
• Java 21 added first/last entry, putFirst/putLast and reversed().

Related Tutorials

• HashMap in Java
• TreeMap in Java
• LinkedHashSet in Java
• Difference between HashMap and LinkedHashMap

Reference: Java SE 21 API: java.util.LinkedHashMap

Frequently Asked Questions (FAQ)