We covered 2 true LRU implementations: square matrix implementation and counter based implementation in previous post. We will discuss 2 more true LRU implementations in this post.
In the following discussion, we assume the number of ways in a cache set is N.
Linked List Implementation
Linked list is probably the most straightforward LRU implementation. Nodes are linked from head to tail. Head points to the most recently used item, while tail points to the least recently used item.
Upon a cache access, the corresponding node “jumps” to the head, and the previous head becomes the next node of new head.