LinkedHashMap is a HashMap that remembers the order in which entries were added. It provides the same average O(1) get and put as HashMap, while iteration walks the entries in a predictable order rather than the scrambled bucket order a plain HashMap produces. It also has a second mode, access order, which fits building a small LRU cache. This lesson covers both modes, the doubly-linked list that makes them work, how to bound the size by overriding removeEldestEntry, and when picking LinkedHashMap over HashMap or TreeMap is appropriate.

A plain HashMap stores entries in buckets chosen by hash code. Iteration walks the bucket array, which has no relation to insertion order. Two runs of the same program can iterate in different orders if the JVM rearranges entries during resizing. For most lookups that's fine, but it's a problem the moment a stable iteration order is required.

Consider a shopping cart. The user adds a notebook, then a pen, then an eraser. When the cart renders on the page, those rows should appear in the order they were added, not the order the hash function produced. With a plain HashMap, the order is unpredictable.

The output isn't wrong, it's just not the insertion order. The user added the notebook first, but the eraser printed first. Swap HashMap for LinkedHashMap and the output lines up with what the user did.

Same API, same Map interface, same average performance. The only visible difference is that iteration follows the insertion order.

LinkedHashMap extends HashMap. The bucket array, the hash function, and the resize behavior are all inherited. What LinkedHashMap adds is a doubly-linked list that threads through every entry. Each entry remembers the previous entry and the next entry in the order it should be visited. Iteration walks this list from head to tail instead of scanning the bucket array.

The diagram below shows the two structures side by side for a small cart. The buckets on the left are hash-driven, the same as HashMap. The arrows at the bottom show the linked list overlay that captures insertion order.

The same three entries appear in both pictures. The bucket layout decides where lookup goes. The linked list decides what iteration sees. A put("Eraser", 3) lands the entry in whatever bucket its hash points to, and at the same time appends it to the end of the linked list. A remove("Pen") takes the entry out of its bucket and unlinks it from the list at the same time, with the neighbors stitched back together.

Lookup never walks the list. It uses the bucket array, just like HashMap, so get and containsKey stay average O(1). The list is touched only when entries are added, removed, or, in access-order mode, accessed.

Each entry in LinkedHashMap carries two extra references (a before and an after pointer) compared with HashMap. For a few thousand entries the overhead is invisible. For tens of millions of entries it adds up, and a plain HashMap is the cheaper choice when ordering isn't needed.

The constructor controls which order the linked list follows. The no-argument constructor uses insertion order, the mode shown so far. The three-argument constructor with accessOrder = true switches the list to access order, where every get or put of an existing key moves that entry to the end of the list.

The signature is LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder). The first two parameters work the same way they do in HashMap. The third controls ordering mode.

Each get promotes the touched key to the tail of the list, which is treated as "most recently used". The entry at the head hasn't been touched the longest. This is the structure an LRU cache needs.

The diagram below traces the same access-order behavior. The list starts as Notebook -> Pen -> Eraser. After get("Notebook"), the list becomes Pen -> Eraser -> Notebook. The entry physically stays in the same hash bucket; only its position in the linked list overlay changes.

put on an existing key counts as an access, so it also moves the entry to the tail. put on a new key appends it to the tail (that part is the same as insertion order). containsKey and containsValue are not considered accesses and don't reorder the list. Neither does iteration through keySet, values, or entrySet.

Access-order mode by itself doesn't evict anything. To turn LinkedHashMap into a real cache that drops the oldest entries when it fills up, override removeEldestEntry. This method is called automatically after every put and putAll. If it returns true, the entry at the head of the list (the least recently used one) is removed before the method returns.

The contract: read the size of the map, compare it with the maximum to enforce, and return true to evict.

The first three inserts fit within the capacity, so nothing is evicted. The fourth insert pushes the size to 4, removeEldestEntry returns true, and the head of the list (Notebook) is dropped. After that, viewing Pen promotes it to the tail. When Stapler is inserted, the new head is Backpack, which is evicted next.

A few details:

Eviction itself is O(1). removeEldestEntry is consulted on every put, so the implementation should stay cheap. A check that scans the map turns an O(1) operation into something slower.

LinkedHashMap sits between HashMap and TreeMap in the design space. Pick it for one of the two specific guarantees it provides, and stick with HashMap otherwise.

Some concrete situations where LinkedHashMap is the natural fit:

Two situations where LinkedHashMap is the wrong tool:

For everyday workloads, treat LinkedHashMap as having the same big-O behavior as HashMap. The list operations on insert, remove, and access are O(1) because the entry already knows its neighbors, so unlinking and relinking is constant time. The only operations that touch every entry are iteration and clearing, both O(n) regardless of map choice.

Memory is the visible cost. A HashMap.Node holds the key, value, hash, and next pointer. A LinkedHashMap.Entry adds a before and after reference on top of that. On a 64-bit JVM with compressed oops, that's roughly 16 extra bytes per entry. For a cache of 10,000 items, that's about 160 KB of overhead, which is negligible. For 100 million items, it's 1.6 GB, which is not.

Iteration is one place LinkedHashMap actually beats HashMap. Walking the linked list visits each entry once with two pointer reads per step. Iterating HashMap scans the entire bucket array, including empty buckets, then follows the bucket chains. When the map is sparse (large capacity, few entries), LinkedHashMap iteration can be visibly faster than HashMap iteration, even though both are O(n) in the size of the map.

Same five inserts, same key-value pairs, two different orders on iteration. The HashMap order depends on the hash codes of the strings and the current bucket array size, neither of which is part of the API contract. The LinkedHashMap order is locked to the order the puts happened.

For thread safety, LinkedHashMap itself is not synchronized. Wrapping it with Collections.synchronizedMap works, but is tricky for an LRU cache, because access-order mode mutates the list on get. Two threads reading the same key can race. For concurrent LRU caches, libraries like Caffeine or Guava's cache fit better. ConcurrentHashMap appears later in the section; it does not preserve any order.