DSA-150 · Key-to-node lookup plus sentinel-based doubly linked recency order

LRU Cache

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1840872 deterministic checks. Learner drafts are not executed.

Understand the problem

Implement a fixed-capacity least-recently-used cache mapping int keys to int values. Successful get and every put make the affected key most recently used. When a new key enters a full cache, evict the least recently used key.

Construct Solution.LRUCache(capacity) with capacity in 0..100000; other capacities throw IllegalArgumentException. Zero capacity is supported and stores nothing. All signed int keys and values are valid, including zero, −1, MIN_VALUE, and MAX_VALUE. Capacity never changes.
get(int key) returns OptionalInt.of(value) on a hit and OptionalInt.empty() on a miss. A hit promotes that same entry to most recent; a miss does not change order. OptionalInt avoids confusing a stored −1 with absence. No nullable keys or values are involved.
put(int key,int value) returns void. An existing key changes value and becomes most recent without growing the cache or evicting another key, even when full. A missing key enters as most recent; if full, remove the least recent resident first. Capacity zero makes put a no-op.
size() and capacity() are read-only metadata and do not count as accesses. Each cache owns its map, sentinels, and nodes. There is no expiry, resizing, persistence, loading callback, or concurrency guarantee; callers must serialize operations. Even a successful get mutates recency.
Trace outcomes are in operation order: put→null for void, get miss→null for OptionalInt.empty(), get hit→the signed int, size→the count. The operation label disambiguates void from miss. Constructor failure is a thrown outcome rather than an operation result. Histories and retired-node cards are teaching data not retained by the Java cache.

Examples

Input: capacity=2; ops=[put(1,10),put(2,20),get(1),put(3,30),get(2),size()]
Output: [null,null,10,null,null,2]
get(1) changes recency to [1,2], so inserting three evicts two; a miss does not promote anything.
Input: capacity=2; ops=[put(1,-1),put(2,2),put(1,99),put(3,3),get(1),get(2)]
Output: [null,null,null,null,99,null]
Updating one reuses and promotes its node. It does not consume another slot; adding three evicts two.
Input: capacity=0; ops=[put(7,-1),get(7),size()]
Output: [null,null,0]
The zero-capacity cache remains empty; its sentinel links stay valid.

Before you start

Hash maps from keys to exact object identities
Doubly linked lists, sentinel nodes, and constant-time unlinking

Recognize the structure

The API needs two unrelated abilities at once: find an arbitrary key quickly and remove whichever entry is least recent. A hash map alone does not encode recency; an ordered list alone needs a scan to locate a key. Store a map from each key to its exact node in a doubly linked list. With the node in hand, unlinking and moving it to the most-recent end needs only neighboring references. Two sentinels remove empty/head/tail special cases from real-node operations.

Try before revealing

Hint 1

Which structure finds a key directly, and which structure exposes the oldest access at one end?

Hint 2

Map each key to its exact list node so promotion does not require a list search.

Hint 3

Keep most recent after HEAD, least recent before TAIL, and preserve the map/list bijection at every public return.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Maintain a most-recent-first array list of key/value entries

Scan the list to find a requested key. On a hit or update, remove that entry and insert it at index zero; on a new key, discard the last entry if full and insert at zero. A zero-capacity cache ignores puts. This direct model makes the recency contract visible but takes O(C+1) worst-case time per get/put from lookup and shifting, for capacity C. The test oracle is different again: it records monotone logical last-access timestamps and selects/sorts by those timestamps, independently of pointer operations and list shifting.

Improve the baseline

Choose an orientation and stable identities

HEAD.next is most recent and TAIL.previous is least recent. Only real key/value nodes appear in the index. HEAD and TAIL are distinct private objects whose dummy key fields have no semantic meaning, even when a real key is zero. A key hit or update keeps its existing node identity; eviction removes that identity and a later reinsertion allocates a new node.

State the representation invariant at public boundaries

Every indexed key maps to exactly one real node in the list, every real list node is indexed by its own key, and no node appears twice. Forward and backward links agree. HEAD.previous and TAIL.next are null; the empty list has HEAD.next=TAIL and TAIL.previous=HEAD. Size never exceeds capacity, and list order matches descending last successful-get/put time. Metadata reads and misses do not change that time.

Derive unlink and front insertion locally

For a real resident node, join node.previous directly to node.next in both directions, then clear the detached node’s own two links. To insert at the front, point the node to HEAD and the old first node, update that old first node’s previous link, then update HEAD.next. The same statements handle a one-entry list because sentinels are always present. Never pass a sentinel to unlink.

Promote hits and existing-key updates

A successful get looks up the node, detaches it, reinserts it after HEAD, and returns its value. An existing put changes its value and uses the same promotion. It does not allocate a replacement node or evict a neighbor. Promoting an already most-recent node is harmless, including at capacity one. During the private detach/relink sequence, the indexed node is temporarily outside the list; the stable public invariant is restored before returning.

Insert missing keys only after handling zero and fullness

At capacity zero return without inserting. Otherwise, if index.size()==capacity, TAIL.previous identifies a real least-recent victim. Unlink it and remove its key from the map. Then allocate one new node, link it after HEAD, and index it. Evicting before insertion keeps resident size within the fixed capacity and avoids evicting the just-updated key in the existing-key branch.

Keep complexity and concurrency claims precise

List pointer work is worst-case constant per operation, while map lookup/update costs use an expected/amortized hash-table model. This is not a universal worst-case O(1) guarantee. The methods are not atomic across threads: even get rewires shared links. No lock, timestamp array, scan for the oldest entry, or eviction-history collection is part of the reference.

Why it is correct

Empty construction and local list operations

Construction joins the two sentinels and leaves an empty map, establishing the bijection, link, size and order invariants. Unlink preserves every other node’s relative order and reconnects both neighboring directions. Front insertion adds the detached node exactly once and restores both directions at the new first position. Sentinel identities make these arguments valid for empty and singleton transitions.

Hit and update transitions

A miss changes nothing. A hit moves exactly the accessed node to the front, leaving all other relative recency order unchanged; the map still names that same node. Updating changes only the resident value and performs the same promotion, so membership and size stay fixed. These transitions implement precisely a new last-access time for the affected key. The private temporary detached state is not exposed as a completed operation.

New-key insertion and least-recent eviction

For positive capacity, a nonfull insertion adds one previously absent key at the front. In a full cache, the invariant identifies TAIL.previous as the minimum-recency resident; removing that node and its map entry deletes exactly the policy’s victim, then insertion adds the new most-recent key. The map/list bijection and capacity bound hold again at return. Zero capacity retains the empty invariant.

Complete operation sequences and instance ownership

Induct over any finite serialized sequence of valid operations. Each constructor establishes the invariant and every operation preserves it while producing the specified OptionalInt or metadata result. No traversal is needed by the public implementation. Distinct cache instances allocate separate state, and callers cannot obtain or mutate private node references through the API.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.OptionalInt;

public final class Solution {
    private Solution() {}
    private static void validateCapacity(int capacity) {
        if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
    }
    public static final class LRUCache {
        private static final class Node {
            final int key;
            int value;
            Node previous, next;
            Node(int key, int value) { this.key = key; this.value = value; }
        }
        private final int capacity;
        private final Map<Integer, Node> index = new HashMap<>();
        private final Node head = new Node(0, 0), tail = new Node(0, 0);
        public LRUCache(int capacity) {
            validateCapacity(capacity);
            this.capacity = capacity;
            head.next = tail;
            tail.previous = head;
        }
        private void unlink(Node node) {
            node.previous.next = node.next;
            node.next.previous = node.previous;
            node.previous = null;
            node.next = null;
        }
        private void linkMostRecent(Node node) {
            node.previous = head;
            node.next = head.next;
            head.next.previous = node;
            head.next = node;
        }
        private void touch(Node node) {
            unlink(node);
            linkMostRecent(node);
        }
        public OptionalInt get(int key) {
            Node node = index.get(key);
            if (node == null) return OptionalInt.empty();
            touch(node);
            return OptionalInt.of(node.value);
        }
        public void put(int key, int value) {
            Node node = index.get(key);
            if (node != null) {
                node.value = value;
                touch(node);
                return;
            }
            if (capacity == 0) return;
            if (index.size() == capacity) {
                Node victim = tail.previous;
                unlink(victim);
                index.remove(victim.key);
            }
            Node inserted = new Node(key, value);
            linkMostRecent(inserted);
            index.put(key, inserted);
        }
        public int size() { return index.size(); }
        public int capacity() { return capacity; }
    }
    // Linear MRU-first array-list model; independent of pointer manipulation.
    public static final class Baseline {
        private record Entry(int key, int value) {}
        private final int capacity;
        private final ArrayList<Entry> entries = new ArrayList<>();
        public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
        public OptionalInt get(int key) {
            for (int i = 0; i < entries.size(); i++) {
                if (entries.get(i).key() == key) {
                    Entry entry = entries.remove(i);
                    entries.add(0, entry);
                    return OptionalInt.of(entry.value());
                }
            }
            return OptionalInt.empty();
        }
        public void put(int key, int value) {
            for (int i = 0; i < entries.size(); i++) {
                if (entries.get(i).key() == key) {
                    entries.remove(i);
                    entries.add(0, new Entry(key, value));
                    return;
                }
            }
            if (capacity == 0) return;
            if (entries.size() == capacity) entries.removeLast();
            entries.add(0, new Entry(key, value));
        }
        public int size() { return entries.size(); }
        public int capacity() { return capacity; }
    }
}

