Python Dict + Double LinkedList


  • 37
    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?


  • 2
    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.


  • 1
    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
    

  • 0
    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
    

Log in to reply
 

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