双向链表实现LRUDemo（待补全HashMap）

昨天刷的题改了又改，写了个比较好看的双链。

/**
 * 用双向链表实现LRU的缓存机制 （最近最少使用）
 * 实现put()方法
 * 当写入已有的数据时，应当提高该节点在链表中的优先级
 * 当Cache容量满时，会删除最近最少使用的数据
 *
 * 这里应当有：
 *  写入的addNode()方法
 *  提升优先级中，删除原有结点的removeNode()方法
 *      这两个可以共同组合成提升优先级的 MoveNodeToHead()方法
 *  踢出最少使用结点的popTail()方法
 *
 */
public class LRUCacheDemo2 {
    /**
     * 双向结点类
     */
    class DLinkNode{
        int val;
        DLinkNode next,prev;
    }

    private int size;   //记录结点数量
    private int capacity;   //Cache容量
    private DLinkNode head,tail;    //头尾节点，不需检查null,防止NullPointerException

    /**
     *  LRUCache的构造方法
     * @param capacity 最大节点容量
     */
    public LRUCacheDemo2(int capacity){
        this.capacity=capacity;  //最大缓存容量
        this.size=0;             //成员结点数量

        head=new DLinkNode();   //head.prev=null;
        tail=new DLinkNode();   //tail.next=null;

        head.next=tail;
        tail.prev=head;
    }

    /**
     * 加入节点
     * @param node
     */
    private void addNode(DLinkNode node){
        node.next=head.next;
        head.next.prev=node;
        head.next=node;
        node.prev=head;
    }

    /**
     * 移除节点
     * @param node
     */
    private void removeNode(DLinkNode node){
        node.prev.next=node.next;
        node.next.prev=node.prev;
    }

    /**
     *  提升优先级
     * @param node
     */
    private void MoveNodeToHead(DLinkNode node){
        removeNode(node);
        addNode(node);
    }

    /**
     * 删除最后结点
     */
    private void popTail(){
        DLinkNode res=tail.prev;
        removeNode(res);
    }

    /**
     * 查找是否有相同值的节点
     * 相同会把它删除后移动到最前面
     * @param val
     */
    private boolean get(int val){
        DLinkNode p=head;
        while(p.next!=tail){
            p=p.next;
            if(p.val==val){
                MoveNodeToHead(p);
                return true;
            }
        }
        return false;
    }

    /**
     * 向Cache中添加节点
     * @param val
     */
    public void add(int val){
        //如果没有找到
        if(!get(val)){
            DLinkNode newNode=new DLinkNode();
            newNode.val=val;
            addNode(newNode);
            size++;
            //超出上限
            if(size>capacity){
                popTail();
                size--;
            }
        }
        //get(val)会在找到时自动迁移 无需else处理
    }

    /**
     * 输出表中结点信息
     * @return
     */
    public String toString(){
        StringBuilder sb = new StringBuilder(" ");
        DLinkNode p=head;
        while(p.next!=tail){
            p=p.next;
            sb.append(p.val).append(" ");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LRUCacheDemo2 lruCache = new LRUCacheDemo2(5);
        lruCache.add(1);
        lruCache.add(2);
        lruCache.add(3);
        lruCache.add(4);
        lruCache.add(5);
        System.out.println("装填capacity数量的结点情况：");
        System.out.println(lruCache.toString());
        System.out.println();

        System.out.println("装填已存在结点的情况：");
        lruCache.add(1);
        System.out.println(lruCache.toString());
        System.out.println();

        System.out.println("装填结点达到上限的情况：");
        lruCache.add(6);
        System.out.println(lruCache.toString());
        System.out.println();
    }
}