Read the meaningful blocks

Own private map and sentinel state

The map stores Node references, not positions or duplicate value records. Final sentinel references identify boundaries even when real keys match their dummy values. Constructor validation fixes the maximum supported capacity without preallocating a capacity-sized list.

Use the two helpers only on their intended states

unlink accepts a real linked node, while linkMostRecent accepts a detached/new node. Clearing detached links prevents stale neighbor references on an evicted node. touch composes the two helpers and keeps a hit/update’s exact identity. No helper is a public cache operation.

Separate existing-key, zero-capacity, and new-key branches

Handle a resident update first, then the zero-capacity case, then possible eviction. Removing the victim’s map entry is as important as unlinking it; retaining either representation would create a ghost resident. size and capacity do not call get or promote anything.

Complexity

For C fixed capacity and s current residents, get and put perform O(1) pointer work and expected/amortized O(1) map work under a hash-table model; hash-map resizing and collision behavior prevent a blanket worst-case constant-time claim. size and capacity take O(1). Construction takes O(1) without allocating C nodes.

Retained storage is O(s+1), bounded by O(C+1), for one map entry and node per resident plus two sentinels. A zero-capacity cache still has constant state. The array-list baseline uses O(C+1) storage and O(C+1) worst-case get/put time. Snapshots, retired identities, timestamps, reflection checks and trace histories belong to verification/teaching, not reference memory.

Exact-state walkthroughs

Reveal normal and boundary traces

A successful read changes the next eviction victim

Input: {"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]} · Operation outcomes in call order / constructor failure: [null,null,10,null,null,2]

Step 1 of 23: Create private sentinels and an empty key-to-node index.

HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.

LRU Cache — exact key lookup and reciprocal recency links

Phase: initial. Fixed capacity: 2.

Indexed residents: 0. Linked real nodes: 0. HEAD.next is most recent; TAIL.previous is least recent. Sentinel identities have no cache key.

MRU → LRU order of currently linked real nodes

Empty.

Key → exact node index — sorted display copy, not HashMap iteration order

Empty.

Sentinels and live or pending node identities

HEAD — sentinelprevious → nullnext → TAILsentinel
TAIL — sentinelprevious → HEADnext → nullsentinel

Completed outcomes — decoded by original operation

Empty.

MRU key order after each completed operation — teaching history

Empty.

Successful gets and every stored/new put promote. Misses and metadata reads leave order unchanged. The public invariant requires one indexed real node per resident and matching forward/backward links.

Pointer work is constant; map costs are expected/amortized. Calls must be serialized because hits mutate recency. Histories and sorted index cards are excluded from cache workspace.

State after this step
Variable	Value
input	`{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}`
phase	`"initial"`
capacity	`2`
nodes	`[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]`
lookup	`[]`
order	`[]`
pending	`null`
outcomes	`[]`
history	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.OptionalInt;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validateCapacity(int capacity) {
 9         if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
10     }
11     public static final class LRUCache {
12         private static final class Node {
13             final int key;
14             int value;
15             Node previous, next;
16             Node(int key, int value) { this.key = key; this.value = value; }
17         }
18         private final int capacity;
19         private final Map<Integer, Node> index = new HashMap<>();
20         private final Node head = new Node(0, 0), tail = new Node(0, 0);
21         public LRUCache(int capacity) {
22             validateCapacity(capacity);
23             this.capacity = capacity;
24             head.next = tail;
25             tail.previous = head;
26         }
27         private void unlink(Node node) {
28             node.previous.next = node.next;
29             node.next.previous = node.previous;
30             node.previous = null;
31             node.next = null;
32         }
33         private void linkMostRecent(Node node) {
34             node.previous = head;
35             node.next = head.next;
36             head.next.previous = node;
37             head.next = node;
38         }
39         private void touch(Node node) {
40             unlink(node);
41             linkMostRecent(node);
42         }
43         public OptionalInt get(int key) {
44             Node node = index.get(key);
45             if (node == null) return OptionalInt.empty();
46             touch(node);
47             return OptionalInt.of(node.value);
48         }
49         public void put(int key, int value) {
50             Node node = index.get(key);
51             if (node != null) {
52                 node.value = value;
53                 touch(node);
54                 return;
55             }
56             if (capacity == 0) return;
57             if (index.size() == capacity) {
58                 Node victim = tail.previous;
59                 unlink(victim);
60                 index.remove(victim.key);
61             }
62             Node inserted = new Node(key, value);
63             linkMostRecent(inserted);
64             index.put(key, inserted);
65         }
66         public int size() { return index.size(); }
67         public int capacity() { return capacity; }
68     }
69     // Linear MRU-first array-list model; independent of pointer manipulation.
70     public static final class Baseline {
71         private record Entry(int key, int value) {}
72         private final int capacity;
73         private final ArrayList<Entry> entries = new ArrayList<>();
74         public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
75         public OptionalInt get(int key) {
76             for (int i = 0; i < entries.size(); i++) {
77                 if (entries.get(i).key() == key) {
78                     Entry entry = entries.remove(i);
79                     entries.add(0, entry);
80                     return OptionalInt.of(entry.value());
81                 }
82             }
83             return OptionalInt.empty();
84         }
85         public void put(int key, int value) {
86             for (int i = 0; i < entries.size(); i++) {
87                 if (entries.get(i).key() == key) {
88                     entries.remove(i);
89                     entries.add(0, new Entry(key, value));
90                     return;
91                 }
92             }
93             if (capacity == 0) return;
94             if (entries.size() == capacity) entries.removeLast();
95             entries.add(0, new Entry(key, value));
96         }
97         public int size() { return entries.size(); }
98         public int capacity() { return capacity; }
99     }
100 }
101

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create private sentinels and an empty key-to-node index.
HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"initial"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":1,"value":10}
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"insert"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":1,"value":10}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
0
operation
{"type":"put","key":1,"value":10}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":20}
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"insert"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":20}
nodeId
"N1"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":20}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"get","key":1}
Find the exact indexed resident node.
The map locates a node directly; no list scan is needed.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"hit"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"get","key":1}
nodeId
"N0"
Detach this same resident node before promotion.
Private transient state: the map still names the detached node. Its links are null and it awaits reattachment; other resident order is unchanged. The public bijection is restored before return.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"detach"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":null,"next":null,"status":"detached"},{"id":"N1","key":2,"value":20,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1"]
pending
"N0"
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"get","key":1}
nodeId
"N0"
Reattach the existing node immediately after HEAD.
The original node identity and indexed key remain unchanged. A most-recent hit may pass through a temporarily empty list at capacity one.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"promote"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"HEAD","next":"N1","status":"linked"},{"id":"N1","key":2,"value":20,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N0","N1"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"get","key":1}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"HEAD","next":"N1","status":"linked"},{"id":"N1","key":2,"value":20,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N0","N1"]
pending
null
outcomes
[null,null,10]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]}]
operationIndex
2
operation
{"type":"get","key":1}
outcome
10
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"HEAD","next":"N1","status":"linked"},{"id":"N1","key":2,"value":20,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N0","N1"]
pending
null
outcomes
[null,null,10]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]}]
operationIndex
3
operation
{"type":"put","key":3,"value":30}
Remove the least-recent node from both representations.
TAIL.previous identified the oldest resident. The retired card is historical teaching data; Java does not retain a list of evicted nodes. Its own links are cleared.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"evict"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"HEAD","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,null,10]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]}]
operationIndex
3
operation
{"type":"put","key":3,"value":30}
victimId
"N1"
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"insert"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":30,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,10]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]}]
operationIndex
3
operation
{"type":"put","key":3,"value":30}
nodeId
"N2"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":30,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,10,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]}]
operationIndex
3
operation
{"type":"put","key":3,"value":30}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":30,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,10,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]}]
operationIndex
4
operation
{"type":"get","key":2}
A missing key has no effect on recency.
An empty OptionalInt is distinct from a stored −1. No node is allocated, removed or promoted.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"miss"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":30,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,10,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]}]
operationIndex
4
operation
{"type":"get","key":2}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":30,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,10,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[3,1]}]
operationIndex
4
operation
{"type":"get","key":2}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":30,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,10,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[3,1]}]
operationIndex
5
operation
{"type":"size"}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":30,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,10,null,null,2]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[3,1]},{"operationIndex":5,"keysMRU":[3,1]}]
operationIndex
5
operation
{"type":"size"}
outcome
2
The finite operation sequence is complete.
Outcome order matches call order. Histories, sorted map cards and retired node identities explain state but are not Java cache allocations.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":10},{"type":"put","key":2,"value":20},{"type":"get","key":1},{"type":"put","key":3,"value":30},{"type":"get","key":2},{"type":"size"}]}
phase
"complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":10,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":20,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":30,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,10,null,null,2]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[3,1]},{"operationIndex":5,"keysMRU":[3,1]}]
Return the documented operation outcomes or constructor failure.
A stateful cache returns one value per get/metadata call and void for puts. It does not return its private list or node references.
result
[null,null,10,null,null,2]

