Python Double Linked List


  • 0
    class LinkedList(object):
        def __init__(self, val, key):
            self.val, self.key = val, key
            self.next, self.pre = None, None
    
    
    class LRUCache(object):
        def __init__(self, capacity):
            self.dic, self.cap, self.h, self.r = {}, capacity, LinkedList(-1, -1), LinkedList(-1, -1)
            self.h.next = self.r
            self.r.pre = self.h
    
        def get(self, key):
            if key not in self.dic:
                return -1
            ans = self.dic[key]
            pre, net = ans.pre, ans.next
            pre.next = net
            net.pre = pre
            head = self.h.next
            self.h.next = ans
            ans.pre = self.h
            ans.next = head
            head.pre = ans
            return self.dic[key].val
    
        def set(self, key, value):
            if not key in self.dic:
                if len(self.dic) == self.cap:
                    del self.dic[self.r.pre.key]
                    r = self.r.pre.pre
                    r.next = self.r
                    self.r.pre = r
                self.dic[key] = LinkedList(value, key)
    
            else:
                pre, net = self.dic[key].pre, self.dic[key].next
                pre.next = net
                net.pre = pre
                self.dic[key].val = value
            head = self.h.next
            self.h.next = self.dic[key]
            self.dic[key].pre = self.h
            head.pre = self.dic[key]
            self.dic[key].next = head
    

Log in to reply
 

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