LFU实现

public static class Node{
			//HashMap<Integer, Node> records,key是用来查找
			public Integer key;
			public Integer value;
			//HashMap<Node, NodeList> heads是根据times来排序的
			public Integer times;
			public Node up;
			public Node down;
			//初始化
			public Node(int key,int value,int times) {
				this.key=key;
				this.value=value;
				this.times=times;
			}
		}
		
		public static class LFUCache{
			//head双向链表的每个节点都会有一个子双向链表
			public static class NodeList{
				public Node head;
				public Node tail;
				public NodeList last;
				public NodeList next;
				//初始化，不允许空链表的出现
				public NodeList(Node node) {
					head=node;
					tail=node;
				}
				
				public void addNodeFromHead(Node newHead) {
					newHead.down=head;
					head.up=newHead;
					head=newHead;
				}
				
				public boolean isEmpty() {
				//head==null为真，反之为假，查看当前双向列表是否为空
					return head ==null;
				}
				
				public void deleteNode(Node node) {
					if(head==tail) {
					//链表中只有一个节点
						head=null;
						tail=null;
					}
					//列表中不止一个节点
					else {
						if(node==head) {
						//要删除的节点是头节点就进行换头操作（headList）
							head=node.down;
							head.up=null;
						}
						//要删除的节点是尾结点就进行换尾操作
						else if(node==tail) {
							tail=node.up;
							tail.down=null;
						}
						//要删除的节点位于链表中间
						else {
							node.up.down=node.down;
							node.down.up=node.up;
						}
					}
					//将要删除的节点前后指针指向空
					node.up=null;
					node.down=null;
				}
			}
			
			private int capacity;//容量
			private int size;//现有节点数
			private HashMap<Integer,Node>records;
			private HashMap<Node,NodeList>heads;
			private NodeList headList;
			//每个频率次数的双向链表
			public LFUCache(int capacity) {
				this.capacity=capacity;
				this.size=0;
				this.records=new HashMap<>();
				this.heads=new HashMap<>();
				headList=null;
			}
			
			public void set(int key,int value) {
				//如果records中包含此值
				if (records.containsKey(key)) {
					//获得该节点
					Node node=records.get(key);
					node.value=value;
					node.times++;
					//获得times++后的子双向链表
					NodeList curNodeList=heads.get(node);
					//将set的节点从老链表移到新链表
					move(node,curNodeList);
				}
				//如果records中不包含此值
				else {
					//如果已经超出内存就要先移除一个，再添加
					if(size==capacity) {
						//定位到head的尾部（那是访问频率最少处）
						Node node=headList.tail;
						//调用已经定义的删除节点函数
						headList.deleteNode(node);
						modifyHeadList(headList);
						//移除node在records的记录
						records.remove(node.key);
						//移除node在heads中的记录
						heads.remove(node);
						size--;
					}
					Node node=new Node(key,value,1);
					if(headList==null) {
						//频率链表如果为空，Node为第一个值
						headList=new NodeList(node);
					}
					//Node不是第一个值
					else {
						//如果1频率的头节点存在，我就接着放
						if(headList.head.equals(node.times))
						{
							headList.addNodeFromHead(node);
						}
						//如果没有1频率的头节点，我就得新建一个
						else{
							NodeList newList=new NodeList(node);
							newList.next=headList;
							headList.last=newList;
							headList=newList;
						}
					}
					records.put(key, node);
					heads.put(node, headList);
					size++;
				}
			}
			//将访问过的节点从老链表移入新链表中
			private void move(Node node,NodeList oldNodeList) {
				//老链表中先将要移除的节点移除
				oldNodeList.deleteNode(node);
				//modifyHeadList(oldNodeList)
				//判断//删除节点后是否要将链表也删掉(发生在你把节点删除后)
				//如果删除了旧链表preList就是旧链表的前一个
				//如果没有删除旧链表preList就是旧链表
				NodeList preList=modifyHeadList(oldNodeList)?oldNodeList.last:oldNodeList;
				NodeList nextList=oldNodeList.next;
				if(nextList==null) {
					//旧链表后面接的是空
					//新建一个新的频率头节点
					NodeList newList=new NodeList(node);
					if(preList!=null) {
					//旧链表的前面的链表不是空
						preList.next=newList;
					}
					newList.last=preList;
					if(headList==null) {
						headList=newList;
					}
					//将node换到newList中
					heads.put(node, newList);
				}
				//如果旧链表后面接的不是空
				else{
					//如果节点的频率和旧链表后的频率相同
					if(nextList.head.times.equals(node.times)) {
						nextList.addNodeFromHead(node);
						heads.put(node,nextList);
					}
					//如果不同，还得新建一个频率头节点
					else {
						NodeList newList=new NodeList(node);
						if(preList!=null) {
							preList.next=newList;
						}
						newList.last=preList;
						newList.next=nextList;
						nextList.last=newList;
						//说明新链表建在频率头节点的前面
						if(headList==nextList) {
							headList=newList;
						}
						//将node放到新链表中
						heads.put(node, newList);
					}
				}
			}			
			
			//删除节点后是否要将链表也删掉(发生在你把节点删除后)
			private boolean modifyHeadList(NodeList nodeList) {
				//如果删除节点后链表空了
				if(nodeList.isEmpty()) {
					//如果频率链表和要删除的子链表相同
					if(headList==nodeList)
					//新头部就是下一个
					headList=nodeList.next;
					//如果新头部也是空就不用管
					//如果新头部不为空
					if(headList!=null) {
					//让它的前指向为空
						headList.last=null;
					}
				}
				//如果删除节点后链表后没有空
				else {
					nodeList.last.next=nodeList.next;
					//如果nodelist下一个节点不是空，让它的下个节点的前指向为上一个
					if(nodeList.next!=null) {
						nodeList.next.last=nodeList.last;
					}
					return true;
				}
				return false;
			}	
		}