[Python] Dict + Double-linkedlist, O(1) get and set


  • 2
    Z

    I have read the existing python solutions using Dict + deque, or ordered dict. Dict + Deque has complexity of O(1) set and O(N) get, since moving an element from middle to one end takes O(N). Ordered Dict may have O(N) complexity as well depending on its implementation. Since python does not have a built-in double linked list, I implemented my own.

    The idea behind is simple, use a Hashmap to track where the node is, O(1), and change the order of the node and access the last node exploiting Double linked list

    class ListNode(object):
        def __init__(self, key, value):
            self.key = key
            self.val = value
            self.next = None
            self.prev = None
    
    
    class LRUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.cap = capacity
            self.count = 0
            self.head = ListNode(None, 0)
            self.tail = ListNode(None, 0)
            self.head.next, self.tail.prev = self.tail, self.head
            self.table = {}
    
        def detachNode(self, node):
            node.prev.next = node.next
            node.next.prev = node.prev
            node.prev = None
            node.next = None
            self.count -= 1
    
        def attachNode(self, node):
            node.prev = self.head
            node.next = self.head.next
            node.next.prev = node
            self.head.next = node
            self.count += 1
    
        def get(self, key):
            """
            :rtype: int
            """
            if key in self.table:
                node = self.table[key]
                self.detachNode(node)
                self.attachNode(node)
                return node.val
            else:
                return -1
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            if key in self.table:
                node = self.table[key]
                self.detachNode(node)
                self.attachNode(node)
                node.val = value
            else:
                node = ListNode(key, value)
                if self.count == self.cap:
                    lastNode = self.tail.prev
                    self.table.pop(lastNode.key)
                    self.detachNode(lastNode)
                self.table[key] = node
                self.attachNode(node)

Log in to reply
 

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