Doubly Linked List
Each node points to both neighbours, so a node can be unlinked in O(1) given only the node, as the LRU cache's moves rely on.
Decision · step 2 of 8LRU Cache: A hit moves the node to the front
put 1 10: a new key with room to spare. It becomes the head, the most recently used.
What you will see
Two arrows per link; deleting a node redirects both neighbours' pointers.
Cost
| access | O(n) |
|---|---|
| search | O(n) |
| insert at ends | O(1) |
| delete given node | O(1) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.