LRUCache算法缓存策略（map+doubleLinkedList）

package arithmetic;

import java.util.HashMap;

public class FaceTest81 {
//LRUcache缓存策略map+双向链表
//get、update、put需要时间复杂度达到O1
//map+双向链表结构

public FaceTest81(int capacity) {
	cache = new MyCache(capacity);
}
private MyCache<Integer,Integer> cache;

public int get(int key) {//复用get
	Integer ans = cache.get(key);
	return ans == null ? -1 : ans;
}
//没有就是新增，有就是修改
public void put(int key,int value) {
	cache.set(key,value);
}

//节点类型，包含键值，上一个节点和下一个节点
public static class Node<K,V> {
	public K key;
	public V value;
	public Node <K,V> last;//上一个节点
	public Node <K,V> next;//下一个节点
	public Node(K key,V value) {
		this.key = key;
		this.value=value;
	}
}


//双向链表
public static class NodeDoubleLinkedList<K,V>{
	private Node<K,V> head;
	private Node<K, V> tail;
	public NodeDoubleLinkedList() {
		head = null;
		tail = null;
	}
	
	//构建双向链表的增删改查的方法
	public void addNode(Node<K, V> newNode) {
		if (newNode == null) {
			return;
		}
		if (head == null) {
			head = newNode;
			tail = newNode;
		}else {
			tail.next = newNode;
			newNode.last=tail;
			tail = newNode;
		}
	}
	
	//将节点放入尾部
	public void moveNodeToTail(Node<K, V> node) {//每次操作都会调用
		if (this.tail == node) {//本来就是尾部，直接返回
			return;
		}
		//先将节点拿出来
		if (this.head == node) {//如果他是头部，直接让下一个当头
			this.head = node.next;
			this.head.last = null;
		} else {//
			node.last.next = node.next;
			node.next.last = node.last;
		}
		//将拿出来的节点节点放入尾部
		node.last = this.tail;
		node.next = null;
		this.head.last = null;
	}
	
	public Node<K, V> removeHead(){//超出容量的时候使用
		if (this.head == null) {
			return null;
		}
		//先将节点拿出来
		Node<K, V> res = this.head;
		//直接处理
		if (this.head == this.tail) {
			this.head = null;
			this.tail = null;
		}else {
			this.head = res.next;
			res.next = null;
			this.head.last = null;
		}
		return res;
	}
	
}
//建立缓存策略
public static class MyCache<K,V>{
	private HashMap<K, Node<K,V>> keyNodeMap;
	private NodeDoubleLinkedList<K,V> nodeList;
	private final int capacity;
	public MyCache(int cap) {
		keyNodeMap = new HashMap<K, Node<K,V>>();
		nodeList = new NodeDoubleLinkedList<K, V>();
		capacity = cap;
	}

	public V get(K key) {
		if (keyNodeMap.containsKey(key)) {
			Node<K, V> res = keyNodeMap.get(key);
			nodeList.moveNodeToTail(res);//取出来放入尾部
			return res.value;
		}
		return null;
	}
	//没有就是新增，有就是修改
	public void set(K key, V value) {
		//有就是修改
		if (keyNodeMap.containsKey(key)) {
			Node<K, V> node = keyNodeMap.get(key);
			node.value = value;
			nodeList.moveNodeToTail(node);
		}else {//新增
			Node<K, V> newNode = new Node<K, V>(key, value);
			keyNodeMap.put(key, newNode);
			nodeList.addNode(newNode);
			if (keyNodeMap.size() == capacity + 1) {
				remoceMostUnusedCache();
			}
		}
		
	}

	private void remoceMostUnusedCache() {//超出容量，移除不常用的头部
		Node<K, V> removenoNode = nodeList.removeHead();	
		keyNodeMap.remove(removenoNode.key);
	}
	
}

}