Cache

LRU

Least Recently Used

Algorithm	Complexity
Space	$O(n)$
Get	$O(1)$
Put	$O(1)$

1. Implemented by Built-in Structures

2. Implemented by hash table and doubly linked list

LFU

Least Frequently Used

Algorithm	Complexity
Space	$O(n)$
Get	$O(1)$
Put	$O(1)$

Tests