通过双向链表和哈希表实现
双向链表靠近头部是最近使用的键值对
双向链表靠近尾部是最久未被使用的键值对
哈希表将缓存数据作为key， value为其在双向链表中的位置
首先通过哈希表找到该项在双向链表中的位置，然后将其移动到链表的头部
对于get操作：
首先判断key是否存在，不存在返回-1
如果key存在，通过哈希表找出对应的位置，然后将它移动到头部
对于put操作：
如果key不存在，使用key和value创建一个新结点并放到头部，然后判断节点是是否超出容量，如果超出容量，则删除链表尾部节点，并删除出哈希表中对应的项
如果key存在，则更新哈希表中的value，并将链表中结点放到头部
class LRUCache {
//定义双向链表结构
class Node{
int key;
int value;
Node prev;
Node next;
public Node(){key = -1;}
public Node(int k, int v){
key = k;
value = v;
}
}
//定义哈希表和容量以及头尾结点
private Map<Integer, Node> mp = new HashMap<>();
private int capacity;
private Node head, tail;
//
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if(mp.containsKey(key)){
Node node = mp.get(key);
//先删除该结点
node.prev.next = node.next;
node.next.prev = node.prev;
//移动到头部
moveToHead(node);
return node.value;
}else{
return -1;
}
}
public void put(int key, int value) {
if(mp.containsKey(key)){
Node node = mp.get(key);
node.value = value;
node.prev.next = node.next;
node.next.prev = node.prev;
moveToHead(node);
}else{
Node node = new Node(key, value);
mp.put(key, node);
if(mp.size() > capacity){
Node delNode = tail.prev;
mp.remove(delNode.key);
tail.prev.prev.next = tail;
tail.prev = tail.prev.prev;
}
moveToHead(node);
}
}
private void moveToHead(Node node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
}
