LinkedHashMap in Java — Complete Guide with Real-World Applications

By Sumit Kumar
Java Backend Engineer | Agentic AI Developer

🔗 GitHub | 🌐 Portfolio

This article is a complete, production-focused guide to LinkedHashMap in Java — from internals to real-world applications I've encountered building telecom network management systems and AI pipelines. Whether you're preparing for interviews or designing production systems, this covers everything.

---

Table of Contents

1. What is LinkedHashMap?
2. Internal Structure — How it actually works
3. Constructors
4. Insertion Order vs Access Order
5. All Methods with Examples
6. removeEldestEntry — The Secret Weapon
7. LRU Cache — Full Implementation
8. Real-World Applications with Code
9. Performance Analysis
10. LinkedHashMap vs HashMap vs TreeMap
11. Common Interview Problems
12. When to Use LinkedHashMap
13. Summary

---

1. What is LinkedHashMap?

LinkedHashMap is a Map implementation that combines the O(1) lookup speed of HashMap with a doubly linked list that preserves entry order.

It extends HashMap and implements the Map interface:

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

It was introduced in Java 1.4 and lives in java.util.

The two things that make it unique:

• Maintains insertion order by default
• Can be switched to access order mode — the foundation of LRU caches

---

2. Internal Structure — How It Actually Works

HashMap stores entries in a bucket array using hash codes. LinkedHashMap adds a doubly linked list woven through all entries:

Bucket Array         Doubly Linked List
[ bucket 0 ] ──────► [Entry A] ↔ [Entry B] ↔ [Entry C] ↔ [Entry D]
[ bucket 1 ]           head                                  tail
[ bucket 2 ]

Each node extends HashMap.Node with two extra pointers:

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before;   // previous node in linked list
    Entry<K,V> after;    // next node in linked list
}

So every entry simultaneously lives in:

1. The hash bucket array → for O(1) get/put
2. The doubly linked list → for ordered iteration

This is why iteration over LinkedHashMap is actually faster than HashMap — it walks the linked list directly instead of scanning all bucket slots including empty ones.

---

3. Constructors

// 1. Default — insertion order, capacity 16, load factor 0.75
LinkedHashMap<K, V> map = new LinkedHashMap<>();

// 2. Custom initial capacity
LinkedHashMap<K, V> map = new LinkedHashMap<>(32);

// 3. Custom capacity + load factor
LinkedHashMap<K, V> map = new LinkedHashMap<>(32, 0.75f);

// 4. Copy constructor
LinkedHashMap<K, V> map = new LinkedHashMap<>(existingMap);

// 5. ACCESS ORDER mode — the key to LRU cache
LinkedHashMap<K, V> map = new LinkedHashMap<>(16, 0.75f, true);
//                                                         ^^^^
//                                               true  = access order
//                                               false = insertion order (default)

Load factor controls when rehashing triggers. At 0.75, the map rehashes when 75% full — a good balance between memory and performance.

---

4. Insertion Order vs Access Order

Insertion Order (default)

Entries are iterated in the order they were inserted. put() appends to the tail. Re-inserting an existing key does NOT change its position.

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("Banana", 3);
map.put("Apple", 1);
map.put("Mango", 2);

// Re-insert existing key — position doesn't change
map.put("Banana", 99);

map.forEach((k, v) -> System.out.println(k + " = " + v));
// Output:
// Banana = 99   ← still first (original insertion position)
// Apple = 1
// Mango = 2

Access Order (accessOrder = true)

Every get(), put(), or getOrDefault() call moves the accessed entry to the tail of the list. The head always holds the least recently used entry.

LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

// Access A — moves to tail
map.get("A");

map.forEach((k, v) -> System.out.print(k + " "));
// Output: B C A
//         ^     ^ most recently accessed = last (tail)
//   least recently used = first (head)

This access-order behavior is exactly what powers LRU (Least Recently Used) cache eviction.

---

5. All Methods with Examples

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

// ── BASIC CRUD ──────────────────────────────────────────

map.put("key", 1);               // insert or update
map.get("key");                  // returns 1, null if absent
map.remove("key");               // removes and returns value
map.containsKey("key");          // O(1) key check
map.containsValue(1);            // O(n) value scan
map.size();                      // number of entries
map.isEmpty();                   // true if size == 0
map.clear();                     // removes all entries

