Great question! Let’s unpack whether a singly linked list can work for an LRU cache, and the tradeoffs involved compared to the standard doubly linked list + hash map approach.

Short Answer #

Yes, you can implement an LRU cache with a singly linked list—but you’ll sacrifice the O(1) time complexity that makes LRU caches useful for high-performance scenarios. The standard doubly linked list approach is preferred because it keeps all core operations (get, put, evict) in constant time.

The Tradeoffs of Using a Singly Linked List #

First, let’s recap the core operations an LRU cache needs to handle efficiently:

• get(key): Retrieve a value and mark the key as "recently used" (move it to the front of the usage order)
• put(key, value): Insert a new key-value pair; if the cache is full, evict the "least recently used" key (usually the tail of the list) before inserting the new one
• Eviction: Remove the least recently used node quickly

The Problem with Singly Linked Lists #

Singly linked lists only let you traverse forward from a node—you can’t access a node’s predecessor without traversing from the head. This breaks the O(1) guarantee for two critical operations:

1. Moving a node to the front: To remove a node from its current position, you need to find its predecessor. Without a direct reference, you have to traverse the list from the head until you find it, which takes O(n) time.
2. Evicting the tail node: To delete the least recently used node (the tail), you need to find the second-to-last node to update its next pointer. Again, this requires traversing the entire list, taking O(n) time.

A Workaround (That Still Has Flaws) #

You could tweak the design to store references to each node’s predecessor in your hash map (instead of the node itself). Here’s a simplified Python example to illustrate:

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.head = None
        # Maps each key to its predecessor node (None if the node is the head)
        self.key_to_prev = {}

    def get(self, key):
        if key not in self.key_to_prev:
            return -1
        
        prev_node = self.key_to_prev[key]
        target_node = prev_node.next if prev_node else self.head

        # If node is already the head, no need to move it
        if not prev_node:
            return target_node.value

        # Remove target node from its current position
        prev_node.next = target_node.next
        # Update the next node's predecessor entry if it exists
        if target_node.next:
            self.key_to_prev[target_node.next.key] = prev_node

        # Move target node to the head of the list
        target_node.next = self.head
        self.head = target_node
        # Update the target node's predecessor entry to None
        self.key_to_prev[key] = None
        # Update the old head's predecessor entry to the target node
        if target_node.next:
            self.key_to_prev[target_node.next.key] = target_node

        return target_node.value

    def put(self, key, value):
        if key in self.key_to_prev:
            # Update the value and mark as recently used
            prev_node = self.key_to_prev[key]
            target_node = prev_node.next if prev_node else self.head
            target_node.value = value
            self.get(key)  # Reuse get logic to move to head
            return

        # Create new node and add to head
        new_node = Node(key, value)
        new_node.next = self.head
        self.head = new_node
        self.key_to_prev[key] = None
        if new_node.next:
            self.key_to_prev[new_node.next.key] = new_node

        # Evict least recently used node if capacity is exceeded
        if len(self.key_to_prev) > self.capacity:
            # PROBLEM: We have to traverse the entire list to find the tail
            current = self.head
            prev_tail = None
            while current.next:
                prev_tail = current
                current = current.next
            
            # Delete the tail node
            del self.key_to_prev[current.key]
            if prev_tail:
                prev_tail.next = None

Even with this workaround, the eviction step (deleting the tail) still requires an O(n) traversal. There’s no way around this with a pure singly linked list—you can’t track the tail’s predecessor without extra overhead that defeats the purpose.

Why Doubly Linked Lists Are the Standard #

Doubly linked lists solve this problem by giving each node a reference to both its predecessor and successor. When combined with a hash map that stores references to each node, you can:

• Find any node in O(1) time via the hash map
• Remove or move any node in O(1) time using its predecessor/successor references
• Evict the tail node in O(1) time (since you track the tail directly)

All core operations stay in constant time, which is why this approach is universally recommended for LRU caches.

内容的提问来源于stack exchange，提问作者asndonsadoasndo231213