LRU Cache Eviction Algorithm: Principles and Implementation

Problem Description
LRU (Least Recently Used) is a widely used cache eviction algorithm. Its core principle is "evict the least recently used data." When cache space is insufficient, LRU prioritizes removing the data items that have not been accessed for the longest time. The algorithm needs to efficiently support data insertion, lookup, and deletion operations, with time complexity ideally close to O(1).

Core Principles

1. Access Order Determines Priority: Data accessed recently has a higher probability of being accessed again in the future.
2. Eviction Policy: When the cache is full, evict the node in the linked list that has been unused for the longest time (head or tail depends on design).
3. Data Structure Requirements: Need fast data location (hash table) and maintenance of access order (doubly linked list).

Algorithm Implementation Steps

Step 1: Design Node Structure
Each cache node consists of three parts:

class Node:
    def __init__(self, key, value):
        self.key = key      # For hash table lookup
        self.value = value  # Stored data
        self.prev = None    # Previous node
        self.next = None    # Next node

Step 2: Initialize Data Structures

• Use a hash table (dictionary) for O(1) queries.
• Use a doubly linked list with dummy head and tail sentinel nodes to maintain access order.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity        # Cache capacity
        self.cache = {}                 # Hash table: key -> Node
        # Create sentinel nodes to simplify linked list operations
        self.head = Node(0, 0)          # Most recently accessed node
        self.tail = Node(0, 0)          # Least recently used node
        self.head.next = self.tail
        self.tail.prev = self.head

Step 3: Implement Node Operation Helper Methods

• Add to Head of List (marks as newly accessed)

def _add_node(self, node):
    # Insert node after head
    node.prev = self.head
    node.next = self.head.next
    self.head.next.prev = node
    self.head.next = node

• Remove Node (delete from linked list)

def _remove_node(self, node):
    # Disconnect node links
    prev_node = node.prev
    next_node = node.next
    prev_node.next = next_node
    next_node.prev = prev_node

• Move Node to Head (called when accessing existing data)

def _move_to_head(self, node):
    self._remove_node(node)  # Remove from original position
    self._add_node(node)     # Add to head

• Pop Tail Node (evict the least recently used)

def _pop_tail(self):
    last_node = self.tail.prev  # The least recently used node
    self._remove_node(last_node)
    return last_node

Step 4: Implement Core Interfaces

• get Operation (query data)

def get(self, key):
    if key not in self.cache:
        return -1  # Cache miss
    
    node = self.cache[key]
    self._move_to_head(node)  # Update as most recently accessed
    return node.value

• put Operation (insert data)

def put(self, key, value):
    if key in self.cache:
        # Key exists, update value and promote priority
        node = self.cache[key]
        node.value = value
        self._move_to_head(node)
    else:
        # Create new node
        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add_node(new_node)
        
        # Check capacity, trigger eviction
        if len(self.cache) > self.capacity:
            last_node = self._pop_tail()
            del self.cache[last_node.key]  # Delete from hash table

Complexity Analysis

• Time Complexity: get and put operations are both O(1).
• Space Complexity: O(capacity), fixed capacity.

Practical Application Scenarios

1. Database query cache (Redis, Memcached)
2. Browser caching for recently visited pages
3. Operating system page replacement algorithms
4. API response caching in microservices architecture

Optimization Variants

• LRU-K: Considers recent K access history.
• 2Q: Uses two queues to distinguish hot data.
• LFU: Eviction policy based on access frequency.