Clean python code with Doubly Linked List + HashTable

  • 2
    class LinkedListNode(object):
        def __init__(self, key=None, val=-1):
            self.key = key
            self.val = val
            self.pre = None
   = None
    class LinkedList(object):
        def __init__(self):
            self.head = None
            self.tail = None
            self.size = 0
        def appendHead(self, node):
  , node.pre = self.head, None
            if self.head:
                self.head.pre = node
            self.head = node
            if not self.tail:
                self.tail = self.head
            self.size += 1
        def remove(self, node):
            if not node:
            pre, next = node.pre,
            if pre:
       = next
            if next:
                next.pre = pre
            if self.head == node:
                self.head = next
            if self.tail == node:
                self.tail = pre
            self.size -= 1
            return node
        def removeTail(self):
            return self.remove(self.tail)
        def advance(self, node):
    class LRUCache(object):
        def __init__(self, capacity):
            self.capacity = capacity
            self.record = {}
            self.linkedList = LinkedList()
        def get(self, key):
            if key not in self.record:
                return -1
            return self.record[key].val
        def set(self, key, value):
            if key not in self.record:
                node = LinkedListNode(key, value)
                self.record[key] = node
                if self.linkedList.size > self.capacity:
                    del self.record[self.linkedList.removeTail().key]
                self.record[key].val = value

Log in to reply

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