[Python] Doubly linked list and dictionary. Easy to understand


  • 1

    I think this is a very typical solution. If you have any suggestions, please let me know! It is O(1) set and get.

    Each node in the list corresponds to a key-value pair in the hash table. When we insert new key-value pair into the cache, we also add a node to the front of the list. When the cache is full and we still need to add data to it, we basically remove the last element in the list, because it is least recently used. When we actually have a cache hit, we can simply bring the corresponding node to the front of the list,by removing it (constant time for doubly linked list) then prepending it to the list.

    class DLLNode:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next
        
    class DLL:
    def __init__(self):
        self.head = None
        self.tail = None
        
    def prepend(self, dllnode):
        if self.head is None:
            self.head = dllnode
            self.tail = dllnode
        else:
            self.head.prev = dllnode
            dllnode.next = self.head
            self.head = dllnode
    
    def append(self, dllnode):
        if self.head is None:
            self.head = dllnode
            self.tail = dllnode
        else:
            self.tail.next = dllnode
            dllnode.prev = self.tail
            self.tail = dllnode
            
    def remove(self, dllnode):
        """Constant time removal in DLL"""
        nextnode = dllnode.next
        prevnode = dllnode.prev
        if nextnode is None and prevnode is None:
            self.head = None
            self.tail = None
        else:
            if nextnode is not None:
                nextnode.prev = prevnode
            else:
                # We are removing the tail node
                self.tail = prevnode
                
            if prevnode is not None:
                prevnode.next = nextnode
            else:
                # We are removing the head node
                self.head = nextnode
        if dllnode != self.tail and dllnode != self.head:
            dllnode.next = None
            dllnode.prev = None
    
    class LRUCache(object):
    
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.data = {}
        self.capacity = capacity
        self.dll = DLL()
    
    def get(self, key):
        """
        :rtype: int
        """
        if key in self.data:
            self.__increasePriority(key)
            return self.data[key][0]
        else:
            return -1
        
    def set(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: nothing
        """
        if key in self.data:
            self.__increasePriority(key)
            self.data[key] = (value, self.data[key][1])
        else:
            if len(self.data) == self.capacity:
                self.__evict(key)
                
            newnode = DLLNode(key)
            self.dll.prepend(newnode)
            self.data[key] = (value, newnode)
    
    def __evict(self, key):
        lru_node = self.dll.tail
        self.dll.remove(lru_node)
        self.data.pop(lru_node.data, None)
    
    def __increasePriority(self, key):
        _, dllnode = self.data[key]
        self.dll.remove(dllnode)
        self.dll.prepend(dllnode)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.