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

  • 2

    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]
                return node.val
                return -1
        def set(self, key, value):
            :type key: int
            :type value: int
            :rtype: nothing
            if key in self.table:
                node = self.table[key]
                node.val = value
                node = ListNode(key, value)
                if self.count == self.cap:
                    lastNode = self.tail.prev
                self.table[key] = node

Log in to reply

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