LinkedHashMap extends HashMap to preserve the order of entries—either by insertion or access sequence—while retaining O(1) average-time complexity for lookups. It achieves this by combining HashMap’s hash table structure with an additional doubly linked list that tracks entry order.

Core Structure

LinkedHashMap reuses HashMap’s underlying array-of-buckets, where each bucket may contain a linked list or red-black tree of nodes. On top of this, it maintains a separate doubly linked list using enhanced node objects:

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Each Entry participates in both the hash table (via next) and the doubly linked list (via before and after).

Three key fields manage the linked list:

• head: points to the least recently added or accessed entry
• tail: points to the most recently added or accessed entry
• accessOrder: if true, ordering reflects access sequence; otherwise, insertion sequence (default)

Order Maintenance via Hook Methods

Rather than overriding put() or get(), LinkedHashMap customizes behavior by implementing three callback methods defined as empty in HashMap:

• afterNodeInsertion(boolean evict)
• afterNodeAccess(Node<K,V> p)
• afterNodeRemoval(Node<K,V> p)

Insertion

When a new entry is inserted:

1. HashMap handles the hash table update.
2. newNode() creates a LinkedHashMap.Entry and appends it to the tail of the doubly linked list via linkNodeLast():

private void linkNodeLast(Entry<K,V> newNode) {
    Entry<K,V> prevTail = tail;
    tail = newNode;
    if (prevTail == null) {
        head = newNode;
    } else {
        newNode.before = prevTail;
        prevTail.after = newNode;
    }
}

Access (for accessOrder = true)

On get(key), if accessOrder is enabled, the retrieved node is moved to the tail:

void afterNodeAccess(Node<K,V> node) {
    Entry<K,V> e = (Entry<K,V>) node;
    if (accessOrder && tail != e) {
        Entry<K,V> before = e.before, after = e.after;
        e.after = null;

        if (before == null) head = after;
        else before.after = after;

        if (after != null) after.before = before;
        else tail = before;

        if (tail == null) head = e;
        else {
            e.before = tail;
            tail.after = e;
        }
        tail = e;
        ++modCount;
    }
}

Removal

When an entry is removed, afterNodeRemoval() unlinks it from the doubly linked list:

void afterNodeRemoval(Node<K,V> node) {
    Entry<K,V> e = (Entry<K,V>) node;
    Entry<K,V> before = e.before, after = e.after;
    e.before = e.after = null;

    if (before == null) head = after;
    else before.after = after;

    if (after == null) tail = before;
    else after.before = before;
}

LRU Cache Implementation

By overriding removeEldestEntry(), LinkedHashMap can automatically evict the least recently used entry when size exceeds a threshold:

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

    LRUCache(int capacity) {
        super(16, 0.75f, true); // access-order mode
        this.capacity = capacity;
    }

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

This works because in access-order mode, the head of the list is always the least recently used entry.

Key Characteristics

• Ordering: Guaranteed iteration order (insertion or access)
• Performance: Same O(1) average lookup as HashMap; faster iteration due to direct linked list traversal
• Memory: Higher overhead due to two extra pointers per entry
• Nulls: Supports one null key and multiple null values
• Thread Safety: Not thread-safe

When to Use

• Preserving insertion order (e.g., configuration loading)
• Implementing LRU caches
• Generating ordered output (e.g., recent activity logs)

Unlike HashMap, which offers no iteration guarantees, LinkedHashMap provides predictable traversal while maintaining efficient key-based access.