请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

需要满足：

1. 初始化容量
2. get方法，从缓存获取一个数
3. put方法，将一个数放入缓存，如果已经存在，则更新值
4. 如果缓存中的数超过容量，则删除最近最少使用的那个数
5. 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

解题思路

1. 使用 HashMap + 双向链表 HashMap 用作哈希存取，双向链表用作最近使用排序（最近最多使用的在表头，最少使用的在表尾）
2. 使用 dummyHead 和 dummyTail 虚拟头尾，避免处理空指针
3. 调用 get 方法，将该节点移动到表头（先在原位置删除再在头部插入）
4. 调用 put 方法，如果节点不存在，新增节点并移动到头部，如果容量超限，删除最末尾节点，并删除 hashMap 中的记录
5. 双向链表 Node 必须同时存储 key 和 val ， 因为当容量超限时，除了要删除表尾节点，还要删除它在 HashMap 中的记录，没有 key 将会无法删除

Java 实现

public class LRUCache {

	class Node{
		int key;
		int val;
		Node prev;
		Node next;
		public Node(int key, int val) {
			this.key = key;
			this.val = val;
		}
		public Node() {
		}
	}

	Map<Integer, Node> cache = new HashMap<>();
	private int capacity;
	// 避免处理 null ，使用伪头部 (dummy head) 和 伪尾部 (dummy tail)
	private Node dummyHead;
	private Node dummyTail;

	public LRUCache(int capacity) {
		this.capacity = capacity;
		dummyHead = new Node();
		dummyTail = new Node();
		dummyHead.next = dummyTail;
		dummyTail.prev = dummyHead;
	}

	public int get(int key) {
		Node node = cache.get(key);
		if (node == null){
			return -1;
		}
		removeNode(node);
		moveToHead(node);
		return node.val;
	}

	/**
	 * 删除节点，即节点的上一个节点接到原节点的下一个节点
	 */
	private void removeNode(Node node){
		node.prev.next = node.next;
		node.next.prev = node.prev;
	}

	/**
	 * 将节点移动到头部
	 */
	private void moveToHead(Node node){
		// 节点移动到头部
		node.next = dummyHead.next;
		node.prev = dummyHead;
		// 原头部调整
		dummyHead.next.prev = node;
		// dummy 调整
		dummyHead.next = node;
	}

	public void put(int key, int value) {
		Node node = cache.get(key);
		// 如果节点不存在，新增节点并移动到头部
		if (node == null){
			node = new Node(key, value);
			moveToHead(node);
			cache.put(key, node);
			// 如果容量超限，删除最末尾节点，并删除 hashMap 中的记录
			if (cache.size() > capacity){
				Node tail = dummyTail.prev;
				cache.remove(tail.key);
				removeNode(tail);
			}
		}
		// 如果节点存在，更新值并移动到头部
		node.val = value;
		removeNode(node);
		moveToHead(node);
	}
}