AlgoScope

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.

Data structures, data structure, beginner
get 1 hits, value 10, moved to the front.1:103:302:20head
get 1 hits, value 10, moved to the front.1:103:302:20head

LRU Cache: A hit moves the node to the front

Decision, step 5 of 8

get 1: the map points straight at its node, value 10. It sat at position 2. Unlink it there, which its prev and next pointers make O(1), and link it back in at the head as the most recently used.

How lru cache works

Cost

Access
O(n)
Search
O(n)
Insert at ends
O(1)
Delete given node
O(1)
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

LRU Cache covers these too, in the same run.