// ── NULL SUPPORT ─────────────────────────────────────────

map.put(null, 99);               // ONE null key allowed
map.put("nullval", null);        // null values allowed

// ── SAFE RETRIEVAL ───────────────────────────────────────

map.getOrDefault("missing", 0);  // returns 0 if key absent

// ── CONDITIONAL PUTS ─────────────────────────────────────

map.putIfAbsent("key", 5);       // only inserts if key not present
map.putAll(otherMap);            // bulk insert

// ── COMPUTE OPERATIONS ───────────────────────────────────

// Increment counter (handles null on first call)
map.compute("key", (k, v) -> v == null ? 1 : v + 1);

// Only compute if key is absent
map.computeIfAbsent("key", k -> k.length());

// Only compute if key is present
map.computeIfPresent("key", (k, v) -> v * 2);

// Merge — perfect for frequency counting
map.merge("key", 1, Integer::sum);
// If "key" absent → puts 1
// If "key" present → applies Integer::sum to old + new value

// ── REPLACE OPERATIONS ───────────────────────────────────

map.replace("key", 10);                  // replace if key exists
map.replace("key", 10, 20);             // replace only if current value = 10
map.replaceAll((k, v) -> v * 2);        // apply function to all values

// ── ITERATION ────────────────────────────────────────────

// EntrySet — most efficient for key+value access
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " → " + entry.getValue());
}

// forEach lambda
map.forEach((k, v) -> System.out.println(k + " → " + v));

// KeySet only
for (String key : map.keySet()) {
    System.out.println(key);
}

// Values only
for (int val : map.values()) {
    System.out.println(val);
}

// Iterator with safe removal
Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, Integer> e = it.next();
    if (e.getValue() < 0) it.remove();  // safe removal during iteration
}

---

6. removeEldestEntry — The Secret Weapon

This protected method is called internally after every put(). By default it returns false (never remove). Override it to implement automatic eviction:

LinkedHashMap<Integer, String> bounded = new LinkedHashMap<>(16, 0.75f, true) {
    private static final int MAX_SIZE = 100;

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        // eldest = head of linked list = least recently used
        return size() > MAX_SIZE;
    }
};

When removeEldestEntry returns true, the map automatically removes the head entry (least recently used in access-order mode, or oldest inserted entry in insertion-order mode).

This single override turns LinkedHashMap into a bounded, self-evicting cache without any extra code.

---

7. LRU Cache — Full Implementation

The classic interview problem, production-ready:

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

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // access order = true → get() moves entry to tail
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
                // When over capacity, remove head (least recently used)
            }
        };
    }

    public int get(int key) {
        // getOrDefault also triggers access-order update
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
        // If over capacity, removeEldestEntry fires automatically
    }

    public void printCache() {
        System.out.println("Cache (LRU → MRU): " + cache.keySet());
    }
}

// Usage
LRUCache lru = new LRUCache(3);
lru.put(1, 10);   // Cache: [1]
lru.put(2, 20);   // Cache: [1, 2]
lru.put(3, 30);   // Cache: [1, 2, 3]
lru.get(1);       // Access 1 → Cache: [2, 3, 1]
lru.put(4, 40);   // Over capacity → evict head (2) → Cache: [3, 1, 4]
lru.printCache(); // [3, 1, 4]
System.out.println(lru.get(2)); // -1 (evicted)
System.out.println(lru.get(3)); // 30

Time complexity: O(1) for both get() and put() — exactly what LeetCode problem #146 requires.

---

8. Real-World Applications with Code

8.1 Browser History

class BrowserHistory {
    private final LinkedHashMap<String, Long> history;
    private final int maxSize;

    public BrowserHistory(int maxSize) {
        this.maxSize = maxSize;
        this.history = new LinkedHashMap<>(16, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<String, Long> eldest) {
                return size() > maxSize;
            }
        };
    }

    public void visit(String url) {
        history.put(url, System.currentTimeMillis());
        System.out.println("Visited: " + url);
    }

    public void printHistory() {
        System.out.println("\n── Browser History (oldest → newest) ──");
        history.forEach((url, time) ->
            System.out.println("  " + url + " @ " + time));
    }
}

