LRU算法

设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

代码实现下载地址

核心思想：

通过HashMap结合双链表的方法实现，HashMap获取value可以达到O(1)的效率

核心算法：

/*添加Node*/

public void addNode(DLinkedList node){

    node.pre   = head;    //将添加node的pre指向头

    node.next = head.next;    //将添加node的next指向头的next

    head.next.pre = node;    //将原来头的next节点的pre节点指向node

    head.next = node;    //将头的next节点指向node

}

/*移除node，然后将node的pre与next节点进行关联*/

public void removeNode(DLinkedList node){

    DLinkedList pre = node.pre;    //获取node的pre节点

    DLinkedList next = node.next;    //获取node的next节点

    pre.next = next;    //pre节点的next节点指向next节点

    next.pre = pre;    //next节点的pre节点指向pre节点

}

/*将新增节点移到头部*/

public void moveToHead(DLinkedlist node){

    this.removeNode(node);    //先删除节点在原始链表中的位置

    this.addNode(node);    //添加节点到头

}

/*删除尾部节点*/

public DLinkedList popTail(){

    DLinkedList pre = this.tail.pre;

    this.removeNode(pre);

    return pre;

}