Leetcode-LRU缓存机制

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

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

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

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

解题思路：

LRU ：最近最少使用
在Java语言中，LinkedList是一种常用的数据容器，并且LinkeList实现了list和Deque接口，所以具备列表操作和双向队列的能力，如API：

增
public boolean add(E e)，链表末尾添加元素，返回是否成功；
public void add(int index, E element)，向指定位置插入元素；
public boolean addAll(Collection<? extends E> c)，将一个集合的所有元素添加到链表后面，返回是否成功；
public boolean addAll(int index, Collection<? extends E> c)，将一个集合的所有元素添加到链表的指定位置后面，返回是否成功；
public void addFirst(E e)，添加到第一个元素；
public void addLast(E e)，添加到最后一个元素；
public boolean offer(E e)，向链表末尾添加元素，返回是否成功；
public boolean offerFirst(E e)，头部插入元素，返回是否成功；
public boolean offerLast(E e)，尾部插入元素，返回是否成功；

删
public void clear()，清空链表；
public E removeFirst()，删除并返回第一个元素；
public E removeLast()，删除并返回最后一个元素；
public boolean remove(Object o)，删除某一元素，返回是否成功；
public E remove(int index)，删除指定位置的元素；
public E poll()，删除并返回第一个元素；
public E remove()，删除并返回第一个元素；

查
public boolean contains(Object o)，判断是否含有某一元素；
public E get(int index)，返回指定位置的元素；
public E getFirst(), 返回第一个元素；
public E getLast()，返回最后一个元素；
public int indexOf(Object o)，查找指定元素从前往后第一次出现的索引；
public int lastIndexOf(Object o)，查找指定元素最后一次出现的索引；
public E peek()，返回第一个元素；
public E element()，返回第一个元素；
public E peekFirst()，返回头部元素；
public E peekLast()，返回尾部元素；

改
public E set(int index, E element)，设置指定位置的元素；

所以我们可以借助LinkedList列表操作和HashMap查找的特性来实现LRU
(ps: java 存在api：LinkedHashMap可以认为是HashMap+LinkedList，即它既使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序)。

显然使用HashMap+LinkedList或者LinkedHashMap能够很容易解答该题，但是直接使用语言自带API并不是该题的初衷，所以我们要模仿LinkedHashMap：

1.HashMap,用来存储key和链表节点，方便后续查询操作
2.双向链表，方便节点的操作，如增删改。

综上，代码如下：

class LRUCache {

    private int capacity;
    private int count;
    private Map<Integer,Node> map = new HashMap<Integer,Node>();

    //定义头尾伪节点，这样在添加和删除节点时不需要判断相邻节点是否存在问题
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.count = 0;

        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {

        Node node = map.get(key);
        if(node == null)
        {
            return -1;
        }

        removeNode(node);
        moveToHead(node);
        return node.val;

    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if(node != null)
        {
            node.val = value;

            removeNode(node);
            moveToHead(node);
        }else
        {
            Node newNode = new Node(key,value);
            //容量已满，需要删除尾部节点（其实是倒数第二个节点）
            if(count == capacity)
            {
                int tailKey = removeTail(tail);
                map.remove(tailKey);
            }else{
                count++;
            }
            moveToHead(newNode);
            map.put(key,newNode);
        }
    }

    public void removeNode(Node node)
    {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    //将node添加到头结点（其实是插入到head伪节点之后）
    public void moveToHead(Node node)
    {
        Node second = head.next; //获取真正的head节点

        head.next = node;
        node.pre = head;

        node.next = second;
        second.pre = node;
    }

    //删除尾结点（倒数第二个节点才是真正的尾结点）
    public int removeTail(Node node)
    {
        Node pre = tail.pre;
        removeNode(pre);
        return pre.key;
    }

    /**
    * 自定义双向链表
    */
    class Node
    {
        public Node pre;
        public Node next;
        public int key;
        public int val;
    
        //默认无参构造
        public Node()
        {
        }
        //有参构造 
        public Node(int key,int val)
        {
            this.key = key;
            this.val = val;
        }
    }
}