// Usage
BrowserHistory browser = new BrowserHistory(3);
browser.visit("google.com");
browser.visit("github.com");
browser.visit("stackoverflow.com");
browser.visit("leetcode.com");  // evicts google.com
browser.printHistory();
// github.com
// stackoverflow.com
// leetcode.com

---

8.2 API Rate Limiter

class RateLimiter {
    // userId → timestamps of recent requests
    private final LinkedHashMap<String, LinkedList<Long>> userRequests
        = new LinkedHashMap<>();
    private final int maxRequests;
    private final long windowMs;

    public RateLimiter(int maxRequests, long windowMs) {
        this.maxRequests = maxRequests;
        this.windowMs = windowMs;
    }

    public boolean isAllowed(String userId) {
        long now = System.currentTimeMillis();
        userRequests.putIfAbsent(userId, new LinkedList<>());
        LinkedList<Long> timestamps = userRequests.get(userId);

        // Evict expired timestamps outside the window
        while (!timestamps.isEmpty() && now - timestamps.peek() > windowMs)
            timestamps.poll();

        if (timestamps.size() < maxRequests) {
            timestamps.add(now);
            return true;
        }
        return false; // rate limit exceeded
    }
}

// Usage — 5 requests per 10 seconds
RateLimiter limiter = new RateLimiter(5, 10_000);
for (int i = 1; i <= 6; i++) {
    System.out.println("Request " + i + ": " + limiter.isAllowed("user_sumit"));
}
// Request 1: true
// Request 2: true
// Request 3: true
// Request 4: true
// Request 5: true
// Request 6: false ← rate limit hit

---

8.3 Database Query Cache

A pattern I use in backend services to avoid repeated expensive DB calls:

class QueryCache {
    private final LinkedHashMap<String, Object> cache;

    public QueryCache(int capacity) {
        this.cache = new LinkedHashMap<>(16, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) {
                return size() > capacity;
            }
        };
    }

    public Object get(String sql) {
        return cache.getOrDefault(sql, null);
    }

    public void put(String sql, Object result) {
        cache.put(sql, result);
    }
}

// Usage in a Spring Boot service
@Service
public class NetworkEventService {
    private final QueryCache queryCache = new QueryCache(100);

    public List<NetworkEvent> getCriticalEvents() {
        String sql = "SELECT * FROM network_events WHERE status='CRITICAL'";
        List<NetworkEvent> cached = (List<NetworkEvent>) queryCache.get(sql);
        if (cached != null) {
            System.out.println("Cache hit");
            return cached;
        }
        List<NetworkEvent> result = networkEventRepository.findCritical();
        queryCache.put(sql, result);
        System.out.println("DB hit — cached for next call");
        return result;
    }
}

---

8.4 Kafka Consumer Offset Tracker

Directly relevant to event-driven systems using Apache Kafka:

class KafkaOffsetTracker {
    // partition → last committed offset (insertion order = partition order)
    private final LinkedHashMap<Integer, Long> offsets = new LinkedHashMap<>();

    public void commit(int partition, long offset) {
        offsets.put(partition, offset);
        System.out.println("Committed → partition=" + partition + " offset=" + offset);
    }

    public long getLastOffset(int partition) {
        return offsets.getOrDefault(partition, -1L);
    }

    public void replayFrom(int partition) {
        long lastOffset = getLastOffset(partition);
        System.out.println("Replaying partition " + partition + " from offset " + lastOffset);
    }

    public void printAll() {
        System.out.println("\n── Partition Offsets ──");
        offsets.forEach((p, o) -> System.out.println("  Partition " + p + " → offset " + o));
    }
}

// Usage
KafkaOffsetTracker tracker = new KafkaOffsetTracker();
tracker.commit(0, 1001);
tracker.commit(1, 2045);
tracker.commit(2, 3087);
tracker.commit(0, 1002);  // update partition 0
tracker.printAll();
// Partition 0 → 1002
// Partition 1 → 2045
// Partition 2 → 3087

---

8.5 HTTP API Response Builder

Preserving JSON key order matters for API consumers and debugging:

