LinkedHashMap

📋 Quick Reference

Property	Value
Type	HashMap + doubly-linked list for ordering
Get/Put	O(1) average
Ordering	Insertion order (or access order)
Memory	O(n) + linked list overhead
Null	One null key, multiple null values
Best For	Ordered maps, LRU cache, predictable iteration

One-liner: HashMap with predictable iteration order - insertion order by default, or access order for LRU cache.

🎮 Interactive Visualizer

Watch how LinkedHashMap maintains order while providing O(1) operations:

LinkedHashMap
O(1) opsOrdered
1 / 18
Initialize LinkedHashMap with 6 buckets. Mode: Access-order (LRU)
Use cases:LRU cache, ordered iteration, insertion-order maps
vs HashMap:Same O(1) ops, predictable iteration, ~20% more memory
🔗 LinkedHashMap = HashMap + LinkedList
🗂️ Hash Table
O(1) get/put • Same as HashMap
🔗 Doubly Linked List
Access order (LRU cache) • O(1) reorder
Access operations will show LRU updates here
Hash Table (6 buckets)
0
∅
1
∅
2
∅
3
∅
4
∅
5
∅
🔗 Access Order (LRU: oldest → newest)
HEAD → TAIL (empty)
LRU Cache Usage:Cache empty
Pseudocode
1class LinkedHashMap<K,V> extends HashMap {
2  Entry<K,V> head, tail;
3  boolean accessOrder; // false=insertion
4 
5  V put(K key, V value) {
6    Entry e = super.put(key, value);
7    if (e.isNew()) {
8      linkNodeLast(e); // Add to list end
9    } else if (accessOrder) {
10      moveToLast(e);
11    }
12    return e.value;
13  }
14 
15  V get(K key) {
16    Entry e = super.get(key);
17    if (e != null && accessOrder) {
18      moveToLast(e); // LRU: move to end
19    }
20    return e != null ? e.value : null;
21  }
22}
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Current bucket
Current bucket
Insert/Update
Insert/Update
Found
Found
Linked list order
Linked list order
P · [ ] · R
Loading visualizer...

Try these operations:

Put entries - see both hash bucket and linked list
Iterate - entries come out in insertion order
Remove and re-add - position changes
Enable access order - see LRU behavior

🔧 Key Operations

Creating

JAVA(12 lines)
Code
Loading syntax highlighter...

Adding/Updating

JAVA(7 lines)
Code
Loading syntax highlighter...

Retrieving

JAVA(4 lines)
Code
Loading syntax highlighter...

Removing

JAVA(3 lines)
Code
Loading syntax highlighter...

Iteration (Ordered!)

JAVA(13 lines)
Code
Loading syntax highlighter...

📊 Complexity Analysis

Operation	Time	Notes
`get(key)`	O(1)	May reorder if access order
`put(key, val)`	O(1)	Updates linked list
`remove(key)`	O(1)	Updates linked list
`containsKey`	O(1)	Hash lookup
`containsValue`	O(n)	Scans all values
`iteration`	O(n)	Follows linked list

Internal Structure

Hash Buckets:          Doubly-Linked List:
[0] → null             head ← → A ← → B ← → C ← → tail
[1] → B                         ↑           ↑
[2] → A → C                   first       last inserted
[3] → null

Each entry has: hash, key, value, next (bucket), before, after (linked list)

✅ When to Use LinkedHashMap

Good Use Cases

Predictable iteration - need consistent order
LRU cache - access-order mode with removeEldestEntry
JSON serialization - preserve field order
Duplicate-preserving - remember first occurrence position
Copy with order - when HashMap order is chaotic

Avoid When

Order doesn't matter - use HashMap (less overhead)
Need sorted order - use TreeMap
Memory constrained - extra pointers per entry
Thread safety needed - no concurrent version exists

🧩 LRU Cache Implementation

JAVA(23 lines)
Code
Loading syntax highlighter...

Manual LRU with Access Order

JAVA(6 lines)
Code
Loading syntax highlighter...

🔄 LinkedHashMap vs HashMap vs TreeMap

Feature	HashMap	LinkedHashMap	TreeMap
Order	None	Insertion/Access	Sorted
Get/Put	O(1)	O(1)	O(log n)
Memory	Lowest	Medium	Higher
Use Case	General	Ordered/LRU	Sorted keys

JAVA(4 lines)
Code
Loading syntax highlighter...

⚠️ Common Pitfalls

1. Forgetting Access Order Moves Elements

JAVA(12 lines)
Code
Loading syntax highlighter...

2. Assuming Order After HashMap Conversion

JAVA(7 lines)
Code
Loading syntax highlighter...

3. Not Using for Predictable Tests

JAVA(6 lines)
Code
Loading syntax highlighter...

4. Missing LRU Behavior Configuration

JAVA(6 lines)
Code
Loading syntax highlighter...

🎤 Interview Tips

Q: How does LinkedHashMap maintain order?

"

It extends HashMap and adds a doubly-linked list through all entries. Each entry has before/after pointers in addition to the hash bucket chain. Iteration follows the linked list, not the buckets.

Q: How would you implement an LRU cache?

"

Use LinkedHashMap with access-order=true and override removeEldestEntry() to return true when size exceeds capacity. Gets and puts move entries to the tail; eviction removes from head.

Q: LinkedHashMap vs TreeMap for ordered iteration?

"

LinkedHashMap maintains insertion (or access) order with O(1) operations. TreeMap maintains sorted order with O(log n) operations. Choose based on whether you need "order added" or "sorted by key".

Q: What's the memory overhead of LinkedHashMap?

"

Each entry has two extra references (before/after) for the linked list, plus the head/tail references. This is typically 16-24 bytes per entry overhead compared to HashMap.

Previous: Part 6: ArrayDeque

Next: Part 8: EnumSet

Visualizer: LinkedHashMap from @tomaszjarosz/react-visualizers

📋 Quick Reference

🎮 Interactive Visualizer

LinkedHashMap

🔧 Key Operations

Creating

Adding/Updating

Retrieving

Removing

Iteration (Ordered!)

📊 Complexity Analysis

Internal Structure

✅ When to Use LinkedHashMap

Good Use Cases

Avoid When

🧩 LRU Cache Implementation

Manual LRU with Access Order

🔄 LinkedHashMap vs HashMap vs TreeMap

⚠️ Common Pitfalls

1. Forgetting Access Order Moves Elements

2. Assuming Order After HashMap Conversion

3. Not Using for Predictable Tests

4. Missing LRU Behavior Configuration

🎤 Interview Tips

📚 Series Navigation

Tags:

LinkedHashMap