Updating a full cache reuses its node without eviction

Input: {"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]} · Operation outcomes in call order / constructor failure: [null,null,null,null,99,null]

Step 1 of 26: Create private sentinels and an empty key-to-node index.

HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.

LRU Cache — exact key lookup and reciprocal recency links

Phase: initial. Fixed capacity: 2.

Indexed residents: 0. Linked real nodes: 0. HEAD.next is most recent; TAIL.previous is least recent. Sentinel identities have no cache key.

MRU → LRU order of currently linked real nodes

Empty.

Key → exact node index — sorted display copy, not HashMap iteration order

Empty.

Sentinels and live or pending node identities

HEAD — sentinelprevious → nullnext → TAILsentinel
TAIL — sentinelprevious → HEADnext → nullsentinel

Completed outcomes — decoded by original operation

Empty.

MRU key order after each completed operation — teaching history

Empty.

Pointer work is constant; map costs are expected/amortized. Calls must be serialized because hits mutate recency. Histories and sorted index cards are excluded from cache workspace.

State after this step
Variable	Value
input	`{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}`
phase	`"initial"`
capacity	`2`
nodes	`[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]`
lookup	`[]`
order	`[]`
pending	`null`
outcomes	`[]`
history	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.OptionalInt;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validateCapacity(int capacity) {
 9         if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
10     }
11     public static final class LRUCache {
12         private static final class Node {
13             final int key;
14             int value;
15             Node previous, next;
16             Node(int key, int value) { this.key = key; this.value = value; }
17         }
18         private final int capacity;
19         private final Map<Integer, Node> index = new HashMap<>();
20         private final Node head = new Node(0, 0), tail = new Node(0, 0);
21         public LRUCache(int capacity) {
22             validateCapacity(capacity);
23             this.capacity = capacity;
24             head.next = tail;
25             tail.previous = head;
26         }
27         private void unlink(Node node) {
28             node.previous.next = node.next;
29             node.next.previous = node.previous;
30             node.previous = null;
31             node.next = null;
32         }
33         private void linkMostRecent(Node node) {
34             node.previous = head;
35             node.next = head.next;
36             head.next.previous = node;
37             head.next = node;
38         }
39         private void touch(Node node) {
40             unlink(node);
41             linkMostRecent(node);
42         }
43         public OptionalInt get(int key) {
44             Node node = index.get(key);
45             if (node == null) return OptionalInt.empty();
46             touch(node);
47             return OptionalInt.of(node.value);
48         }
49         public void put(int key, int value) {
50             Node node = index.get(key);
51             if (node != null) {
52                 node.value = value;
53                 touch(node);
54                 return;
55             }
56             if (capacity == 0) return;
57             if (index.size() == capacity) {
58                 Node victim = tail.previous;
59                 unlink(victim);
60                 index.remove(victim.key);
61             }
62             Node inserted = new Node(key, value);
63             linkMostRecent(inserted);
64             index.put(key, inserted);
65         }
66         public int size() { return index.size(); }
67         public int capacity() { return capacity; }
68     }
69     // Linear MRU-first array-list model; independent of pointer manipulation.
70     public static final class Baseline {
71         private record Entry(int key, int value) {}
72         private final int capacity;
73         private final ArrayList<Entry> entries = new ArrayList<>();
74         public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
75         public OptionalInt get(int key) {
76             for (int i = 0; i < entries.size(); i++) {
77                 if (entries.get(i).key() == key) {
78                     Entry entry = entries.remove(i);
79                     entries.add(0, entry);
80                     return OptionalInt.of(entry.value());
81                 }
82             }
83             return OptionalInt.empty();
84         }
85         public void put(int key, int value) {
86             for (int i = 0; i < entries.size(); i++) {
87                 if (entries.get(i).key() == key) {
88                     entries.remove(i);
89                     entries.add(0, new Entry(key, value));
90                     return;
91                 }
92             }
93             if (capacity == 0) return;
94             if (entries.size() == capacity) entries.removeLast();
95             entries.add(0, new Entry(key, value));
96         }
97         public int size() { return entries.size(); }
98         public int capacity() { return capacity; }
99     }
100 }
101

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create private sentinels and an empty key-to-node index.
HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"initial"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":1,"value":-1}
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"insert"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":1,"value":-1}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
0
operation
{"type":"put","key":1,"value":-1}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":2}
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"insert"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":-1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":2}
nodeId
"N1"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":-1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":2}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":-1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"put","key":1,"value":99}
Change the existing value without growing membership.
An update at full capacity must not evict a neighbor or allocate a replacement identity. Recency promotion follows.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"update"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"put","key":1,"value":99}
nodeId
"N0"
Detach this same resident node before promotion.
Private transient state: the map still names the detached node. Its links are null and it awaits reattachment; other resident order is unchanged. The public bijection is restored before return.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"detach"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":null,"next":null,"status":"detached"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1"]
pending
"N0"
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"put","key":1,"value":99}
nodeId
"N0"
Reattach the existing node immediately after HEAD.
The original node identity and indexed key remain unchanged. A most-recent hit may pass through a temporarily empty list at capacity one.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"promote"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N1","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N0","N1"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"put","key":1,"value":99}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N1","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N0","N1"]
pending
null
outcomes
[null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]}]
operationIndex
2
operation
{"type":"put","key":1,"value":99}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N1","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N0","N1"]
pending
null
outcomes
[null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]}]
operationIndex
3
operation
{"type":"put","key":3,"value":3}
Remove the least-recent node from both representations.
TAIL.previous identified the oldest resident. The retired card is historical teaching data; Java does not retain a list of evicted nodes. Its own links are cleared.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"evict"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]}]
operationIndex
3
operation
{"type":"put","key":3,"value":3}
victimId
"N1"
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"insert"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]}]
operationIndex
3
operation
{"type":"put","key":3,"value":3}
nodeId
"N2"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]}]
operationIndex
3
operation
{"type":"put","key":3,"value":3}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]}]
operationIndex
4
operation
{"type":"get","key":1}
Find the exact indexed resident node.
The map locates a node directly; no list scan is needed.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"hit"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"N2","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2","N0"]
pending
null
outcomes
[null,null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]}]
operationIndex
4
operation
{"type":"get","key":1}
nodeId
"N0"
Detach this same resident node before promotion.
Private transient state: the map still names the detached node. Its links are null and it awaits reattachment; other resident order is unchanged. The public bijection is restored before return.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"detach"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":null,"next":null,"status":"detached"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N2"]
pending
"N0"
outcomes
[null,null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]}]
operationIndex
4
operation
{"type":"get","key":1}
nodeId
"N0"
Reattach the existing node immediately after HEAD.
The original node identity and indexed key remain unchanged. A most-recent hit may pass through a temporarily empty list at capacity one.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"promote"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N2","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N0","N2"]
pending
null
outcomes
[null,null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]}]
operationIndex
4
operation
{"type":"get","key":1}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N2","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N0","N2"]
pending
null
outcomes
[null,null,null,null,99]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[1,3]}]
operationIndex
4
operation
{"type":"get","key":1}
outcome
99
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N2","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N0","N2"]
pending
null
outcomes
[null,null,null,null,99]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[1,3]}]
operationIndex
5
operation
{"type":"get","key":2}
A missing key has no effect on recency.
An empty OptionalInt is distinct from a stored −1. No node is allocated, removed or promoted.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"miss"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N2","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N0","N2"]
pending
null
outcomes
[null,null,null,null,99]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[1,3]}]
operationIndex
5
operation
{"type":"get","key":2}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N2","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N0","N2"]
pending
null
outcomes
[null,null,null,null,99,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[1,3]},{"operationIndex":5,"keysMRU":[1,3]}]
operationIndex
5
operation
{"type":"get","key":2}
outcome
null
The finite operation sequence is complete.
Outcome order matches call order. Histories, sorted map cards and retired node identities explain state but are not Java cache allocations.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":-1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":99},{"type":"put","key":3,"value":3},{"type":"get","key":1},{"type":"get","key":2}]}
phase
"complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":99,"previous":"HEAD","next":"N2","status":"linked"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":3,"value":3,"previous":"N0","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":3,"node":"N2"}]
order
["N0","N2"]
pending
null
outcomes
[null,null,null,null,99,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[1,2]},{"operationIndex":3,"keysMRU":[3,1]},{"operationIndex":4,"keysMRU":[1,3]},{"operationIndex":5,"keysMRU":[1,3]}]
Return the documented operation outcomes or constructor failure.
A stateful cache returns one value per get/metadata call and void for puts. It does not return its private list or node references.
result
[null,null,null,null,99,null]

