Python Dict + Double LinkedList


  • 53
    T
    class Node:
    def __init__(self, k, v):
        self.key = k
        self.val = v
        self.prev = None
        self.next = None
    
    class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.dic = dict()
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key):
        if key in self.dic:
            n = self.dic[key]
            self._remove(n)
            self._add(n)
            return n.val
        return -1
    
    def set(self, key, value):
        if key in self.dic:
            self._remove(self.dic[key])
        n = Node(key, value)
        self._add(n)
        self.dic[key] = n
        if len(self.dic) > self.capacity:
            n = self.head.next
            self._remove(n)
            del self.dic[n.key]
    
    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p
    
    def _add(self, node):
        p = self.tail.prev
        p.next = node
        self.tail.prev = node
        node.prev = p
        node.next = self.tail

  • 2

    I think this solution is better than the most upvotes Java solution since it has less methods and the algorithm is more clear. Thank you!


  • 0
    N

    Hi, can you explain your solution a little bit?


  • 3
    X

    @nicsin my code has some comment, same idea, might be a little easier to read

    class LRUCache(object):
    
        def __init__(self, capacity):
            self.capacity = capacity
            self.head = LinkedNode(None,'head')
            self.tail = LinkedNode(None,'tail')
            self.head.next = self.tail # tail being most recent
            self.tail.prev = self.head # head being oldest
            self.data = {}
            
        def deleteNode(self,node):
            assert(node is not self.head and node is not self.tail)
            del self.data[node.key]
            node.prev.next = node.next
            node.next.prev = node.prev
            del node
            
        def get(self,key):
            if key not in self.data:
                return -1
            node = self.data[key]
            # take the node out
            node.prev.next = node.next
            node.next.prev = node.prev
            # insert into most recent position
            self.insertNew(node)
            return node.value
    
        def put(self, key, value):
            # remove old value if present
            if key in self.data:
                self.deleteNode(self.data[key])
            
            # create new node
            newNode = LinkedNode(key,value)
            self.data[key] = newNode
            
            # if over limit, delete oldest node
            if len(self.data)>self.capacity:
                self.deleteNode(self.head.next)
            
            self.insertNew(newNode)
            
        def insertNew(self,newNode):
            # insert new node into last position    
            last = self.tail.prev
            last.next = newNode
            self.tail.prev = newNode
            newNode.next = self.tail
            newNode.prev = last
    

  • 0
    R

    Really good solution. Used double linked list to achieve constant access and update time. Upvoted :)


  • 1
    A

    Using dummy nodes for the head and tail is a really good idea. You don't have to account for a couple annoying edge cases when you do this.


  • 2
    S

    A much shorter solution with about the same complexity as the OP.

    OP Runtime = 246ms, faster than 89.57% of all Python submissions.
    Soln below Runtime = 275ms, faster than 74.80% of all Python submissions.

    from collections import OrderedDict
    
    class LRUCache(object):
        def __init__(self, capacity):
            self.array = OrderedDict()
            self.capacity = capacity
    
        def get(self, key):
            if key in self.array:
                value = self.array[key]
                # Remove first
                del self.array[key]
                # Add back in
                self.array[key] = value
                return value
            else:
                return -1
    
        def put(self, key, value):
            if key in self.array:
                # Delete existing key before refreshing it
                del self.array[key]
            elif len(self.array) >= self.capacity:
                # Delete oldest
                k, v = self.array.iteritems().next()
                del self.array[k]
            self.array[key] = value
    

  • 1
    D

    mimic the internal implementation of OrderedDict

    class LRUCache(object):
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.capacity = capacity
    
            # https://github.com/python/cpython/blob/2.7/Lib/collections.py
            # Node: [prev, next, key, val]
            root = self._root = []
            root[:] = [root, root, None, None]
    
            self._data = {}  # key -> node
    
        def _pop(self, key=None):
            root, data = self._root, self._data
            if key is None:
                node = root[1]
                key = node[2]
            else:
                node = data[key]
    
            prev, next, key, val = node
            prev[1], next[0] = next, prev
            del data[key]
    
            return val
    
        def _insert(self, key, val):
            root, data = self._root, self._data
            assert key not in data
    
            prev = root[0]
            node = [prev, root, key, val]
            prev[1] = root[0] = node
            data[key] = node
    
        def get(self, key):
            data, root = self._data, self._root
            if not key in data: return -1
    
            val = self._pop(key)
            self._insert(key, val)
    
            return val
    
        def put(self, key, value):
            data = self._data
            if key in data:
                self._pop(key)
    
            if len(data) == self.capacity:
                self._pop()
    
            self._insert(key, value)
    
    

  • 0
    U

    Great solution! Probably we don't need head and tail nodes.

    class Node:
        def __init__(self, k, v):
            self.key = k
            self.val = v
            self.prev = None
            self.next = None
    
    class LRUCache:
        def __init__(self, capacity):
            self.capacity = capacity
            self.dic = dict()
            self.prev = self.next = self
            
        def get(self, key):
            if key in self.dic:
                n = self.dic[key]
                self._remove(n)
                self._add(n)
                return n.val
            return -1
    
        def put(self, key, value):
            if key in self.dic:
                self._remove(self.dic[key])
            n = Node(key, value)
            self._add(n)
            self.dic[key] = n
            if len(self.dic) > self.capacity:
                n = self.next
                self._remove(n)
                del self.dic[n.key]
    
        def _remove(self, node):
            p = node.prev
            n = node.next
            p.next = n
            n.prev = p
    
        def _add(self, node):
            p = self.prev
            p.next = node
            self.prev = node
            node.prev = p
            node.next = self
    

  • 1
    X

    @starchild You can use .popitem(False) to pop the first item in ordereddict

    from collections import OrderedDict
    class LRUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.cap = capacity
            self.dict = OrderedDict()
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            if key in self.dict:
                val = self.dict[key]
                del self.dict[key]
                self.dict[key] = val
                return val
            else:
                return -1
    
        def put(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if key in self.dict:
                del self.dict[key]
            elif len(self.dict) >= self.cap:
                self.dict.popitem(False)
            self.dict[key] = value
    

    OrderedDict.popitem(last=True)
    The popitem() method for ordered dictionaries returns and removes a (key, value) pair. The pairs are returned in LIFO order if last is true or FIFO order if false.


  • 0

    Could you please go over what each function uses? This is one of the only Python solutions and yet it has multiple funcitons whereas the problem only defines two


Log in to reply
 

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