lru_cache.py

class Node:
    def __init__(self, value, key=None, next=None, prev=None):
        self.value = value
        self.next = next
        self.prev = prev
        self.key = key


class LRUCache:

    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.hash = {}
        self.tail = None
        self.head = None
        self.key = None


    def get(self, key):
        node = self.hash.get(key, None)

        if node is None:
            return -1

        next = node.next
        prev = node.prev
        tail = self.tail

        if next is not None:
            if prev is None:
                self.head = next
                next.prev = None
            else:
                prev.next = next
                next.prev = prev

            node.prev = tail
            tail.next = node

            node.next = None
            self.tail = node

        return node.value

    def _delete_tail(self, node):
        prev = node.prev
        prev.next = None
        node.prev = None
        self.tail = prev

    def _delete_head(self, node):
        next = node.next
        next.prev = None
        node.next = None
        self.head = next

    def _delete_node(self, node):
        if node.prev == None:
            self._delete_head(node)
        elif node.next == None:
            self._delete_tail(node)
        else:
            # Node in middle
            prev = node.prev
            next = node.next
            prev.next = next
            next.prev = prev

    def put(self, key, value):
        node = Node(value)
        node.key = key

        if self.tail is None and self.head is None:
            self.tail = node
            self.head = node
        else:
            tail = self.tail
            tail.next = node

            node.prev = tail
            node.next = None
            self.tail = node

        key_exists = self.hash.get(key)

        if key_exists:
            self.size -= 1
            self._delete_node(key_exists)

        self.hash[key] = node
        self.size += 1

        if self.size > self.capacity and not key_exists:
            head = self.head
            self._delete_head(self.head)
            del self.hash[head.key]
            self.size -= 1


if __name__ == "__main__":
    def test_1():
        cache = LRUCache(2)
        cache.put(2, 1)
        cache.put(1, 1)
        cache.put(2, 3)
        cache.put(4, 1)
        assert cache.get(1) == -1
        assert cache.get(2) == 3

    def test_2():
        cache = LRUCache(2)
        cache.put(1, 1)
        cache.put(2, 2)
        assert cache.get(1) == 1
        cache.put(3, 3)
        assert cache.get(2) == -1
        cache.put(4, 4)
        assert cache.get(1) == -1
        assert cache.get(3) == 3
        assert cache.get(4) == 4

    def test_3():
        cache = LRUCache(10)
        cache.put(10, 13)
        cache.put(3, 17)
        cache.put(6, 11)
        cache.put(10, 5)
        cache.put(9, 10)
        assert cache.get(13) == -1
        cache.put(2, 19)
        assert cache.get(2) == 19
        assert cache.get(3) == 17
        cache.put(5, 25)
        assert cache.get(8) == -1
        cache.put(9, 22)
        cache.put(5, 5)
        cache.put(1, 30)
        assert cache.get(11) == -1
        cache.put(9, 12)
        assert cache.get(7) == -1
        assert cache.get(5) == 5
        assert cache.get(8) == -1
        assert cache.get(9) == 12
        cache.put(4, 30)
        head = cache.head
        cache.put(9, 3)
        assert cache.get(9) == 3
        assert cache.get(10) == 5
        assert cache.get(10) == 5
        cache.put(6, 14)
        cache.put(3, 1)
        assert cache.get(3) == 1
        cache.put(10, 11)
        assert cache.get(8) == - 1
        cache.put(2, 14)
        assert cache.get(1) == 30
        assert cache.get(5) == 5
        assert cache.get(4) == 30

    test_1()
    test_2()
    test_3()