用Python实现树形结构的缓存算法

class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.parent = None
        self.child = None
        self.prev = None   # previous node
        self.next = None   # next node

class LRU_Cache:
    def __init__(self, capacity=5):
        self.capacity = capacity
        self.size = 0
        self.root = Node()  # the root node of the tree
        self.cache = {}     # the key-value pairs stored in the tree

    def add_node_to_tail(self, node):
        """Add a node to the end of the doubly linked list."""
        if self.root.prev is None:
            self.root.prev = node
        else:
            tail = self.root.prev
            tail.next = node
            node.prev = tail
        self.root.prev = node

    def remove_node(self, node):
        """Remove a node from the doubly linked list."""
        prev = node.prev
        next = node.next
        if prev is not None:
            prev.next = next
        if next is not None:
            next.prev = prev
        if node == self.root.prev:
            self.root.prev = prev

    def remove_node_from_head(self):
        """Remove the node at the head of the doubly linked list."""
        head = self.root.next
        if head is None:
            return None
        else:
            self.remove_node(head)
            return head

    def move_node_to_tail(self, node):
        """Move a node to the end of the doubly linked list."""
        self.remove_node(node)
        self.add_node_to_tail(node)

    def get(self, key):
        """Get the value of a key in the cache."""
        if key not in self.cache:
            return None
        node = self.cache[key]
        self.move_node_to_tail(node)
        return node.value

    def put(self, key, value):
        """Put a key-value pair into the cache."""
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_node_to_tail(node)
        else:
            if self.size == self.capacity:
                head = self.remove_node_from_head()
                if head is not None:
                    del self.cache[head.key]
                self.size -= 1
            node = Node(key, value)
            self.add_node_to_tail(node)
            self.cache[key] = node
            self.size += 1

cache = LRU_Cache(3)

cache.put("pidancode.com", "Welcome to pidancode.com!")
cache.put("python", "Python is awesome!")
cache.put("tree", "This is a tree-structured cache.")
assert cache.get("python") == "Python is awesome!"

assert cache.get("tree") == "This is a tree-structured cache."
assert cache.get("pidancode.com") == "Welcome to pidancode.com!"

cache.put("lru", "LRU is a popular caching algorithm.")
assert cache.get("python") == None  # python was the oldest, evicted by LRU
assert cache.get("lru") == "LRU is a popular caching algorithm."