Zero capacity stores no resident nodes

Input: {"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]} · Operation outcomes in call order / constructor failure: [null,null,0]

Step 1 of 11: Create private sentinels and an empty key-to-node index.

HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.

LRU Cache — exact key lookup and reciprocal recency links

Phase: initial. Fixed capacity: 0.

Indexed residents: 0. Linked real nodes: 0. HEAD.next is most recent; TAIL.previous is least recent. Sentinel identities have no cache key.

MRU → LRU order of currently linked real nodes

Empty.

Key → exact node index — sorted display copy, not HashMap iteration order

Empty.

Sentinels and live or pending node identities

HEAD — sentinelprevious → nullnext → TAILsentinel
TAIL — sentinelprevious → HEADnext → nullsentinel

Completed outcomes — decoded by original operation

Empty.

MRU key order after each completed operation — teaching history

Empty.

Pointer work is constant; map costs are expected/amortized. Calls must be serialized because hits mutate recency. Histories and sorted index cards are excluded from cache workspace.

State after this step
Variable	Value
input	`{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}`
phase	`"initial"`
capacity	`0`
nodes	`[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]`
lookup	`[]`
order	`[]`
pending	`null`
outcomes	`[]`
history	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.OptionalInt;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validateCapacity(int capacity) {
 9         if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
10     }
11     public static final class LRUCache {
12         private static final class Node {
13             final int key;
14             int value;
15             Node previous, next;
16             Node(int key, int value) { this.key = key; this.value = value; }
17         }
18         private final int capacity;
19         private final Map<Integer, Node> index = new HashMap<>();
20         private final Node head = new Node(0, 0), tail = new Node(0, 0);
21         public LRUCache(int capacity) {
22             validateCapacity(capacity);
23             this.capacity = capacity;
24             head.next = tail;
25             tail.previous = head;
26         }
27         private void unlink(Node node) {
28             node.previous.next = node.next;
29             node.next.previous = node.previous;
30             node.previous = null;
31             node.next = null;
32         }
33         private void linkMostRecent(Node node) {
34             node.previous = head;
35             node.next = head.next;
36             head.next.previous = node;
37             head.next = node;
38         }
39         private void touch(Node node) {
40             unlink(node);
41             linkMostRecent(node);
42         }
43         public OptionalInt get(int key) {
44             Node node = index.get(key);
45             if (node == null) return OptionalInt.empty();
46             touch(node);
47             return OptionalInt.of(node.value);
48         }
49         public void put(int key, int value) {
50             Node node = index.get(key);
51             if (node != null) {
52                 node.value = value;
53                 touch(node);
54                 return;
55             }
56             if (capacity == 0) return;
57             if (index.size() == capacity) {
58                 Node victim = tail.previous;
59                 unlink(victim);
60                 index.remove(victim.key);
61             }
62             Node inserted = new Node(key, value);
63             linkMostRecent(inserted);
64             index.put(key, inserted);
65         }
66         public int size() { return index.size(); }
67         public int capacity() { return capacity; }
68     }
69     // Linear MRU-first array-list model; independent of pointer manipulation.
70     public static final class Baseline {
71         private record Entry(int key, int value) {}
72         private final int capacity;
73         private final ArrayList<Entry> entries = new ArrayList<>();
74         public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
75         public OptionalInt get(int key) {
76             for (int i = 0; i < entries.size(); i++) {
77                 if (entries.get(i).key() == key) {
78                     Entry entry = entries.remove(i);
79                     entries.add(0, entry);
80                     return OptionalInt.of(entry.value());
81                 }
82             }
83             return OptionalInt.empty();
84         }
85         public void put(int key, int value) {
86             for (int i = 0; i < entries.size(); i++) {
87                 if (entries.get(i).key() == key) {
88                     entries.remove(i);
89                     entries.add(0, new Entry(key, value));
90                     return;
91                 }
92             }
93             if (capacity == 0) return;
94             if (entries.size() == capacity) entries.removeLast();
95             entries.add(0, new Entry(key, value));
96         }
97         public int size() { return entries.size(); }
98         public int capacity() { return capacity; }
99     }
100 }
101

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create private sentinels and an empty key-to-node index.
HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"initial"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"operation"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":7,"value":-1}
Zero capacity stores no key or node.
The sentinels stay linked directly. A later get is still a miss.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"ignore"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":7,"value":-1}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"operation-complete"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[]}]
operationIndex
0
operation
{"type":"put","key":7,"value":-1}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"operation"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[]}]
operationIndex
1
operation
{"type":"get","key":7}
A missing key has no effect on recency.
An empty OptionalInt is distinct from a stored −1. No node is allocated, removed or promoted.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"miss"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[]}]
operationIndex
1
operation
{"type":"get","key":7}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"operation-complete"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[]},{"operationIndex":1,"keysMRU":[]}]
operationIndex
1
operation
{"type":"get","key":7}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"operation"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[]},{"operationIndex":1,"keysMRU":[]}]
operationIndex
2
operation
{"type":"size"}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"operation-complete"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[null,null,0]
history
[{"operationIndex":0,"keysMRU":[]},{"operationIndex":1,"keysMRU":[]},{"operationIndex":2,"keysMRU":[]}]
operationIndex
2
operation
{"type":"size"}
outcome
0
The finite operation sequence is complete.
Outcome order matches call order. Histories, sorted map cards and retired node identities explain state but are not Java cache allocations.
input
{"capacity":0,"ops":[{"type":"put","key":7,"value":-1},{"type":"get","key":7},{"type":"size"}]}
phase
"complete"
capacity
0
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[null,null,0]
history
[{"operationIndex":0,"keysMRU":[]},{"operationIndex":1,"keysMRU":[]},{"operationIndex":2,"keysMRU":[]}]
Return the documented operation outcomes or constructor failure.
A stateful cache returns one value per get/metadata call and void for puts. It does not return its private list or node references.
result
[null,null,0]

Signed extremes and a stored negative-one hit

