LRU cache

cache.py

class Node(object):

    def __init__(self, k, v):
        self.k = k
        self.v = v
        self.next = None
        self.prev = None

    def __str__(self):
        return '%s->%s' % (self.k, self.v)


class Cache(object):

    def __init__(self, max_size):
        assert max_size, 'Cache size must be >= 1'
        self.max_size = max_size
        self._cache = dict()
        self._head = None
        self._tail = None

    def put(self, k, v):
        if k not in self._cache:
            node = Node(k, v)
            self._cache[k] = node
            if not self._head:
                self._head = self._tail = node
                return
            self._head.prev = node
            node.next = self._head
            self._head = node
        else:
            node = self._cache[k]
            node.v = v
            if self._head.next:
                self._move_to_head_of_list(node)
        if len(self._cache) > self.max_size:
            self._evict()

    def _move_to_head_of_list(self, node):
        if not node:
            return
        if node.prev:
            node.prev.next = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self._tail = node.prev
        node.next = self._head
        node.prev = None
        self._head = node

    def _evict(self):
        if self._tail is None:
            return
        k = self._tail.k
        if k not in self._cache:
            return
        node = self._cache.pop(k)
        if node == self._head:
            self._head = self._head.next
        if node == self._tail:
            self._tail = self._tail.prev
            self._tail.next = None
        del node

    def get(self, k):
        if k not in self._cache:
            return
        node = self._cache[k]
        self._move_to_head_of_list(node)
        return node.v

    def __str__(self):
        node = self._head
        s = ''
        while node:
            s += '%s ' % str(node)
            node = node.next
        return s

c = Cache(4)
c.put('a', 'apps')
c.put('b', 'bobbs')
c.put('c', 'cats')
c.put('d', 'dogs')
c.put('e', 'elephant')
c.put('z' , 'zell')
c.put('f', 'fara')
c.get('d')
c.put('e', 'esot')
c.get('z')
print(c)