class ApiResponseBuilder {
    private final LinkedHashMap<String, Object> body = new LinkedHashMap<>();

    public ApiResponseBuilder status(int code) {
        body.put("status", code);
        return this;
    }

    public ApiResponseBuilder message(String msg) {
        body.put("message", msg);
        return this;
    }

    public ApiResponseBuilder data(Object data) {
        body.put("data", data);
        return this;
    }

    public ApiResponseBuilder timestamp() {
        body.put("timestamp", System.currentTimeMillis());
        return this;
    }

    public Map<String, Object> build() {
        return Collections.unmodifiableMap(body);
    }
}

// Usage in Spring Boot controller
@GetMapping("/events")
public ResponseEntity<Map<String, Object>> getEvents() {
    Map<String, Object> response = new ApiResponseBuilder()
        .status(200)
        .message("Network events fetched successfully")
        .data(eventService.getAll())
        .timestamp()
        .build();
    return ResponseEntity.ok(response);
}
// JSON output always in this order:
// { "status": 200, "message": "...", "data": [...], "timestamp": 1234567890 }

---

8.6 Network Alarm Deduplicator (Telecom Domain)

A real pattern from telecom NMS (Network Management System) development — suppress duplicate alarms while preserving arrival order for audit:

class AlarmDeduplicator {
    // alarmId → alarm details — insertion order = arrival order
    private final LinkedHashMap<String, String> activeAlarms = new LinkedHashMap<>();

    public void receive(String alarmId, String description) {
        if (!activeAlarms.containsKey(alarmId)) {
            activeAlarms.put(alarmId, description);
            System.out.println("[NEW]       " + alarmId + ": " + description);
        } else {
            System.out.println("[SUPPRESSED] Duplicate: " + alarmId);
        }
    }

    public void clear(String alarmId) {
        if (activeAlarms.remove(alarmId) != null) {
            System.out.println("[CLEARED]   " + alarmId);
        }
    }

    public void printInArrivalOrder() {
        System.out.println("\n── Active Alarms (arrival order) ──");
        activeAlarms.forEach((id, desc) ->
            System.out.println("  " + id + ": " + desc));
    }
}

// Usage
AlarmDeduplicator dedup = new AlarmDeduplicator();
dedup.receive("ALM001", "Link down on port GE0/1");
dedup.receive("ALM002", "CPU spike on Node-A");
dedup.receive("ALM001", "Link down on port GE0/1");  // suppressed
dedup.receive("ALM003", "Memory threshold exceeded");
dedup.printInArrivalOrder();
// ALM001: Link down on port GE0/1
// ALM002: CPU spike on Node-A
// ALM003: Memory threshold exceeded

---

8.7 Session Manager

class SessionManager {
    private final int maxSessions;
    private final LinkedHashMap<String, String> sessions;

    public SessionManager(int maxSessions) {
        this.maxSessions = maxSessions;
        this.sessions = new LinkedHashMap<>(16, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                if (size() > maxSessions) {
                    System.out.println("[EVICTED] Session: " + eldest.getKey());
                    return true;
                }
                return false;
            }
        };
    }

    public void createSession(String sessionId, String userId) {
        sessions.put(sessionId, userId);
        System.out.println("[CREATED] Session " + sessionId + " for user " + userId);
    }

    public String getSession(String sessionId) {
        // access-order: moves this session to tail (marks as recently used)
        return sessions.getOrDefault(sessionId, null);
    }

    public void invalidate(String sessionId) {
        sessions.remove(sessionId);
        System.out.println("[INVALIDATED] Session " + sessionId);
    }
}

// Usage
SessionManager sm = new SessionManager(3);
sm.createSession("sess_001", "sumit");
sm.createSession("sess_002", "alice");
sm.createSession("sess_003", "bob");
sm.getSession("sess_001");         // sess_001 moves to tail (recently used)
sm.createSession("sess_004", "charlie"); // evicts sess_002 (LRU)

---

9. Performance Analysis

Operation	Time Complexity	Notes
put()	O(1) average	Same as HashMap + linked list append
get()	O(1) average	Hash lookup + optional list reorder
remove()	O(1) average	Hash removal + linked list pointer update
containsKey()	O(1) average	Pure hash lookup
containsValue()	O(n)	Must scan all values
Iteration	O(n)	Faster than HashMap — walks linked list

