146. LRU Cache

Problem Link

To support both get and put operations in \(O(1)\) time, we combine a hash map with a doubly linked list.

• The hash map stores key-to-node mappings, allowing direct access to cache entries in constant time.
• The doubly linked list maintains the usage order of the cache, where the least recently used (LRU) node is near the head, and the most recently used (MRU) node is near the tail.

We use two dummy nodes, lru and mru, to simplify insertion and removal. When a key is accessed or updated, its node is removed from its current position and reinserted just before the mru node, marking it as most recently used.

For the get operation,

• if the key exists, we move the corresponding node to the MRU position and return its value.
• If the key does not exist, we return -1.

For the put operation,

• if the key already exists, we remove its current node before inserting the updated one.
• After insertion, if the cache exceeds its capacity, we remove the node next to the lru dummy node, which represents the least recently used entry, and delete it from the hash map.

This design ensures constant-time operations while correctly maintaining the LRU eviction policy.

Runtime Complexity

Time: \(O(1)\) for both put and get

Space: \(O(n)\)

PythonGo

class ListNode:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.data = dict()

        self.lru, self.mru = ListNode(), ListNode()
        self.lru.next, self.mru.prev = self.mru, self.lru

    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    def insert(self, node):
        prev, nxt = self.mru.prev, self.mru
        prev.next = nxt.prev = node
        node.prev, node.next = prev, nxt

    def get(self, key: int) -> int:
        if key in self.data:
            self.remove(self.data[key])
            self.insert(self.data[key])
            return self.data[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.remove(self.data[key])

        self.data[key] = ListNode(key=key, val=value)
        self.insert(self.data[key])

        if len(self.data) > self.cap:
            lru = self.lru.next
            self.remove(lru)
            del self.data[lru.key]

type DoubleListNode struct {
    Key  int
    Val  int
    Next *DoubleListNode
    Prev *DoubleListNode
}

type LRUCache struct {
    Cap  int
    data map[int]*DoubleListNode
    MRU  *DoubleListNode
    LRU  *DoubleListNode
}

func ConstructorLRU(capacity int) LRUCache {
    obj := LRUCache{Cap: capacity,
        data: make(map[int]*DoubleListNode),
        MRU:  &DoubleListNode{Key: -1, Val: -1},
        LRU:  &DoubleListNode{Key: -1, Val: -1},
    }
    obj.LRU.Next, obj.MRU.Prev = obj.MRU, obj.LRU
    return obj
}

func (this *LRUCache) remove(node *DoubleListNode) {
    prev, next := node.Prev, node.Next
    prev.Next, next.Prev = next, prev
}

func (this *LRUCache) insert(node *DoubleListNode) {
    prev, nxt := this.MRU.Prev, this.MRU
    prev.Next = node
    nxt.Prev = node
    node.Prev, node.Next = prev, nxt
}

func (this *LRUCache) Get(key int) int {
    if node, ok := this.data[key]; ok {
        this.remove(node)
        this.insert(node)
        return node.Val
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if node, ok := this.data[key]; ok {
        this.remove(node)
    }
    node := &DoubleListNode{Key: key, Val: value}
    this.data[key] = node
    this.insert(node)
    if len(this.data) > this.Cap {
        lru := this.LRU.Next
        this.remove(lru)
        delete(this.data, lru.Key)
    }
}

---