Implementing LFU Cache with linked lists of linked lists.

lfu_cache.py

class EnhancedLinkedListNode:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c
        self.next = None
        self.prev = None

    def remove(self):
        if self.prev:
            self.prev.next = self.next
        if self.next:
            self.next.prev = self.prev
        self.next = self.prev = None

    def __str__(self):
        return '{}/({})'.format(
            self.a, self.b) if not self.next else '{}/({}) -> {}'.format(
                self.a, self.b, self.next)


class LFUCache:
    def __init__(self, capacity: int):
        """
        We can use linked list of linked lists
        backbone - linked list holding linked lists
        map = holding key-node pair for every node of the backbone's linked lists

        Backbone Node
        a - freq
        b - list head
        c - list tail

        Node
        a - key
        b - value
        c - reference to the backbone node
        """
        self.backbone = None
        self.map = {}
        self.capacity = capacity

    def increment_freq(self, key):
        node = self.map[key]
        bnode_curr = node.c

        if bnode_curr.b == node:
            bnode_curr.b = node.next

        if bnode_curr.c == node:
            bnode_curr.c = node.prev

        node.remove()

        freq = bnode_curr.a
        if not bnode_curr.next or bnode_curr.next.a > freq + 1:
            bnode = EnhancedLinkedListNode(freq + 1, node, node)
            node.c = bnode
            bnode.prev = bnode_curr
            bnode.next = bnode_curr.next
            bnode_curr.next = bnode
            if bnode.next:
                bnode.next.prev = bnode
        else:
            bnode = bnode_curr.next
            head = bnode.b
            bnode.b = node
            node.c = bnode
            node.next = head
            head.prev = node

        if not bnode_curr.b:
            if self.backbone == bnode_curr:
                self.backbone = bnode_curr.next
            bnode_curr.remove()

    def remove_least_frequent(self):
        if self.backbone.c == self.backbone.b:
            b = self.backbone
            self.backbone = b.next
            b.remove()
            b.b.remove()
            del self.map[b.b.a]
        else:
            tail = self.backbone.c
            self.backbone.c = tail.prev
            tail.remove()
            del self.map[tail.a]

    def get(self, key: int) -> int:
        if key in self.map:
            self.increment_freq(key)
            return self.map[key].b
        return -1

    def put(self, key: int, value: int) -> None:
        if not self.capacity:
            return
        if key in self.map:
            self.map[key].b = value
            self.increment_freq(key)
        else:
            if len(self.map) == self.capacity:
                self.remove_least_frequent()
            node = EnhancedLinkedListNode(key, value, None)
            self.map[key] = node
            if not self.backbone or self.backbone.a != 1:
                bnode = EnhancedLinkedListNode(1, node, node)
                node.c = bnode
                bnode.next = self.backbone
                if bnode.next:
                    bnode.next.prev = bnode
                self.backbone = bnode
            else:
                node.c = self.backbone
                node.next = self.backbone.b
                node.next.prev = node
                self.backbone.b = node