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.
LRU Cache: A hit moves the node to the front
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.
Cost
- Access
- O(n)
- Search
- O(n)
- Insert at ends
- O(1)
- Delete given node
- O(1)
- Space
- O(n)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
LRU Cache covers these too, in the same run.