Input: {"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]} · Operation outcomes in call order / constructor failure: [null,-1,null,null,-2147483648,1]

Step 1 of 25: Create private sentinels and an empty key-to-node index.

HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.

LRU Cache — exact key lookup and reciprocal recency links

Phase: initial. Fixed capacity: 1.

Indexed residents: 0. Linked real nodes: 0. HEAD.next is most recent; TAIL.previous is least recent. Sentinel identities have no cache key.

MRU → LRU order of currently linked real nodes

Empty.

Key → exact node index — sorted display copy, not HashMap iteration order

Empty.

Sentinels and live or pending node identities

HEAD — sentinelprevious → nullnext → TAILsentinel
TAIL — sentinelprevious → HEADnext → nullsentinel

Completed outcomes — decoded by original operation

Empty.

MRU key order after each completed operation — teaching history

Empty.

Pointer work is constant; map costs are expected/amortized. Calls must be serialized because hits mutate recency. Histories and sorted index cards are excluded from cache workspace.

State after this step
Variable	Value
input	`{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}`
phase	`"initial"`
capacity	`1`
nodes	`[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]`
lookup	`[]`
order	`[]`
pending	`null`
outcomes	`[]`
history	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.OptionalInt;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validateCapacity(int capacity) {
 9         if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
10     }
11     public static final class LRUCache {
12         private static final class Node {
13             final int key;
14             int value;
15             Node previous, next;
16             Node(int key, int value) { this.key = key; this.value = value; }
17         }
18         private final int capacity;
19         private final Map<Integer, Node> index = new HashMap<>();
20         private final Node head = new Node(0, 0), tail = new Node(0, 0);
21         public LRUCache(int capacity) {
22             validateCapacity(capacity);
23             this.capacity = capacity;
24             head.next = tail;
25             tail.previous = head;
26         }
27         private void unlink(Node node) {
28             node.previous.next = node.next;
29             node.next.previous = node.previous;
30             node.previous = null;
31             node.next = null;
32         }
33         private void linkMostRecent(Node node) {
34             node.previous = head;
35             node.next = head.next;
36             head.next.previous = node;
37             head.next = node;
38         }
39         private void touch(Node node) {
40             unlink(node);
41             linkMostRecent(node);
42         }
43         public OptionalInt get(int key) {
44             Node node = index.get(key);
45             if (node == null) return OptionalInt.empty();
46             touch(node);
47             return OptionalInt.of(node.value);
48         }
49         public void put(int key, int value) {
50             Node node = index.get(key);
51             if (node != null) {
52                 node.value = value;
53                 touch(node);
54                 return;
55             }
56             if (capacity == 0) return;
57             if (index.size() == capacity) {
58                 Node victim = tail.previous;
59                 unlink(victim);
60                 index.remove(victim.key);
61             }
62             Node inserted = new Node(key, value);
63             linkMostRecent(inserted);
64             index.put(key, inserted);
65         }
66         public int size() { return index.size(); }
67         public int capacity() { return capacity; }
68     }
69     // Linear MRU-first array-list model; independent of pointer manipulation.
70     public static final class Baseline {
71         private record Entry(int key, int value) {}
72         private final int capacity;
73         private final ArrayList<Entry> entries = new ArrayList<>();
74         public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
75         public OptionalInt get(int key) {
76             for (int i = 0; i < entries.size(); i++) {
77                 if (entries.get(i).key() == key) {
78                     Entry entry = entries.remove(i);
79                     entries.add(0, entry);
80                     return OptionalInt.of(entry.value());
81                 }
82             }
83             return OptionalInt.empty();
84         }
85         public void put(int key, int value) {
86             for (int i = 0; i < entries.size(); i++) {
87                 if (entries.get(i).key() == key) {
88                     entries.remove(i);
89                     entries.add(0, new Entry(key, value));
90                     return;
91                 }
92             }
93             if (capacity == 0) return;
94             if (entries.size() == capacity) entries.removeLast();
95             entries.add(0, new Entry(key, value));
96         }
97         public int size() { return entries.size(); }
98         public int capacity() { return capacity; }
99     }
100 }
101

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create private sentinels and an empty key-to-node index.
HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"initial"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":-2147483648,"value":-1}
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"insert"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":-2147483648,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":-2147483648,"value":-1}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":-2147483648,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]}]
operationIndex
0
operation
{"type":"put","key":-2147483648,"value":-1}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":-2147483648,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]}]
operationIndex
1
operation
{"type":"get","key":-2147483648}
Find the exact indexed resident node.
The map locates a node directly; no list scan is needed.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"hit"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":-2147483648,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]}]
operationIndex
1
operation
{"type":"get","key":-2147483648}
nodeId
"N0"
Detach this same resident node before promotion.
Private transient state: the map still names the detached node. Its links are null and it awaits reattachment; other resident order is unchanged. The public bijection is restored before return.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"detach"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"detached"}]
lookup
[{"key":-2147483648,"node":"N0"}]
order
[]
pending
"N0"
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]}]
operationIndex
1
operation
{"type":"get","key":-2147483648}
nodeId
"N0"
Reattach the existing node immediately after HEAD.
The original node identity and indexed key remain unchanged. A most-recent hit may pass through a temporarily empty list at capacity one.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"promote"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":-2147483648,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]}]
operationIndex
1
operation
{"type":"get","key":-2147483648}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":-2147483648,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,-1]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]}]
operationIndex
1
operation
{"type":"get","key":-2147483648}
outcome
-1
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":-2147483648,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,-1]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]}]
operationIndex
2
operation
{"type":"put","key":2147483647,"value":-2147483648}
Remove the least-recent node from both representations.
TAIL.previous identified the oldest resident. The retired card is historical teaching data; Java does not retain a list of evicted nodes. Its own links are cleared.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"evict"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"}]
lookup
[]
order
[]
pending
null
outcomes
[null,-1]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]}]
operationIndex
2
operation
{"type":"put","key":2147483647,"value":-2147483648}
victimId
"N0"
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"insert"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]}]
operationIndex
2
operation
{"type":"put","key":2147483647,"value":-2147483648}
nodeId
"N1"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]}]
operationIndex
2
operation
{"type":"put","key":2147483647,"value":-2147483648}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]}]
operationIndex
3
operation
{"type":"get","key":-2147483648}
A missing key has no effect on recency.
An empty OptionalInt is distinct from a stored −1. No node is allocated, removed or promoted.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"miss"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]}]
operationIndex
3
operation
{"type":"get","key":-2147483648}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null,null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]}]
operationIndex
3
operation
{"type":"get","key":-2147483648}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null,null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]}]
operationIndex
4
operation
{"type":"get","key":2147483647}
Find the exact indexed resident node.
The map locates a node directly; no list scan is needed.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"hit"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null,null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]}]
operationIndex
4
operation
{"type":"get","key":2147483647}
nodeId
"N1"
Detach this same resident node before promotion.
Private transient state: the map still names the detached node. Its links are null and it awaits reattachment; other resident order is unchanged. The public bijection is restored before return.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"detach"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":null,"next":null,"status":"detached"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
[]
pending
"N1"
outcomes
[null,-1,null,null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]}]
operationIndex
4
operation
{"type":"get","key":2147483647}
nodeId
"N1"
Reattach the existing node immediately after HEAD.
The original node identity and indexed key remain unchanged. A most-recent hit may pass through a temporarily empty list at capacity one.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"promote"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null,null]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]}]
operationIndex
4
operation
{"type":"get","key":2147483647}
nodeId
"N1"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null,null,-2147483648]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]},{"operationIndex":4,"keysMRU":[2147483647]}]
operationIndex
4
operation
{"type":"get","key":2147483647}
outcome
-2147483648
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null,null,-2147483648]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]},{"operationIndex":4,"keysMRU":[2147483647]}]
operationIndex
5
operation
{"type":"size"}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null,null,-2147483648,1]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]},{"operationIndex":4,"keysMRU":[2147483647]},{"operationIndex":5,"keysMRU":[2147483647]}]
operationIndex
5
operation
{"type":"size"}
outcome
1
The finite operation sequence is complete.
Outcome order matches call order. Histories, sorted map cards and retired node identities explain state but are not Java cache allocations.
input
{"capacity":1,"ops":[{"type":"put","key":-2147483648,"value":-1},{"type":"get","key":-2147483648},{"type":"put","key":2147483647,"value":-2147483648},{"type":"get","key":-2147483648},{"type":"get","key":2147483647},{"type":"size"}]}
phase
"complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":-2147483648,"value":-1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2147483647,"value":-2147483648,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2147483647,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,-1,null,null,-2147483648,1]
history
[{"operationIndex":0,"keysMRU":[-2147483648]},{"operationIndex":1,"keysMRU":[-2147483648]},{"operationIndex":2,"keysMRU":[2147483647]},{"operationIndex":3,"keysMRU":[2147483647]},{"operationIndex":4,"keysMRU":[2147483647]},{"operationIndex":5,"keysMRU":[2147483647]}]
Return the documented operation outcomes or constructor failure.
A stateful cache returns one value per get/metadata call and void for puts. It does not return its private list or node references.
result
[null,-1,null,null,-2147483648,1]

Most-recent hits and reinsertion after eviction

