小红书的图片存储系统需要设计一个缓存机制，以提高图片的访问速度。假设图片的唯一标识为图片 ID，图片数据存储在磁盘上。请设计一个缓存类，实现以下功能：1. 缓存图片数据，当缓存满时，使用 LRU（最近最少使用）算法淘汰最久未使用的图片。2. 提供获取图片数据的方法，若图片在缓存中则直接返回，否则从磁盘读取并缓存。3. 提供更新图片数据的方法，若图片已在缓存中则更新，否则添加到缓存。

Question

Accepted Answer

采用面向对象设计法。答题框架：定义缓存类，包含缓存容量、缓存字典和双向链表等属性，实现获取和更新图片数据的方法。关键要点：1. 定义缓存类，初始化缓存容量、缓存字典和双向链表。2. 实现 get 方法，若图片在缓存中，将其移动到链表头部并返回数据，否则从磁盘读取并添加到缓存。3. 实现 put 方法，若图片已在缓存中，更新数据并移动到链表头部，否则添加到缓存，若缓存满则淘汰最久未使用的图片。4. 双向链表用于维护图片的访问顺序。示例思路：我会定义一个缓存类，使用字典存储图片数据，双向链表维护访问顺序。在 get 方法中，若图片在缓存中，将其移到链表头部；在 put 方法中，根据情况更新或添加图片，若缓存满则淘汰最久未使用的图片。代码示例：
python
class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
        else:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size -= 1

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

def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node