Memory overhead: Each entry stores 2 extra object references (before, after) — roughly 16 extra bytes per entry on a 64-bit JVM. Acceptable for most use cases.

When iteration matters: LinkedHashMap iteration is faster than HashMap in practice because it walks only n nodes in the linked list, while HashMap scans the entire bucket array (capacity = 16, 32, 64... often much larger than n).

---

10. LinkedHashMap vs HashMap vs TreeMap

Feature	HashMap	LinkedHashMap	TreeMap
Order	None	Insertion or Access	Sorted by key
Null key	1 allowed	1 allowed	Not allowed
Null values	Allowed	Allowed	Allowed
Thread-safe	No	No	No
get/put	O(1)	O(1)	O(log n)
Iteration order	Unpredictable	Predictable	Ascending
Memory	Baseline	+2 pointers/entry	Tree node overhead
Best for	Fast lookup, no order needed	Order + speed + LRU	Range queries, sorted keys
Extra API	—	removeEldestEntry	floorKey, ceilingKey, subMap, headMap, tailMap

---

11. Common Interview Problems

Problem 1: First Non-Repeating Character

public char firstNonRepeating(String s) {
    LinkedHashMap<Character, Integer> freq = new LinkedHashMap<>();

    // Count frequencies (insertion order preserved)
    for (char c : s.toCharArray())
        freq.merge(c, 1, Integer::sum);

    // First entry with count 1 = first non-repeating
    for (Map.Entry<Character, Integer> e : freq.entrySet())
        if (e.getValue() == 1) return e.getKey();

    return '#';
}

// Test
System.out.println(firstNonRepeating("aabcbc")); // 'a' → wrong
System.out.println(firstNonRepeating("aabbcc")); // '#'
System.out.println(firstNonRepeating("sumit"));  // 's'

Problem 2: Group Anagrams (preserve input order)

public List<List<String>> groupAnagrams(String[] strs) {
    LinkedHashMap<String, List<String>> map = new LinkedHashMap<>();

    for (String s : strs) {
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        String key = new String(ch);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }

    return new ArrayList<>(map.values());
}

// Test
System.out.println(groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"}));
// [[eat, tea, ate], [tan, nat], [bat]]

Problem 3: Top K Frequent Elements

public int[] topKFrequent(int[] nums, int k) {
    LinkedHashMap<Integer, Integer> freq = new LinkedHashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);

    return freq.entrySet().stream()
        .sorted((a, b) -> b.getValue() - a.getValue())
        .limit(k)
        .mapToInt(Map.Entry::getKey)
        .toArray();
}

Problem 4: LRU Cache (LeetCode #146)

// Already covered in Section 7 — O(1) get and put using
// LinkedHashMap with accessOrder=true + removeEldestEntry override

---

12. When to Use LinkedHashMap

Use LinkedHashMap when:

• You need HashMap speed (O(1) operations)
• You also need predictable iteration order
• You're building a cache with eviction (LRU/MRU)
• You're deduplicating while preserving arrival order
• You're building ordered API responses (JSON key order)
• You're tracking Kafka offsets per partition in order
• You're processing network alarms with deduplication
• You want frequency maps where output order matters

Do NOT use when:

• You need sorted keys → use TreeMap
• You need thread safety → use ConcurrentHashMap
• You have no ordering requirement → use HashMap (less memory)
• Keys must be navigated by range → use TreeMap

---

13. Summary

LinkedHashMap is one of the most underrated data structures in Java. Most developers only know it as "HashMap with order" — but it's actually a production-ready tool for:

• LRU/MRU caches with zero extra code
• Bounded maps via removeEldestEntry
• Ordered deduplication in event-driven systems
• Predictable API responses in REST services

The key insight: it gives you HashMap performance with linked list ordering — and the removeEldestEntry hook makes it a self-managing cache with a single method override.

---

Written by **Sumit Kumar* — Java Backend Engineer & Agentic AI Developer with 3+ years building production systems in Spring Boot, Apache Kafka*

🔗 GitHub: github.com/SumitK25
🌐 Portfolio: sumitkumardev.netlify.app

---