Input: {"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]} · Operation outcomes in call order / constructor failure: [null,1,1,null,null,3]

Step 1 of 29: Create private sentinels and an empty key-to-node index.

HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.

LRU Cache — exact key lookup and reciprocal recency links

Phase: initial. Fixed capacity: 1.

Indexed residents: 0. Linked real nodes: 0. HEAD.next is most recent; TAIL.previous is least recent. Sentinel identities have no cache key.

MRU → LRU order of currently linked real nodes

Empty.

Key → exact node index — sorted display copy, not HashMap iteration order

Empty.

Sentinels and live or pending node identities

HEAD — sentinelprevious → nullnext → TAILsentinel
TAIL — sentinelprevious → HEADnext → nullsentinel

Completed outcomes — decoded by original operation

Empty.

MRU key order after each completed operation — teaching history

Empty.

Pointer work is constant; map costs are expected/amortized. Calls must be serialized because hits mutate recency. Histories and sorted index cards are excluded from cache workspace.

State after this step
Variable	Value
input	`{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}`
phase	`"initial"`
capacity	`1`
nodes	`[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]`
lookup	`[]`
order	`[]`
pending	`null`
outcomes	`[]`
history	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.OptionalInt;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validateCapacity(int capacity) {
 9         if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
10     }
11     public static final class LRUCache {
12         private static final class Node {
13             final int key;
14             int value;
15             Node previous, next;
16             Node(int key, int value) { this.key = key; this.value = value; }
17         }
18         private final int capacity;
19         private final Map<Integer, Node> index = new HashMap<>();
20         private final Node head = new Node(0, 0), tail = new Node(0, 0);
21         public LRUCache(int capacity) {
22             validateCapacity(capacity);
23             this.capacity = capacity;
24             head.next = tail;
25             tail.previous = head;
26         }
27         private void unlink(Node node) {
28             node.previous.next = node.next;
29             node.next.previous = node.previous;
30             node.previous = null;
31             node.next = null;
32         }
33         private void linkMostRecent(Node node) {
34             node.previous = head;
35             node.next = head.next;
36             head.next.previous = node;
37             head.next = node;
38         }
39         private void touch(Node node) {
40             unlink(node);
41             linkMostRecent(node);
42         }
43         public OptionalInt get(int key) {
44             Node node = index.get(key);
45             if (node == null) return OptionalInt.empty();
46             touch(node);
47             return OptionalInt.of(node.value);
48         }
49         public void put(int key, int value) {
50             Node node = index.get(key);
51             if (node != null) {
52                 node.value = value;
53                 touch(node);
54                 return;
55             }
56             if (capacity == 0) return;
57             if (index.size() == capacity) {
58                 Node victim = tail.previous;
59                 unlink(victim);
60                 index.remove(victim.key);
61             }
62             Node inserted = new Node(key, value);
63             linkMostRecent(inserted);
64             index.put(key, inserted);
65         }
66         public int size() { return index.size(); }
67         public int capacity() { return capacity; }
68     }
69     // Linear MRU-first array-list model; independent of pointer manipulation.
70     public static final class Baseline {
71         private record Entry(int key, int value) {}
72         private final int capacity;
73         private final ArrayList<Entry> entries = new ArrayList<>();
74         public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
75         public OptionalInt get(int key) {
76             for (int i = 0; i < entries.size(); i++) {
77                 if (entries.get(i).key() == key) {
78                     Entry entry = entries.remove(i);
79                     entries.add(0, entry);
80                     return OptionalInt.of(entry.value());
81                 }
82             }
83             return OptionalInt.empty();
84         }
85         public void put(int key, int value) {
86             for (int i = 0; i < entries.size(); i++) {
87                 if (entries.get(i).key() == key) {
88                     entries.remove(i);
89                     entries.add(0, new Entry(key, value));
90                     return;
91                 }
92             }
93             if (capacity == 0) return;
94             if (entries.size() == capacity) entries.removeLast();
95             entries.add(0, new Entry(key, value));
96         }
97         public int size() { return entries.size(); }
98         public int capacity() { return capacity; }
99     }
100 }
101

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create private sentinels and an empty key-to-node index.
HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"initial"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":1,"value":1}
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"insert"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":1,"value":1}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
0
operation
{"type":"put","key":1,"value":1}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"get","key":1}
Find the exact indexed resident node.
The map locates a node directly; no list scan is needed.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"hit"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"get","key":1}
nodeId
"N0"
Detach this same resident node before promotion.
Private transient state: the map still names the detached node. Its links are null and it awaits reattachment; other resident order is unchanged. The public bijection is restored before return.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"detach"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"detached"}]
lookup
[{"key":1,"node":"N0"}]
order
[]
pending
"N0"
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"get","key":1}
nodeId
"N0"
Reattach the existing node immediately after HEAD.
The original node identity and indexed key remain unchanged. A most-recent hit may pass through a temporarily empty list at capacity one.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"promote"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"get","key":1}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"get","key":1}
outcome
1
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]}]
operationIndex
2
operation
{"type":"get","key":1}
Find the exact indexed resident node.
The map locates a node directly; no list scan is needed.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"hit"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]}]
operationIndex
2
operation
{"type":"get","key":1}
nodeId
"N0"
Detach this same resident node before promotion.
Private transient state: the map still names the detached node. Its links are null and it awaits reattachment; other resident order is unchanged. The public bijection is restored before return.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"detach"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"detached"}]
lookup
[{"key":1,"node":"N0"}]
order
[]
pending
"N0"
outcomes
[null,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]}]
operationIndex
2
operation
{"type":"get","key":1}
nodeId
"N0"
Reattach the existing node immediately after HEAD.
The original node identity and indexed key remain unchanged. A most-recent hit may pass through a temporarily empty list at capacity one.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"promote"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]}]
operationIndex
2
operation
{"type":"get","key":1}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,1,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]}]
operationIndex
2
operation
{"type":"get","key":1}
outcome
1
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null,1,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]}]
operationIndex
3
operation
{"type":"put","key":2,"value":2}
Remove the least-recent node from both representations.
TAIL.previous identified the oldest resident. The retired card is historical teaching data; Java does not retain a list of evicted nodes. Its own links are cleared.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"evict"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"}]
lookup
[]
order
[]
pending
null
outcomes
[null,1,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]}]
operationIndex
3
operation
{"type":"put","key":2,"value":2}
victimId
"N0"
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"insert"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,1,1]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]}]
operationIndex
3
operation
{"type":"put","key":2,"value":2}
nodeId
"N1"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,1,1,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]}]
operationIndex
3
operation
{"type":"put","key":2,"value":2}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N1","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":2,"node":"N1"}]
order
["N1"]
pending
null
outcomes
[null,1,1,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]}]
operationIndex
4
operation
{"type":"put","key":1,"value":3}
Remove the least-recent node from both representations.
TAIL.previous identified the oldest resident. The retired card is historical teaching data; Java does not retain a list of evicted nodes. Its own links are cleared.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"evict"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"}]
lookup
[]
order
[]
pending
null
outcomes
[null,1,1,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]}]
operationIndex
4
operation
{"type":"put","key":1,"value":3}
victimId
"N1"
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"insert"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":1,"value":3,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N2"}]
order
["N2"]
pending
null
outcomes
[null,1,1,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]}]
operationIndex
4
operation
{"type":"put","key":1,"value":3}
nodeId
"N2"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":1,"value":3,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N2"}]
order
["N2"]
pending
null
outcomes
[null,1,1,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]},{"operationIndex":4,"keysMRU":[1]}]
operationIndex
4
operation
{"type":"put","key":1,"value":3}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":1,"value":3,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N2"}]
order
["N2"]
pending
null
outcomes
[null,1,1,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]},{"operationIndex":4,"keysMRU":[1]}]
operationIndex
5
operation
{"type":"get","key":1}
Find the exact indexed resident node.
The map locates a node directly; no list scan is needed.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"hit"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":1,"value":3,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N2"}]
order
["N2"]
pending
null
outcomes
[null,1,1,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]},{"operationIndex":4,"keysMRU":[1]}]
operationIndex
5
operation
{"type":"get","key":1}
nodeId
"N2"
Detach this same resident node before promotion.
Private transient state: the map still names the detached node. Its links are null and it awaits reattachment; other resident order is unchanged. The public bijection is restored before return.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"detach"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":1,"value":3,"previous":null,"next":null,"status":"detached"}]
lookup
[{"key":1,"node":"N2"}]
order
[]
pending
"N2"
outcomes
[null,1,1,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]},{"operationIndex":4,"keysMRU":[1]}]
operationIndex
5
operation
{"type":"get","key":1}
nodeId
"N2"
Reattach the existing node immediately after HEAD.
The original node identity and indexed key remain unchanged. A most-recent hit may pass through a temporarily empty list at capacity one.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"promote"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":1,"value":3,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N2"}]
order
["N2"]
pending
null
outcomes
[null,1,1,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]},{"operationIndex":4,"keysMRU":[1]}]
operationIndex
5
operation
{"type":"get","key":1}
nodeId
"N2"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"operation-complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":1,"value":3,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N2"}]
order
["N2"]
pending
null
outcomes
[null,1,1,null,null,3]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]},{"operationIndex":4,"keysMRU":[1]},{"operationIndex":5,"keysMRU":[1]}]
operationIndex
5
operation
{"type":"get","key":1}
outcome
3
The finite operation sequence is complete.
Outcome order matches call order. Histories, sorted map cards and retired node identities explain state but are not Java cache allocations.
input
{"capacity":1,"ops":[{"type":"put","key":1,"value":1},{"type":"get","key":1},{"type":"get","key":1},{"type":"put","key":2,"value":2},{"type":"put","key":1,"value":3},{"type":"get","key":1}]}
phase
"complete"
capacity
1
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N2","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N2","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":null,"next":null,"status":"evicted"},{"id":"N1","key":2,"value":2,"previous":null,"next":null,"status":"evicted"},{"id":"N2","key":1,"value":3,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N2"}]
order
["N2"]
pending
null
outcomes
[null,1,1,null,null,3]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[1]},{"operationIndex":2,"keysMRU":[1]},{"operationIndex":3,"keysMRU":[2]},{"operationIndex":4,"keysMRU":[1]},{"operationIndex":5,"keysMRU":[1]}]
Return the documented operation outcomes or constructor failure.
A stateful cache returns one value per get/metadata call and void for puts. It does not return its private list or node references.
result
[null,1,1,null,null,3]

A missing read and size leave order unchanged

