本文共 3089 字，大约阅读时间需要 10 分钟。

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

/** * 用双向链表实现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();    }}

转载地址：http://qxvli.baihongyu.com/