Problem statement

https://leetcode.com/problems/lru-cache/

Solution

If O(1) complexity is not required, than it is enough to keep one dictionary and one array of orders of elements, which we need to update. For O(1) solution we can use dictionary, where we keep links to nodes of double-linked list. The idea is the following:

  1. Keep doubly-linked list with values - for siplicity we use looped list, where tail is connected with head.

  2. Keep also dictionary, where for each value we have address of corresponding node in our linked list.

  3. get(self, key) will work like this: we look for our node in self.dic, remove it from given place and put it to the end.
  4. put(self, key, value) will work like this: first we check if key in self.dic and if it is, remove it from linked list. Then we create new node, add it to the end and to self.dic. Also if we out of capacity, we remove head and delete it from self.dic.

Complexity

Time complexity of all operations is O(1).

Code

#### borrowed code
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 = {}
        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 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.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