Input: {"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]} · Operation outcomes in call order / constructor failure: [null,null,null,2]

Step 1 of 14: Create private sentinels and an empty key-to-node index.

HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.

LRU Cache — exact key lookup and reciprocal recency links

Phase: initial. Fixed capacity: 2.

Indexed residents: 0. Linked real nodes: 0. HEAD.next is most recent; TAIL.previous is least recent. Sentinel identities have no cache key.

MRU → LRU order of currently linked real nodes

Empty.

Key → exact node index — sorted display copy, not HashMap iteration order

Empty.

Sentinels and live or pending node identities

HEAD — sentinelprevious → nullnext → TAILsentinel
TAIL — sentinelprevious → HEADnext → nullsentinel

Completed outcomes — decoded by original operation

Empty.

MRU key order after each completed operation — teaching history

Empty.

Pointer work is constant; map costs are expected/amortized. Calls must be serialized because hits mutate recency. Histories and sorted index cards are excluded from cache workspace.

State after this step
Variable	Value
input	`{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}`
phase	`"initial"`
capacity	`2`
nodes	`[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]`
lookup	`[]`
order	`[]`
pending	`null`
outcomes	`[]`
history	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.OptionalInt;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validateCapacity(int capacity) {
 9         if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
10     }
11     public static final class LRUCache {
12         private static final class Node {
13             final int key;
14             int value;
15             Node previous, next;
16             Node(int key, int value) { this.key = key; this.value = value; }
17         }
18         private final int capacity;
19         private final Map<Integer, Node> index = new HashMap<>();
20         private final Node head = new Node(0, 0), tail = new Node(0, 0);
21         public LRUCache(int capacity) {
22             validateCapacity(capacity);
23             this.capacity = capacity;
24             head.next = tail;
25             tail.previous = head;
26         }
27         private void unlink(Node node) {
28             node.previous.next = node.next;
29             node.next.previous = node.previous;
30             node.previous = null;
31             node.next = null;
32         }
33         private void linkMostRecent(Node node) {
34             node.previous = head;
35             node.next = head.next;
36             head.next.previous = node;
37             head.next = node;
38         }
39         private void touch(Node node) {
40             unlink(node);
41             linkMostRecent(node);
42         }
43         public OptionalInt get(int key) {
44             Node node = index.get(key);
45             if (node == null) return OptionalInt.empty();
46             touch(node);
47             return OptionalInt.of(node.value);
48         }
49         public void put(int key, int value) {
50             Node node = index.get(key);
51             if (node != null) {
52                 node.value = value;
53                 touch(node);
54                 return;
55             }
56             if (capacity == 0) return;
57             if (index.size() == capacity) {
58                 Node victim = tail.previous;
59                 unlink(victim);
60                 index.remove(victim.key);
61             }
62             Node inserted = new Node(key, value);
63             linkMostRecent(inserted);
64             index.put(key, inserted);
65         }
66         public int size() { return index.size(); }
67         public int capacity() { return capacity; }
68     }
69     // Linear MRU-first array-list model; independent of pointer manipulation.
70     public static final class Baseline {
71         private record Entry(int key, int value) {}
72         private final int capacity;
73         private final ArrayList<Entry> entries = new ArrayList<>();
74         public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
75         public OptionalInt get(int key) {
76             for (int i = 0; i < entries.size(); i++) {
77                 if (entries.get(i).key() == key) {
78                     Entry entry = entries.remove(i);
79                     entries.add(0, entry);
80                     return OptionalInt.of(entry.value());
81                 }
82             }
83             return OptionalInt.empty();
84         }
85         public void put(int key, int value) {
86             for (int i = 0; i < entries.size(); i++) {
87                 if (entries.get(i).key() == key) {
88                     entries.remove(i);
89                     entries.add(0, new Entry(key, value));
90                     return;
91                 }
92             }
93             if (capacity == 0) return;
94             if (entries.size() == capacity) entries.removeLast();
95             entries.add(0, new Entry(key, value));
96         }
97         public int size() { return entries.size(); }
98         public int capacity() { return capacity; }
99     }
100 }
101

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create private sentinels and an empty key-to-node index.
HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"initial"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":1,"value":1}
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"insert"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[]
history
[]
operationIndex
0
operation
{"type":"put","key":1,"value":1}
nodeId
"N0"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
0
operation
{"type":"put","key":1,"value":1}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N0","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"HEAD","next":"TAIL","status":"linked"}]
lookup
[{"key":1,"node":"N0"}]
order
["N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":2}
Link and index one fresh most-recent node.
Eviction preceded insertion when necessary. A previously evicted key receives a fresh identity, while an existing-key update would reuse its node.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"insert"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null]
history
[{"operationIndex":0,"keysMRU":[1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":2}
nodeId
"N1"
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
1
operation
{"type":"put","key":2,"value":2}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"get","key":99}
A missing key has no effect on recency.
An empty OptionalInt is distinct from a stored −1. No node is allocated, removed or promoted.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"miss"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"get","key":99}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[2,1]}]
operationIndex
2
operation
{"type":"get","key":99}
outcome
null
Begin a serialized public operation.
The stable boundary has one indexed node per resident, reciprocal links, correct recency order and size within capacity.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"operation"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null,null]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[2,1]}]
operationIndex
3
operation
{"type":"size"}
Return this operation outcome with stable representation invariants restored.
The map/list bijection holds again and the order is MRU→LRU. Put outcomes are void/null; get null means OptionalInt.empty(); a stored signed value remains a hit. Metadata reads do not promote.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"operation-complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null,null,2]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[2,1]},{"operationIndex":3,"keysMRU":[2,1]}]
operationIndex
3
operation
{"type":"size"}
outcome
2
The finite operation sequence is complete.
Outcome order matches call order. Histories, sorted map cards and retired node identities explain state but are not Java cache allocations.
input
{"capacity":2,"ops":[{"type":"put","key":1,"value":1},{"type":"put","key":2,"value":2},{"type":"get","key":99},{"type":"size"}]}
phase
"complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"N1","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"N0","next":null,"status":"sentinel"},{"id":"N0","key":1,"value":1,"previous":"N1","next":"TAIL","status":"linked"},{"id":"N1","key":2,"value":2,"previous":"HEAD","next":"N0","status":"linked"}]
lookup
[{"key":1,"node":"N0"},{"key":2,"node":"N1"}]
order
["N1","N0"]
pending
null
outcomes
[null,null,null,2]
history
[{"operationIndex":0,"keysMRU":[1]},{"operationIndex":1,"keysMRU":[2,1]},{"operationIndex":2,"keysMRU":[2,1]},{"operationIndex":3,"keysMRU":[2,1]}]
Return the documented operation outcomes or constructor failure.
A stateful cache returns one value per get/metadata call and void for puts. It does not return its private list or node references.
result
[null,null,null,2]

Invalid construction has no operation results

Input: {"capacity":-1,"ops":[]} · Operation outcomes in call order / constructor failure: "IllegalArgumentException"

Step 1 of 2: Reject unsupported capacity before any cache operation.

No resident state or operation outcome exists for failed construction.

LRU Cache — exact key lookup and reciprocal recency links

Phase: reject. Fixed capacity: -1.

Capacity must be in 0..100000. Construction throws IllegalArgumentException; no operations or resident state exist.

State after this step
Variable	Value
input	`{"capacity":-1,"ops":[]}`
phase	`"reject"`
capacity	`-1`
nodes	`[]`
lookup	`[]`
order	`[]`
pending	`null`
outcomes	`[]`
history	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.OptionalInt;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validateCapacity(int capacity) {
 9         if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
10     }
11     public static final class LRUCache {
12         private static final class Node {
13             final int key;
14             int value;
15             Node previous, next;
16             Node(int key, int value) { this.key = key; this.value = value; }
17         }
18         private final int capacity;
19         private final Map<Integer, Node> index = new HashMap<>();
20         private final Node head = new Node(0, 0), tail = new Node(0, 0);
21         public LRUCache(int capacity) {
22             validateCapacity(capacity);
23             this.capacity = capacity;
24             head.next = tail;
25             tail.previous = head;
26         }
27         private void unlink(Node node) {
28             node.previous.next = node.next;
29             node.next.previous = node.previous;
30             node.previous = null;
31             node.next = null;
32         }
33         private void linkMostRecent(Node node) {
34             node.previous = head;
35             node.next = head.next;
36             head.next.previous = node;
37             head.next = node;
38         }
39         private void touch(Node node) {
40             unlink(node);
41             linkMostRecent(node);
42         }
43         public OptionalInt get(int key) {
44             Node node = index.get(key);
45             if (node == null) return OptionalInt.empty();
46             touch(node);
47             return OptionalInt.of(node.value);
48         }
49         public void put(int key, int value) {
50             Node node = index.get(key);
51             if (node != null) {
52                 node.value = value;
53                 touch(node);
54                 return;
55             }
56             if (capacity == 0) return;
57             if (index.size() == capacity) {
58                 Node victim = tail.previous;
59                 unlink(victim);
60                 index.remove(victim.key);
61             }
62             Node inserted = new Node(key, value);
63             linkMostRecent(inserted);
64             index.put(key, inserted);
65         }
66         public int size() { return index.size(); }
67         public int capacity() { return capacity; }
68     }
69     // Linear MRU-first array-list model; independent of pointer manipulation.
70     public static final class Baseline {
71         private record Entry(int key, int value) {}
72         private final int capacity;
73         private final ArrayList<Entry> entries = new ArrayList<>();
74         public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
75         public OptionalInt get(int key) {
76             for (int i = 0; i < entries.size(); i++) {
77                 if (entries.get(i).key() == key) {
78                     Entry entry = entries.remove(i);
79                     entries.add(0, entry);
80                     return OptionalInt.of(entry.value());
81                 }
82             }
83             return OptionalInt.empty();
84         }
85         public void put(int key, int value) {
86             for (int i = 0; i < entries.size(); i++) {
87                 if (entries.get(i).key() == key) {
88                     entries.remove(i);
89                     entries.add(0, new Entry(key, value));
90                     return;
91                 }
92             }
93             if (capacity == 0) return;
94             if (entries.size() == capacity) entries.removeLast();
95             entries.add(0, new Entry(key, value));
96         }
97         public int size() { return entries.size(); }
98         public int capacity() { return capacity; }
99     }
100 }
101

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Reject unsupported capacity before any cache operation.
No resident state or operation outcome exists for failed construction.
input
{"capacity":-1,"ops":[]}
phase
"reject"
capacity
-1
nodes
[]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
Return the documented operation outcomes or constructor failure.
A stateful cache returns one value per get/metadata call and void for puts. It does not return its private list or node references.
result
"IllegalArgumentException"

