Leetcode(Medium) 146. LRU Cache (Python)

December 4, 2022 Program

LRU Cache can be regarded as an interesting topic that I have encountered, and I feel that it is also a concept that will be used in many systems. Unfortunately, I never encountered this problem on my job yet...

Just record my solving method of problem

Problem

🔗

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Concept

🔗

The main purpose of the cache mechanism is to keep the more frequently used data and eliminate the infrequently used data, so that users can obtain the information they want more quickly when executing the program.

Use HashMap and DoubleLinkedList to implement, Each event represents the key and value of the HashMap, and the value is the node generated by DoubleLinkedList. This way you can know the actual order of the nodes.

In order to update the state of the node while calling functions get and put, two additional functions are required
def insertInToHead(self, node):
Insert this node to the first position of LinkedList (behind the head, in front of the original first node)

def removeNode(self, node):
Remove this node (connect the node of front and back nodes)

Whether it is calling functions get or put, above of two functions are used when changing the state of the node.

Detail

🔗

The initial data structure of LRUCache needs to include dummyHead and dummyTail, so as to know the most frequently used position (the one after dummyHead) and the least frequently used position (the one before dummyTail)
When calling functions put, if the final HashMap length is greater than capacity, you need to delete the value (key:value) in the HashMap first. The value of the key is the last node of the LinkedList (the node in front of dummyTail), and then delete this node.

Code

🔗

Python
class LinkListed:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.size = capacity
        self.dic = {}
        self.dummyHead = LinkListed(0, 0)
        self.dummyTail = LinkListed(0, 0)
        self.dummyHead.next = self.dummyTail
        self.dummyTail.prev = self.dummyHead.next

    def get(self, key: int) -> int:
        if key not in self.dic: return -1
        node = self.dic[key]
        self.removeNode(node)
        self.insertInToHead(node)
        return node.val
        
    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            node = self.dic[key]
            node.val = value
            self.removeNode(node)
            self.insertInToHead(node)
        else:
            node = LinkListed(key, value)
            self.dic[key] = node
            self.insertInToHead(node)
            
            if len(self.dic) > self.size:
                del self.dic[self.dummyTail.prev.key]
                self.removeNode(self.dummyTail.prev)
        
    def insertInToHead(self, node):
        node.next = self.dummyHead.next
        self.dummyHead.next.prev = node
        self.dummyHead.next = node
        node.prev = self.dummyHead
        return
        
    def removeNode(self, node):
        node.next.prev = node.prev
        node.prev.next = node.next
        return