Empty positive-capacity cache

Input: {"capacity":2,"ops":[]} · Operation outcomes in call order / constructor failure: []

Step 1 of 3: Create private sentinels and an empty key-to-node index.

HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.

LRU Cache — exact key lookup and reciprocal recency links

Phase: initial. Fixed capacity: 2.

Indexed residents: 0. Linked real nodes: 0. HEAD.next is most recent; TAIL.previous is least recent. Sentinel identities have no cache key.

MRU → LRU order of currently linked real nodes

Empty.

Key → exact node index — sorted display copy, not HashMap iteration order

Empty.

Sentinels and live or pending node identities

HEAD — sentinelprevious → nullnext → TAILsentinel
TAIL — sentinelprevious → HEADnext → nullsentinel

Completed outcomes — decoded by original operation

Empty.

MRU key order after each completed operation — teaching history

Empty.

Pointer work is constant; map costs are expected/amortized. Calls must be serialized because hits mutate recency. Histories and sorted index cards are excluded from cache workspace.

State after this step
Variable	Value
input	`{"capacity":2,"ops":[]}`
phase	`"initial"`
capacity	`2`
nodes	`[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]`
lookup	`[]`
order	`[]`
pending	`null`
outcomes	`[]`
history	`[]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.OptionalInt;
 5 
 6 public final class Solution {
 7     private Solution() {}
 8     private static void validateCapacity(int capacity) {
 9         if (capacity < 0 || capacity > 100_000) throw new IllegalArgumentException("capacity must be 0..100000");
10     }
11     public static final class LRUCache {
12         private static final class Node {
13             final int key;
14             int value;
15             Node previous, next;
16             Node(int key, int value) { this.key = key; this.value = value; }
17         }
18         private final int capacity;
19         private final Map<Integer, Node> index = new HashMap<>();
20         private final Node head = new Node(0, 0), tail = new Node(0, 0);
21         public LRUCache(int capacity) {
22             validateCapacity(capacity);
23             this.capacity = capacity;
24             head.next = tail;
25             tail.previous = head;
26         }
27         private void unlink(Node node) {
28             node.previous.next = node.next;
29             node.next.previous = node.previous;
30             node.previous = null;
31             node.next = null;
32         }
33         private void linkMostRecent(Node node) {
34             node.previous = head;
35             node.next = head.next;
36             head.next.previous = node;
37             head.next = node;
38         }
39         private void touch(Node node) {
40             unlink(node);
41             linkMostRecent(node);
42         }
43         public OptionalInt get(int key) {
44             Node node = index.get(key);
45             if (node == null) return OptionalInt.empty();
46             touch(node);
47             return OptionalInt.of(node.value);
48         }
49         public void put(int key, int value) {
50             Node node = index.get(key);
51             if (node != null) {
52                 node.value = value;
53                 touch(node);
54                 return;
55             }
56             if (capacity == 0) return;
57             if (index.size() == capacity) {
58                 Node victim = tail.previous;
59                 unlink(victim);
60                 index.remove(victim.key);
61             }
62             Node inserted = new Node(key, value);
63             linkMostRecent(inserted);
64             index.put(key, inserted);
65         }
66         public int size() { return index.size(); }
67         public int capacity() { return capacity; }
68     }
69     // Linear MRU-first array-list model; independent of pointer manipulation.
70     public static final class Baseline {
71         private record Entry(int key, int value) {}
72         private final int capacity;
73         private final ArrayList<Entry> entries = new ArrayList<>();
74         public Baseline(int capacity) { validateCapacity(capacity); this.capacity = capacity; }
75         public OptionalInt get(int key) {
76             for (int i = 0; i < entries.size(); i++) {
77                 if (entries.get(i).key() == key) {
78                     Entry entry = entries.remove(i);
79                     entries.add(0, entry);
80                     return OptionalInt.of(entry.value());
81                 }
82             }
83             return OptionalInt.empty();
84         }
85         public void put(int key, int value) {
86             for (int i = 0; i < entries.size(); i++) {
87                 if (entries.get(i).key() == key) {
88                     entries.remove(i);
89                     entries.add(0, new Entry(key, value));
90                     return;
91                 }
92             }
93             if (capacity == 0) return;
94             if (entries.size() == capacity) entries.removeLast();
95             entries.add(0, new Entry(key, value));
96         }
97         public int size() { return entries.size(); }
98         public int capacity() { return capacity; }
99     }
100 }
101

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Create private sentinels and an empty key-to-node index.
HEAD.next is MRU; TAIL.previous is LRU. Sentinel dummy keys are not cache entries. Empty links agree in both directions.
input
{"capacity":2,"ops":[]}
phase
"initial"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
The finite operation sequence is complete.
Outcome order matches call order. Histories, sorted map cards and retired node identities explain state but are not Java cache allocations.
input
{"capacity":2,"ops":[]}
phase
"complete"
capacity
2
nodes
[{"id":"HEAD","key":null,"value":null,"previous":null,"next":"TAIL","status":"sentinel"},{"id":"TAIL","key":null,"value":null,"previous":"HEAD","next":null,"status":"sentinel"}]
lookup
[]
order
[]
pending
null
outcomes
[]
history
[]
Return the documented operation outcomes or constructor failure.
A stateful cache returns one value per get/metadata call and void for puts. It does not return its private list or node references.
result
[]

Test the contract

Input: capacity=1; ops=[put(7,-1),get(7),get(8)]
Output: [null,-1,null]
Stored −1 is a hit; missing eight yields OptionalInt.empty().
Input: capacity=1; ops=[put(1,1),get(1),get(1),put(2,2),get(1)]
Output: [null,1,1,null,null]
Repeated most-recent hits preserve one node; inserting two then evicts one.
Input: capacity=2; ops=[put(1,1),put(2,2),get(99),size(),put(3,3),get(1)]
Output: [null,null,null,2,null,null]
Miss and size do not rescue the oldest key.
Input: capacity=1; ops=[put(-2147483648,2147483647),get(-2147483648)]
Output: [null,2147483647]
Full signed-int key/value range.
Input: capacity=2; ops=[]
Output: []
Construction alone leaves an empty valid cache.
Input: capacity=-1; ops=[]
Output: IllegalArgumentException
Capacity is validated at construction.

Common mistakes and counterexamples

Evict on an existing-key update

Counterexample: At capacity two, put(1,10),put(2,20),put(1,99) must retain both keys and promote one.

Look up and handle existing nodes before checking fullness.

Treat a miss or metadata read as an access

Counterexample: After put(1),put(2),get(99), the next insertion must still evict one.

Promote only successful gets and every put on a stored/new key.

Remove a node from only one representation

Counterexample: An evicted node still present in the map can be found and promoted back accidentally; an unindexed list node can consume capacity forever.

Unlink the victim and remove its map entry before inserting the new resident.

Forget a backward pointer or assume nonzero capacity

Counterexample: A capacity-one promotion and capacity-zero put exercise the sentinel boundaries immediately.

Update both neighboring directions, maintain distinct sentinels, and return early for zero capacity.

Return −1 for misses while accepting every int value

Counterexample: A cache storing key seven with value −1 cannot distinguish a successful read from absence using that scalar alone.

Use OptionalInt here; a conventional −1-sentinel API needs an explicit restricted value contract or separate presence information.

Follow-ups

Use an access-ordered LinkedHashMap instead.

Java offers access-order behavior suitable for an alternate implementation. Define exactly which operations count as access and how the eldest entry is removed. It reduces manual pointer code but does not remove the need to specify capacity zero, stored-value/miss distinction, synchronization and ownership. The lesson builds the data structure directly so its invariant is visible.

Support concurrent callers.

A successful get is a write to recency links. A concurrent map alone cannot protect the list or make a map/list transition atomic. A single lock around each operation is one simple starting design; then discuss contention, visibility and whether the eviction policy may become approximate under sharding.

Add expiry, weights, or resizing.

A key-count capacity does not measure memory weight or deadlines. Expiry needs a time source and removal policy; weighted puts may evict several residents; resizing can require repeated evictions. Specify whether expired gets count as hits and analyze extra work rather than keeping the original constant-work claim unchanged.

Compare LRU with LFU or scan-resistant policies.

LRU retains only order of recent access, not long-term frequency. A sequential scan can evict a previously hot set. Frequency buckets, admission filters, or segmented recency need different state and proofs. Do not infer frequency from how far a key sits from the front.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 274/20,000 characters

Self-review

I can state the map/list bijection, sentinel link, capacity, and recency invariants.I can trace get hit/miss, existing update, insertion, eviction, capacity zero and capacity one without losing node identity.I can distinguish expected map costs from constant pointer work, stable public invariants from private detach steps, and metadata reads from recency accesses.I can explain OptionalInt misses, serialized ownership, and why a concurrent map alone is insufficient.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-18 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.